歐幾里德聚類演算法

⑴ 什麼是歐幾里得演算法，它有什麼意義

歐幾里得演算法即輾轉相除法，用以求兩個數的最大公約數（或者最小公倍數）
證明如下
假設x,y的最大公約數為d
且設x=k1*d，y=k2*d;
則有z=x-y=(k1-k2)*d;
也必定能被d整除，所以通過兩個數不斷輾轉，直到其中一個變為0為止，以此最終快速得出兩個數的最大公約數。
在演算法的應用上是用求余以加速運算的速度。
總的來說，歐幾里得演算法的意義就是快速求得兩個數的最大公約數。

⑵ 歐幾里德演算法的介紹

歐幾里德演算法又稱輾轉相除法，用於計算兩個正整數a，b的最大公約數。

⑶ 歐幾里德演算法本質的數學原理是什麼

歐幾里德演算法
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數

假設d 是(b,a mod b)的公約數，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數

因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。

歐幾里德演算法就是根據這個原理來做的，其演算法用C++語言描述為：

void swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}
參考資料：internet

⑷ 歐幾里德演算法的簡單解釋

[編輯本段]歐幾里得演算法的概述 歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a，b的最大公約數。其計算原理依賴於下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 證明：a可以表示成a = kb + r，則r = a mod b 假設d是a,b的一個公約數，則有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公約數 假設d 是(b,a mod b)的公約數，則 d | b ， d |r ，但是a = kb +r 因此d也是(a,b)的公約數 因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證 [編輯本段]歐幾里得演算法原理 Lemma 1.3.1 若 a, b 且 a = bh + r, 其中 h, r , 則 gcd(a, b) = gcd(b, r). 證明. 假設 d1 = gcd(a, b) 且 d2 = gcd(b, r). 我們證明 d1| d2 且 d2| d1, 因而可利用 Proposition 1.1.3(2) 以及 d1, d2 皆為正數得證 d1 = d2. 因 d1| a 且 d1| b 利用 Corollary 1.1.2 我們知 d1| a - bh = r. 因為 d1| b, d1| r 且 d2 = gcd(b, r) 故由 Proposition 1.2.5 知 d1| d2. 另一方面, 因為 d2| b 且 d2| r 故 d2| bh + r = a. 因此可得 d2| d1. Lemma 1.3.1 告訴我們當 a > b > 0 時, 要求 a, b 的最大公因數我們可以先將 a 除以 b 所得餘數若為 r, 則 a, b 的最大公因數等於 b 和 r 的最大公因數. 因為 0r < b < a, 所以當然把計算簡化了. 接著我們就來看看輾轉相除法. 由於 gcd(a, b) = gcd(- a, b) 所以我們只要考慮 a, b 都是正整數的情況. Theorem 1.3.2 (The Euclidean Algorithm) 假設 a, b 且 a > b. 由除法原理我們知存在 h0, r0 使得 a = bh0 + r0, 其中 0r0 < b. 若 r0 > 0, 則存在 h1, r1 使得 b = r0h1 + r1, 其中 0r1 < r0. 若 r1 > 0, 則存在 h2, r2 使得 r0 = r1h2 + r2, 其中 0r2 < r1. 如此繼續下去直到 rn = 0 為止. 若 n = 0 (即 r0 = 0), 則 gcd(a, b) = b. 若 n1, 則 gcd(a, b) = rn - 1. 證明. 首先注意若 r0 0, 由於 r0 > r1 > r2 > ... 是嚴格遞減的, 因為 r0 和 0 之間最多僅能插入 r0 - 1 個正整數, 所以我們知道一定會有 nr0 使得 rn = 0. 若 r0 = 0, 即 a = bh0, 故知 b 為 a 之因數, 得證 b 為 a, b 的最大公因數. 若 r0 > 0, 則由 Lemma 1.3.1 知 gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = ... = gcd(rn - 1, rn) = gcd(rn - 1, 0) = rn - 1. 現在我們來看用輾轉相除法求最大公因數的例子 Example 1.3.3 我們求 a = 481 和 b = 221 的最大公因數. 首先由除法原理得 481 = 2 . 221 + 39, 知 r0 = 39. 因此再考慮 b = 221 除以 r0 = 39 得 221 = 5 . 39 + 26, 知 r1 = 26. 再以 r0 = 39 除以 r1 = 26 得 39 = 1 . 26 + 13, 知 r2 = 13. 最後因為 r2 = 13 整除 r1 = 26 知 r3 = 0, 故由 Theorem 1.3.2 知 gcd(481, 221) = r2 = 13. 在利用輾轉相除法求最大公因數時, 大家不必真的求到 rn = 0. 例如在上例中可看出 r0 = 39 和 r1 = 26 的最大公因數是 13, 利用 Lemma 1.3.1 馬上得知 gcd(a, b) = 13. 在上一節 Corollary 1.2.5 告訴我們若 gcd(a, b) = d, 則存在 m, n 使得 d = ma + nb. 當時我們沒有提到如何找到此 m, n. 現在我們利用輾轉相除法來介紹一個找到 m, n 的方法. 我們沿用 Theorem 1.3.2 的符號. 首先看 r0 = 0 的情形, 此時 d = gcd(a, b) = b 所以若令 m = 0, n = 1, 則我們有 d = b = ma + nb. 當 r0 0 但 r1 = 0 時, 我們知 d = gcd(a, b) = r0. 故利用 a = bh0 + r0 知, 若令 m = 1, n = - h0, 則 d = r0 = ma + nb. 同理若 r0 0, r1 0 但 r2 = 0, 則知 d = gcd(a, b) = r1. 故利用 a = bh0 + r0 以及 b = r0h1 + r1 知 r1 = b - r0h1 = b - (a - bh0)h1 = - h1a + (1 + h0h1)b. 因此若令 m = - h1 且 n = 1 + h0h1, 則 d = r1 = ma + nb. 依照此法, 當 r0, r1 和 r2 皆不為 0 時, 由於 d = gcd(a, b) = rn - 1 故由 rn - 3 = rn - 2hn - 1 + rn - 1 知 d = rn - 3 - hn - 1rn - 2. 利用前面推導方式我們知存在 m1, m2, n1, n2 使得 rn - 3 = m1a + n1b 且 rn - 2 = m2a + n2b 故代入得 d = (m1a + n1b) - hn - 1(m2a + n2b) = (m1 - hn - 1m2)a + (n1 - hn - 1n2)b. 因此若令 m = m1 - hn - 1m2 且 n = n1 - hn - 1n2, 則 d = ma + nb. 上面的說明看似好像當 r0 0 時對每一個 i {0, 1,..., n - 2} 要先將 ri 寫成 ri = mia + nib, 最後才可將 d = rn - 1 寫成 ma + nb 的形式. 其實這只是論證時的方便, 在實際操作時我們其實是將每個 ri 寫成 mi'ri - 2 + ni'ri - 1 的形式慢慢逆推回 d = ma + nb. 請看以下的例子. Example 1.3.4 我們試著利用 Example 1.3.3 所得結果找到 m, n 使得 13 = gcd(481, 221) = 481m + 221n. 首先我們有 13 = r2 = 39 - 26 = r0 - r1. 而 r1 = 221 - 5 . 39 = b - 5r0, 故得 13 = r0 - (b - 5r0) = 6r0 - b. 再由 r0 = 481 - 2 . 221 = a - 2b, 得知 13 = 6(a - 2b) - b = 6a - 13b. 故得 m = 6 且 n = - 13 會滿足 13 = 481m + 221n. 要注意這里找到的 m, n 並不會是唯一滿足 d = ma + nb 的一組解. 雖然上面的推演過程好像會只有一組解, 不過只能說是用上面的方法會得到一組解, 並不能擔保可找到所有的解. 比方說若令 m' = m + b, n' = n - a, 則 m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以 m', n' 也會是另一組解. 所以以後當要探討唯一性時, 若沒有充分的理由千萬不能說由前面的推導過程看出是唯一的就斷言是唯一. 一般的作法是假設你有兩組解, 再利用這兩組解所共同滿足的式子找到兩者之間的關系. 我們看看以下的作法. Proposition 1.3.5 假設 a, b 且 d = gcd(a, b). 若 x = m0, y = n0 是 d = ax + by 的一組整數解, 則對任意 t , x = m0 + bt/d, y = n0 - at/d 皆為 d = ax + by 的一組整數解, 而且 d = ax + by 的所有整數解必為 x = m0 + bt/d, y = n0 - at/d 其中 t 這樣的形式. 證明. 假設 x = m, y = n 是 d = ax + by 的一組解. 由於已假設 x = m0, y = n0 也是一組解, 故得 am + bn = am0 + bn0. 也就是說 a(m - m0) = b(n0 - n). 由於 d = gcd(a, b), 我們可以假設 a = a'd, b = b'd 其中 a', b' 且 gcd(a', b') = 1 (參見 Corollary 1.2.3). 因此得 a'(m - m0) = b'(n0 - n). 利用 b'| a'(m - m0), gcd(a', b') = 1 以及 Proposition 1.2.7(1) 得 b'| m - m0. 也就是說存在 t 使得 m - m0 = b't. 故知 m = m0 + b't = m0 + bt/d. 將 m = m0 + bt/d 代回 am + bn = am0 + bn0 可得 n = n0 - at/d, 因此得證 d = ax + by 的整數解都是 x = m0 + bt/d, y = n0 - at/d 其中 t 這樣的形式. 最後我們僅要確認對任意 t , x = m0 + bt/d, y = n0 - at/d 皆為 d = ax + by 的一組整數解. 然而將 x = m0 + bt/d, y = n0 - at/d 代入 ax + by 得 a(m0 + bt/d )+ b(n0 - at/d )= am0 + bn0 = d, 故得證本定理. 利用 Proposition 1.3.5 我們就可利用 Example 1.3.4 找到 13 = 481x + 221y 的一組整數解 x = 6, y = - 13 得到 x = 6 + 17t, y = - 13 - 37t 其中 t 是 13 = 481x + 221y 所有的整數解

希望採納

⑸ dbscan演算法是什麼

DBSCAN基於高密度連通區域的、基於密度的聚類演算法，能夠將具有足夠高密度的區域劃分為簇，並在具有雜訊的數據中發現任意形狀的簇。我們總結一下DBSCAN聚類演算法原理的基本要點：

DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里德距離來進行度量。

(5)歐幾里德聚類演算法擴展閱讀：

dbscan個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。

（1）適當選擇c個類的初始中心；

（2）在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類；

（3）利用均值等方法更新該類的中心值；

（4）對於所有的c個聚類中心，如果利用（2）（3）的迭代法更新後，值保持不變，則迭代結束，否則繼續迭代。

⑹ 歐幾里德演算法是什麼啊

歐幾里德演算法
歐幾里德演算法又稱輾轉相除法,用於計算兩個整數a,b的最大公約數.其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r,則r = a mod b
假設d是a,b的一個公約數,則有
d|a,d|b,而r = a - kb,因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數,則
d | b ,d |r ,但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的,其最大公約數也必然相等,得證.
歐幾里德演算法就是根據這個原理來做的,其演算法用C++語言描述為：
void swap(int & a,int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}
參考資料：internet

⑺ 關於歐幾里得演算法，主要是看不懂。請高手指點迷津。。。。

1、 歐幾里德演算法：給定兩個正整數m和n，求他們的最大公因子，即能夠同時整除m和n的最大的正整數。
E1：【求余數】以n除m並令r為所得余數（我們將有0<=r<n）。
E2：【余數為0？】若r=0，演算法結束；n即為答案。
E3：【互換】置mßn,nßr,並返回步驟E1.
證明：
我們將兩個正整數m和n的最大公因子表示為：t = gcd（m，n）；
重復應用等式：gcd（m，n）= gcd（n，m mod n）直到m mod n 等於0；
m可以表示成m = kn + r；則 r = m mod n ， 假設 d是 m 和 n的一個公約數，則有：
d|m 和 d|m 而 r =m – kn ，因此 d|r ，因此 d 是 (n,m mod n) 的公約數；假設 d 是 (n,m mod n) 的公約數，
則 d|n ，d|r ，但是 m=kn+r ，因此 d 也是 (a,b) 的公約數；因此 (a,b) 和
(b,a mod b) 的公約數是一樣的，其最大公約數也必然相等，得證。

具體步驟描述如下：
第一步：如果 n=0 ，返回 m 的值作為結果，同時過程結束；否則，進入第二步。
第二步：用 n 去除 m ，將余數賦給 r 。
第三步：將 n 的值賦給 m，將 r的值賦給 n，返回第一步。

偽代碼描述如下：
Euclid(m,n)
// 使用歐幾里得演算法計算gcd(m,n)
// 輸入：兩個不全為0的非負整數m，n
// 輸出：m，n的最大公約數
while n≠0 do
r ← m mod n
m ← n
n ← r
註：(a,b) 是 a,b的最大公因數
(a,b)|c 是指 a,b的最大公因數 可以被c整除。

java實現：
package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class GreatestCommonDivisor {

int a,b,temp = 0;

public static void main(String args[]) throws IOException {

GreatestCommonDivisor gcd = new GreatestCommonDivisor();
gcd.readNum();
gcd.MaxNum();
System.out.print(gcd.a+"和"+gcd.b+"的最大公約數是:");

while (gcd.b != 0) {
gcd.temp = gcd.b;
gcd.b = gcd.a % gcd.b;
gcd.a = gcd.temp;
}
System.out.println(gcd.temp);
}
//輸入兩個正整數,中間用空格分開.
public void readNum() throws IOException{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
String str = buf.readLine();
for(int i = 0;i<str.length();i++){

if(str.charAt(i)==' ' && temp == 0){
a = Integer.parseInt(str.substring(temp,i));
temp = i;
b = Integer.parseInt(str.substring(temp+1,str.length()));
break;
}
}
}
public void MaxNum(){
if (a < b) {
temp = b;
b = a;
a = temp;
}
}

}

⑻ DBSCAN原理和演算法偽代碼，與kmeans，OPTICS區別

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚類演算法，它是一種基於高密度連通區域的、基於密度的聚類演算法，能夠將具有足夠高密度的區域劃分為簇，並在具有雜訊的數據中發現任意形狀的簇。我們總結一下DBSCAN聚類演算法原理的基本要點：
DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里德距離來進行度量。
DBSCAN演算法需要用戶輸入2個參數：一個參數是半徑（Eps），表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量（MinPts）。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點。
DBSCAN聚類使用到一個k-距離的概念，k-距離是指：給定數據集P={p(i); i=0,1,…n}，對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有點之間的距離，距離按照從小到大的順序排序，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，則d(k)就被稱為k-距離。也就是說，k-距離是點p(i)到所有點（除了p(i)點）之間距離第k近的距離。對待聚類集合中每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)}。
根據經驗計算半徑Eps：根據得到的所有點的k-距離集合E，對集合E進行升序排序後得到k-距離集合E』，需要擬合一條排序後的E』集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察，將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值。
根據經驗計算最少點的數量MinPts：確定MinPts的大小，實際上也是確定k-距離中k的值，DBSCAN演算法取k=4，則MinPts=4。
另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變，Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致已一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為雜訊點，MinPts過小，會導致發現大量的核心點。
我們需要知道的是，DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。對於演算法的實現，首先我們概要地描述一下實現的過程：
1）解析樣本數據文件。2）計算每個點與其他所有點之間的歐幾里德距離。3）計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。4）將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢。5）根據散點圖確定半徑Eps的值。）根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與到核心點距離小於半徑Eps的點的映射。7）根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，得到雜訊點。8）將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。9）選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其雜訊點，使用散點圖對比聚類效果。
演算法偽代碼：
演算法描述：
演算法：DBSCAN
輸入：E——半徑
MinPts——給定點在E鄰域內成為核心對象的最小鄰域點數。
D——集合。
輸出：目標類簇集合
方法：Repeat
1）判斷輸入點是否為核心對象
2）找出核心對象的E鄰域中的所有直接密度可達點。
Until 所有輸入點都判斷完畢。
Repeat
針對所有核心對象的E鄰域內所有直接密度可達點找到最大密度相連對象集合，中間涉及到一些密度可達對象的合並。Until 所有核心對象的E領域都遍歷完畢
DBSCAN和Kmeans的區別：
1)K均值和DBSCAN都是將每個對象指派到單個簇的劃分聚類演算法，但是K均值一般聚類所有對象，而DBSCAN丟棄被它識別為雜訊的對象。
2)K均值使用簇的基於原型的概念，而DBSCAN使用基於密度的概念。
3)K均值很難處理非球形的簇和不同大小的簇。DBSCAN可以處理不同大小或形狀的簇，並且不太受雜訊和離群點的影響。當簇具有很不相同的密度時，兩種演算法的性能都很差。
4)K均值只能用於具有明確定義的質心（比如均值或中位數）的數據。DBSCAN要求密度定義（基於傳統的歐幾里得密度概念）對於數據是有意義的。
5)K均值可以用於稀疏的高維數據，如文檔數據。DBSCAN通常在這類數據上的性能很差，因為對於高維數據，傳統的歐幾里得密度定義不能很好處理它們。
6)K均值和DBSCAN的最初版本都是針對歐幾里得數據設計的，但是它們都被擴展，以便處理其他類型的數據。
7)基本K均值演算法等價於一種統計聚類方法（混合模型），假定所有的簇都來自球形高斯分布，具有不同的均值，但具有相同的協方差矩陣。DBSCAN不對數據的分布做任何假定。
8)K均值DBSCAN和都尋找使用所有屬性的簇，即它們都不尋找可能只涉及某個屬性子集的簇。
9)K均值可以發現不是明顯分離的簇，即便簇有重疊也可以發現，但是DBSCAN會合並有重疊的簇。
10)K均值演算法的時間復雜度是O(m)，而DBSCAN的時間復雜度是O(m^2)，除非用於諸如低維歐幾里得數據這樣的特殊情況。
11)DBSCAN多次運行產生相同的結果，而K均值通常使用隨機初始化質心，不會產生相同的結果。
12)DBSCAN自動地確定簇個數，對於K均值，簇個數需要作為參數指定。然而，DBSCAN必須指定另外兩個參數：Eps（鄰域半徑）和MinPts（最少點數）。
13)K均值聚類可以看作優化問題，即最小化每個點到最近質心的誤差平方和，並且可以看作一種統計聚類（混合模型）的特例。DBSCAN不基於任何形式化模型。
DBSCAN與OPTICS的區別：
DBSCAN演算法，有兩個初始參數E（鄰域半徑）和minPts(E鄰域最小點數)需要用戶手動設置輸入，並且聚類的類簇結果對這兩個參數的取值非常敏感，不同的取值將產生不同的聚類結果，其實這也是大多數其他需要初始化參數聚類演算法的弊端。
為了克服DBSCAN演算法這一缺點，提出了OPTICS演算法（Ordering Points to identify the clustering structure）。OPTICS並 不顯示的產生結果類簇，而是為聚類分析生成一個增廣的簇排序（比如，以可達距離為縱軸，樣本點輸出次序為橫軸的坐標圖），這個排序代表了各樣本點基於密度 的聚類結構。它包含的信息等價於從一個廣泛的參數設置所獲得的基於密度的聚類，換句話說，從這個排序中可以得到基於任何參數E和minPts的DBSCAN演算法的聚類結果。
OPTICS兩個概念：
核心距離：對象p的核心距離是指是p成為核心對象的最小E』。如果p不是核心對象，那麼p的核心距離沒有任何意義。
可達距離：對象q到對象p的可達距離是指p的核心距離和p與q之間歐幾里得距離之間的較大值。如果p不是核心對象，p和q之間的可達距離沒有意義。
演算法描述：OPTICS演算法額外存儲了每個對象的核心距離和可達距離。基於OPTICS產生的排序信息來提取類簇。

⑼ 急 歐幾里得演算法是什麼原理啊

在求兩個整數的最大公約數要用到歐幾里得演算法,簡單的說就是：
設A,B(A>B)最大公約數為k,則
A = k*A1
B = k*B1
所以
C = A-B*t = k*(A1-B1*t) (C<B)
得到
(A,B) == (C,B)

歐幾里德演算法
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證
歐幾里德演算法就是根據這個原理來做的，其演算法用C++語言描述為：
void swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}

模P乘法逆元
對於整數a、p，如果存在整數b，滿足ab mod p =1，則說，b是a的模p乘法逆元。

定理：a存在模p的乘法逆元的充要條件是gcd(a,p) = 1

證明：
首先證明充分性
如果gcd(a,p) = 1，根據歐拉定理，aφ(p) ≡ 1 mod p，因此
顯然aφ(p)-1 mod p是a的模p乘法逆元。

再證明必要性
假設存在a模p的乘法逆元為b
ab ≡ 1 mod p
則ab = kp +1 ，所以1 = ab - kp
因為gcd(a,p) = d
所以d | 1
所以d只能為1

擴展歐幾里德演算法
擴展歐幾里德演算法不但能計算(a,b)的最大公約數，而且能計算a模b及b模a的乘法逆元，用C語言描述如下：

int gcd(int a, int b , int& ar,int & br)
{
int x1,x2,x3;
int y1,y2,y3;
int t1,t2,t3;
if(0 == a)
{//有一個數為0，就不存在乘法逆元
ar = 0;
br = 0 ;
return b;
}
if(0 == b)
{
ar = 0;
br = 0 ;
return a;
}
x1 = 1;
x2 = 0;
x3 = a;
y1 = 0;
y2 = 1;
y3 = b;
int k;
for( t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3)
{
k = x3 / y3;
t2 = x2 - k * y2;
t1 = x1 - k * y1;
x1 = y1;
x1 = y2;
x3 = y3;
y1 = t1;
y2 = t2;
y3 = t3;
}
if( y3 == 1)
{
//有乘法逆元
ar = y2;
br = x1;
return 1;
}else{
//公約數不為1，無乘法逆元
ar = 0;
br = 0;
return y3;
}
}

擴展歐幾里德演算法對於最大公約數的計算和普通歐幾里德演算法是一致的。計算乘法逆元則顯得很難明白。我想了半個小時才想出證明他的方法。

首先重復拙作整除中的一個論斷：

如果gcd(a,b)=d，則存在m,n，使得d = ma + nb，稱呼這種關系為a、b組合整數d，m，n稱為組合系數。當d=1時，有 ma + nb = 1 ，此時可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。

為了證明上面的結論，我們把上述計算中xi、yi看成ti的迭代初始值，考察一組數(t1,t2,t3)，用歸納法證明：當通過擴展歐幾里德演算法計算後，每一行都滿足a×t1 + b×t2 = t3

第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假設前k行都成立，考察第k+1行
對於k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分別滿足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根據擴展歐幾里德演算法，假設t3(k-1) = j t3(k) + r
則：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
則
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得證
因此，當最終t3迭代計算到1時，有t1× a + t2 × b = 1，顯然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。

參考資料：
http://ke..com/view/795549.htm

⑽ DBSCAN原理是怎麼樣的

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚類演算法，它是一種基於高密度連通區域的、基於密度的聚類演算法，能夠將具有足夠高密度的區域劃分為簇，並在具有雜訊的數據中發現任意形狀的簇。我們總結一下DBSCAN聚類演算法原理的基本要點：
DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里德距離來進行度量。
DBSCAN演算法需要用戶輸入2個參數：一個參數是半徑（Eps），表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量（MinPts）。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點。
DBSCAN聚類使用到一個k-距離的概念，k-距離是指：給定數據集P={p(i); i=0,1,…n}，對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有點之間的距離，距離按照從小到大的順序排序，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，則d(k)就被稱為k-距離。也就是說，k-距離是點p(i)到所有點（除了p(i)點）之間距離第k近的距離。對待聚類集合中每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)}。
根據經驗計算半徑Eps：根據得到的所有點的k-距離集合E，對集合E進行升序排序後得到k-距離集合E』，需要擬合一條排序後的E』集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察，將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值。
根據經驗計算最少點的數量MinPts：確定MinPts的大小，實際上也是確定k-距離中k的值，DBSCAN演算法取k=4，則MinPts=4。
另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變，Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致已一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為雜訊點，MinPts過小，會導致發現大量的核心點。
DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。對於演算法的實現，首先我們概要地描述一下實現的過程：
1）解析樣本數據文件。
2）計算每個點與其他所有點之間的歐幾里德距離。
3）計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。
4）將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢。
5）根據散點圖確定半徑Eps的值。）根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與到核心點距離小於半徑Eps的點的映射。
6）根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，得到雜訊點。
7）將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。
8）選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其雜訊點，使用散點圖對比聚類效果。