Clustering

同聲相應,同氣相求;水流濕,火就燥,雲從龍,風從虎。《易傳》

Clustering

「分群」。所有數據進行分組,相似數據歸類於同一組,一筆數據只屬於某一組,每一組稱作一個「群集Cluster」。

如何定義所謂的相似呢?方法很多:距離越近,推定為越相似;鄰居越密集,推定為越相似。

分群演算法的基本原理,一類是近朱者赤、近墨者黑,不斷將數據重新分組;另一類是不斷切割群集,表示成樹狀圖。

演算法(K-Means Clustering)(Lloyd-Max Algorithm)

http://etrex.blogspot.tw/2008/05/k-mean-clustering.html

一、群集數量推定為K,隨機散佈K個點作為群集中心(常用既有的點)。

二、每一點分類到距離最近的群集中心(常用直線距離)。

三、重新計算每一個群集中心(常用平均值)。

重複二與三,直到群集不變、群集中心不動為止。最後形成群集中心的Voronoi Diagram。

時間複雜度為O(NKT),N是數據數量,K是群集數量,T是重複次數。我們無法預先得知群集數量、重複次數。數據分布情況、群集中心的初始位置,都會影響重複次數,運氣成份很大。

缺點是群集不能重疊、群集分界不能是曲線和折線、極端數據容易使群集中心偏移、一開始難以決定群集數量與群集中心、數據分布呈甜甜圈時群集中心可能永不停住。

演算法(K-Means++ Clustering)

https://mycourses.aalto.fi/mod/resource/view.php?id=153957

改良K-Means Clustering第一個步驟。

逐一設定K個群集中心。計算每一個點到已設定的群集中心的最短距離,以最短距離的n次方做為機率大小,決定下一個群集中心。距離越遠,機率越大。

0次方等同隨機散佈,K-Means。2次方是K-Means++。∞次方等同找最遠點,Farthest-point Traversal,效果最好。

優點是群集中心比較分散,不容易擠在一起。

演算法(Linde-Buzo-Gray Clustering)

首先隨機設定一個群集中心(常用平均值)。不斷讓群集中心往反方向分裂成兩倍數量(常用少量移動、群集內最遠點對),並且重新實施K-Means Clustering。

優點是不用煩惱群集中心的初始位置。

演算法(EM Clustering)(Gaussian Mixture Model)

假設每個群集各是一個常態分布,平均數、變異數可以相異。

首先設定群集數量(常態分布數量)。然後將所有常態分布融合成一個分布,實施估計,估計方式採用Maximum Likelihood,演算法採用EM Algorithm。名稱是這樣來的。

融合數個常態分布成為一個分布,即Gaussian Mixture Model,替每個常態分布設定不同比重。

優點是考慮了群集尺寸與疏密。

演算法(K-Nearest Neighbor Clustering)

每一點各自找到距離最近的K個點作為鄰居,採多數決歸類到群集。如果距離超過了自訂臨界值,找不足K個鄰居,就替該點創造一個新的群集。

優點是不用煩惱群集數量,缺點是群集鬆散。

演算法(Jarvis-Patrick Clustering)

每一點各自找到距離最近的K個點做為鄰居。當a和b彼此都是鄰居,或者a和b至少有K'個相同鄰居(K'是自訂臨界值,K' ≤ K),則a和b歸類到同一個群集。

優點是不用煩惱群集數量、群集形狀。

演算法(DBSCAN)

https://en.wikipedia.org/wiki/DBSCAN

演算法(Nearest Neighbor Chain)

https://en.wikipedia.org/wiki/Nearest-neighbor_chain_algorithm

演算法(Minimum Spanning Tree)

運用「Minimum Spanning Tree」的瓶頸性質。實施Kruskal's Algorithm,每次新添的邊,若距離不超過threshold,則邊的兩端就視作同一個群集。

演算法(Minimum Cut Tree)

運用「Minimum Cut Tree」的瓶頸性質。然而最小割是距離最近而不是距離最遠,無法用於分離群集,所以就把一個割的權重修改為:

 ∑ w(i, j) ÷ min(|S|, |S|)
i∈S
j∈S

詳情請讀者請自行上網搜尋資料。

Classification

師曠之聰,不以六律,不能正五音。《孟子》

Classification

分群:未知群集(類別),找到群集(類別)。某些演算法會順便找到分界線,例如K-Means Clustering。

分類:已知群集(類別),找到分界線。

群聚與隔離,一體兩面。相似數據群聚,相異數據也漸漸隔離。最後出現了群聚中心,也出現了隔離界線。

不同類別的數據稍微黏在一起,仍然可以找到大致的分界線。如果不同類別的數據幾乎混在一起(例如太極圖案),那麼分界線沒有任何意義。

找到分界線之後,對於一筆新的數據,就利用分界線來決定其類別──這就是Classification的用途。

如何應用Classification?

Classification應用十分廣泛,是世上最實用的演算法之一。

比如說,讓電腦揀土豆。一粒土豆是一筆數據,(土豆重量,土豆顏色)是其數值。

首先,取一百粒土豆,個別以儀器測量其數值,然後人工進行分類,分為良與劣兩類。這些數據全數輸入到電腦當中。

接著,利用任何一種Classification的演算法,找到良與劣的分界線。

最後,每一粒新產的土豆,以儀器自動測量其數值,再用演算法判斷數值在分界線的哪一側,就能判斷出土豆的良劣了。

應用Classification需要考量的關鍵點

這整套自動辨識的流程當中,我們需要考量的有:

一、我們要挑選哪些特徵?例如重量、顏色、形狀等等。

二、我們要如何將特徵化為數值?例如用磅秤得到重量數值,用攝影機得到顏色數值,用影像處理演算法得到形狀數值。

三、我們要取哪些土豆當作樣本?這跟統計學有關。

四、我們如何提升分類的正確率?這跟統計學有關。

五、我們如何從分界線當中發現新的性質?例如重量越重則土豆越優、形狀越圓則土豆越優之類的。

Error

Fitting:間距平方和盡量小。Clustering:最大間距盡量小。Classification:最小間距盡量大。三者都是針對間距進行Optimization。

Point-set Function【尚無專有名詞】

Fitting、Clustering、Classification可以視作「點集合函數」最佳化。函數輸入是一個點集合,代表數據們;函數輸出是一個數值,代表誤差。

後面章節的演算法們,雖然掛名為Classification演算法,但是本質都是「點集合函數最佳化演算法」。更換一下誤差函數,即可解決Fitting、Clustering、Classification,甚至其他問題。

注意到,凸函數最佳化,有著高速演算法,有著唯一的極值。我們往往把誤差函數設計成凸函數。

點到點距離、點到直線距離,恰是凸函數。凸函數的平方,仍是凸函數。多個凸函數相加、取最大值,仍是凸函數。

Linear Classification

Linear Classification

以直線當作分界線。

數據的維度可以推廣到三維以上,此時分界線就成了分界面、分界體等等。分界物是數據維度減少一維(hyperplane)。

雖然可以視作計算幾何問題,但是當維度太高的時候,計算相當複雜,難以快速求得精確解。因此採用了數值方法的套路。

演算法(Perceptron)

不考慮分界線到數據的距離。分界線只要分開數據即可。

分界線是一條直線ax+by+c=0。想判斷一筆數據(x₁,y₁)位於分界線的哪一側,就將(x₁,y₁)代入到直線方程式,計算ax₁+by₁+c,如果大於零就是在正側,小於零就是在反側,等於零就是在分界線上。

每一筆數據都代入計算,不見得都能正確分類。我們必須調整分界線的位置,也就是調整a b c三個參數。該如何調整才好呢?我們可以利用最佳化的思維。

設定誤差是「正確結果、分類結果不相符的數據筆數」,誤差越小越好。為了方便統計誤差,將結果定為數值0和1。正確結果:數據共兩類,第一類數據定為0,第二類數據定為1。分類結果:數據在反側定為0,數據在分界線上、在正側定為1。

如此一來,統計誤差,只需數值運算、無需邏輯運算。正確結果和分類結果先相減再平方,等於0即相符,等於1即不相符。

0和1顛倒設定也沒關係,a b c的計算結果多了負號而已。

 N                     2
 ∑  [gᵢ - u(axᵢ+byᵢ+c)]
i=1

gᵢ          :  correct   result of data i (0 or 1)
u(axᵢ+byᵢ+c): classified result of data i (0 or 1)
u           : unit step function          (0 or 1)

最佳化演算法採用Gradient Descent:往梯度最陡的方向逐步移動。首先推導梯度,也就是分別對a b c三個變數進行偏微分:

∂   N                     2
――  ∑  [gᵢ - u(axᵢ+byᵢ+c)]  =  ∑ [gᵢ - u(axᵢ+byᵢ+c)] ⋅ -2xᵢ
∂a i=1
                            =  ∑ errorᵢ ⋅ -2xᵢ

∂   N                     2
――  ∑  [gᵢ - u(axᵢ+byᵢ+c)]  =  ∑ [gᵢ - u(axᵢ+byᵢ+c)] ⋅ -2yᵢ
∂b i=1
                            =  ∑ errorᵢ ⋅ -2yᵢ

∂   N                     2
――  ∑  [gᵢ - u(axᵢ+byᵢ+c)]  =  ∑ [gᵢ - u(axᵢ+byᵢ+c)] ⋅ -2
∂c i=1
                            =  ∑ errorᵢ ⋅ -2

一開始a b c設定成任意值。a b c不斷往梯度最陡的方向移動一段距離,朝最小值前進:

     [ 0 ]
w0 = [ 0 ]  一開始a b c設定成任意值
     [ 0 ]
                 [ ∑ errorᵢ ⋅ -2xᵢ ]               [ ∑ errorᵢ ⋅ xᵢ ]
wt+1 = wt - rate [ ∑ errorᵢ ⋅ -2yᵢ ] = wt + 2 rate [ ∑ errorᵢ ⋅ yᵢ ]
                 [ ∑ errorᵢ ⋅ -2   ]               [ ∑ errorᵢ      ]

通常會把2併入rate。或者一開始設定誤差函數多乘一個1/2,來把2消掉。

推廣成online演算法,依序處理每一筆數據,一次一筆。

                   [ errorᵢ ⋅ xᵢ ]
wt+1 = wt + 2 rate [ errorᵢ ⋅ yᵢ ]
                   [ errorᵢ      ]

通常會把2併入rate。或者一開始設定誤差函數多乘一個1/2,來把2消掉。

公式非常簡潔!這就是為什麼使用這種誤差設定方式、使用Gradient Descent的原因。這是前人努力試驗出來的最簡潔的方式。

當數據可分為兩半,則誤差呈單峰函數,Gradient Descent不會卡在區域極值。證明方式是逐次加入一筆數據。【尚待確認】

換句話說,當數據可分為兩半,而且rate適中(太小導致攤在山腰、太大導致越過山頂),則此演算法一定可以找到正確的分界線。當數據不可分為兩半,則此演算法毫無用武之地。

「一筆數據代入直線方程式」這件事,通常畫成理工味道十足的圖。這個東西有個古怪名稱叫做perceptron:

所有輸入乘上權重、相加起來,經過unit step function,最後輸出0或1(也有人輸出+1或-1)。

函數不一定得是unit step function。有些時候需要輸出實數,就可以改成sigmoid function。

UVa 11289 ICPC 3581

演算法(Support Vector Machine)

考慮分界線到數據的距離。分界線位於正中央,兩類數據相隔越遠越好。準確來說,分界線到兩類數據的最短距離均等、最短距離越大越好。

舉例來說,二維的情況下,兩類數據各自求凸包,分界線是凸包之間最近點對的中垂線,或者分界線平行於凸包上某一條邊。

但是當維度太高的時候,難以計算凸包、中垂超平面。只好採用數值方法的套路。

分界線是一條直線ax+by+c=0。想計算一筆數據(x₁,y₁)到分界線的距離,就將(x₁,y₁)代入到點與直線距離公式,計算(ax₁+by₁+c) / sqrt(a²+b²)。距離有正負號,如果大於零就是在正側,小於零就是在反側,等於零就是在分界線上。

間距線是兩條直線ax+by+c=1和ax+by+c=-1(已將截距縮放為1)。想計算間距線到分界線的距離,就將間距線上任意一點代入到點與直線距離公式(顯然分子是1和-1)。如此便得到半個間距。

每一筆數據到分界線的距離,都必須大於等於半個間距。而且每一筆數據都要選對邊。

當數據可分為兩半,採用regularization:最大化間距,限制是全部數據都分對。

為了方便判斷距離,數據標記為-1和+1(本應是0和1)。為了避免除以零,改為最小化間距的倒數(本應是負數)。為了方便最佳化,再取平方變成凸函數。

                                                             s
classifer: px+qy+r=0   margin: px+qy+r=±s   half-width: ――――――――――― 
                                                        sqrt(p²+q²)

let a = p/s, b = q/s, c = r/s, remove variable s.

                                                             1
classifer: ax+by+c=0   margin: ax+by+c=±1   half-width: ――――――――――― 
                                                        sqrt(a²+b²)

         1                      axᵢ+byᵢ+c         1
max ―――――――――――   subject to { ――――――――――― ≥ ――――――――――― ⋅ gᵢ } for all i
    sqrt(a²+b²)                sqrt(a²+b²)   sqrt(a²+b²)

         1
max ―――――――――――   subject to { axᵢ+byᵢ+c ≥ gᵢ } for all i
    sqrt(a²+b²)

min sqrt(a²+b²)   subject to { axᵢ+byᵢ+c ≥ gᵢ } for all i

min   (a²+b²)     subject to { axᵢ+byᵢ+c ≥ gᵢ } for all i

min   (a²+b²)     + ∑ αᵢ [ (axᵢ+byᵢ+c) - gᵢ ]   (αᵢ ≥ 0)

針對此誤差式子的最佳化演算法是Sequential Minimal Optimization,請讀者自行查詢。

Inlier / Outlier

真實世界的數據並非完美,常有例外。

無彈性的定義:全部數據分為inlier和outlier;inlier是分對的數據,outlier 是分錯的數據。

有彈性的定義:全部數據分為inlier和outlier;inlier是距離分界線太近的數據、以及分對的數據,outlier是距離分界線太遠又分錯的數據。

順帶一提,當數據無法分兩半,常見的手法是:無視彈性範圍內的數據,並且限制其數量上限。可以透過regularization處理。

演算法(AdaBoost)(Adaptive Boosting)

實施分類演算法,分錯的數據,複製並增加其數量,再繼續實施分類演算法。這使得誤差大幅增加,使得分界線大幅靠近分錯的數據,進而迅速減少分錯的數據。

增加倍率:分對的數量除以分錯的數量。數量不必是整數。

AdaBoost好處多多。分類過程中,分界線的移動步伐變大了,提早找到正確分界線。分類結束後,每筆數據的數量,可以看成是出錯程度,可依此判斷outlier。分類結束後,如果數據無法正確分兩半,就以各回合的分界線的平均,推定是最理想的分界線。

AdaBoost儘管缺乏理論根據,儘管名字怪異,卻非常實用。

演算法(Gradient Boosting)

實施分類演算法,得到分界線。然後不斷微調分界線。

挑出分錯的數據,另外實施分類演算法,得到微調用的分界線。當前分界線,加上微調用的分界線,完成一次微調。重複這些步驟,直到分錯的數據足夠少,或者是誤差總和足夠小。

微調用的分界線,可以乘上倍率。注意到倍率太大就不是微調了,而倍率太小就失去調整效果了。

概念宛如Gradient Descent,故取名Gradient。概念宛如Adaptive Boosting,故取名Boosting。

Polynomial Classification

Polynomial Classification

以多項式曲線、多項式曲面當作分界線。

根據工程師的實驗,稍後介紹的歪招Representation,效果更好──儘管至今沒有嚴謹的數學證明。因此這裡就不介紹分界線是曲線的情況了。

Representation(Feature Map)

classifier center = (24,22) radius = 10, #(data) = 13 + 7 = 21 p = {{17,8},{21,8},{27,8},{33,10},{37,15},{39,22},{36,30},{30,35},{21,35},{12,32},{12,28},{7,22},{10,14},{18,15},{24,16},{28,18},{16,19},{18,24},{24,23},{31,25},{27,29}}; f[x_] := (x-24)*(x-24); g[y_] := (y-22)*(y-22); h[x_,y_] := Sqrt[2]*(x-24)*(y-22); q = Transpose[{ f[ p[[All,1]] ], g[ p[[All,2]] ], Apply[h, p, {1}] }]; ListPointPlot3D[{q[[1;;13]], q[[14;;21]]}, BoxRatios -> {1,1,1}, PlotStyle -> PointSize[Large]] c = Classify[q -> {"A","A","A","A","A","A","A","A","A","A","A","A","A","B","B","B","B","B","B","B","B"}, "Decision", Method->"SupportVectorMachine"];

http://cseweb.ucsd.edu/classes/sp13/cse151-a/Kernels.pdf

先變換、再分類。數據套用變換函數重新呈現,然後尋找分界線。讓新數據的分界線是直線,而原數據的分界線是曲線。

函數決定曲線造型。但是如何挑選函數呢?首先你要學會通靈。

點與直線距離,時間複雜度從O(D)變成O(D'),D是原數據的維度,D'是新數據的維度。

Kernel

http://www.robots.ox.ac.uk/~az/lectures/ml/

分類演算法,每回合都要重新累計誤差總和:每筆數據先套用變換函數、再計算點與直線距離。

兩個步驟,有點煩。有個投機取巧方式稱作kernel trick:不設計變換函數、不推導距離,而是改為設計「數據重新呈現之後的距離函數kernel」。關於距離函數,請見本站文件「Metric」。

分界線的參數a b c,其中a b可以表示成新數據的加權平均值(新數據根據其類別額外乘上+1或-1)。點與直線距離,其中一部分變成了新數據與新數據的點積,即是kernel。

點與直線距離,運用kernel,只需原數據、無需新數據,時間複雜度為O(ND),D是原數據的維度。當原維度遠小於新維度,kernel trick就有好處,可以很快算好誤差總和。

Underfitting / Overfitting

用單純的函數去區分複雜的數據們,顯然分類的不太完美。

用複雜的函數去區分單純的數據們,顯然事情被搞複雜了。

如果我們不清楚數據的性質,也就無法抉擇函數了。那麼,該如何了解數據的性質呢?這屬於宗教信仰的範疇,就此打住。

Hierarchical Classification

Hierarchical Classification

數據往往無法順利地一分為二,數據往往有兩種以上類別,先前的演算法往往毫無用武之地。

解法是階層架構、樹狀圖,稱作「決策樹Decision Tree」。

另一種解法是一連串測試,稱作「蕨Fern」。奇葩的名稱。蕨是決策樹的簡易版本:同一層節點,共用同一條分界線。

演算法(Decision Tree)(Classification Tree)

援引「k-Dimensional Tree」的精神,用於分類。

貪心法。選擇分類效果最好的分界線,將數據分兩份。兩份數據分頭遞迴下去,直到不同類別的數據都被分開為止。

每次選擇分界線時,窮舉各種分界線走向(窮舉每個維度),窮舉各種分界線位置(窮舉每筆數據),從中找到分類效果最好者。

分界線兩側的數據,分頭計算混亂程度。兩個混亂程度,求加權平均值(權重是數據數量),做為分類效果。數值越低,效果越好。

混亂程度有兩種評估方式:一、Gini impurity:各個類別的數據比例,兩兩相乘(不乘自身),總和越小越好;二、information gain:各個類別的數據比例,求熵,總和越小越好。

兩種方式都沒有科學根據。通常使用第一種,比較好算。

不採用清澈程度、卻採用混亂程度,這般迂迴曲折,是因為清澈程度不好揣摩、而混亂程度容易具體實現。

Gini impurity:  ∑ [ p(Ci) p(Cj) ] = 1 - ∑ [ p(Ci) p(Ci) ]
               i≠j                      i

information gain: - ∑ [ p(Ci) log₂ p(Ci) ]
                    i

  Ci :第i種類別的數據集合。
p(Ci):第i種類別的數據數量,除以所有類別的數據總數量。也就是比例。

因為是貪心法,所以分界線配置往往不是最精簡的、分界線數量往往不是最少的。

時間複雜度為O(DNNN)。運用「掃描線」為O(DNNlogN)。當運氣很好,數據的數量每次都剛好對半分,為O(DN(logN)²)。

一、窮舉D個維度、窮舉N筆數據,找到分界線。
二、針對一條分界線,判斷每筆數據位於哪一側,需時O(N)。
三、兩側數據,分頭計算C種類別之間的混亂程度,需時O(C)。C通常視作常數。
四、分界線數量最少0條(數據只有唯一一種類別)。
  分界線數量最多N-1條(每次都分出一筆數據)。
  分界線數量就是節點數量。

預先設置一些分界線,每次找分界線時,就考慮這些分界線。如此一來,分界線就不必是鉛直線、水平線,分界線可以是任意圖形。甚至多條分界線可以合成一種分界線。

當數據有兩種以上類別,先運用Linear Classification,兩兩之間求分界線;再運用Hierarchical Classification,選取適當的分界線,建立階層架構。

演算法(Random Forest)

選擇分界線時,改為隨機窮舉一小部分,可以省時。

接著,製造大量的樹,刪除相似的樹。多數決。就這樣子。

隨機的副作用是分不乾淨。不過為了避免overfitting,也就沒必要分乾淨。而多數決不但抑制了副作用,同時也改良了分界線。

演算法(Random Ferns)

樹改成蕨。可以省時。可以省程式碼。

Bayesian Classification(Under Construction!)

Bayesian Classification

迄今都是假定一筆數據只有唯一一種類別。

現在推廣成一筆數據有多種類別,類別是「浮動數字(隨機變數)」,每種類別的機率高低都不同。

對調主角與配角,切換視角,一種類別也就有多筆數據,數據是浮動數字,每種數據的機率高低都不同。

貝式定理可以用來切換視角。

Linear Discriminative Analysis

援引「Principal Component Analysis」的精神,用於分類。

尋找一組新座標軸,讓數據投影到座標軸之後,各類數據的平均值的變異數盡量大(異類盡量散開),各類數據各自的變異數盡量小(同類盡量聚集)。

個人推測kernel trick (representer theorem)、spectral transform、Ax² optimization有著某種關聯。數據有了類別。

Neighborhood Component Analysis

援引「Principal Component Analysis」的精神,用於分類。

找到一個轉換矩陣,讓新數據同類相聚。統計同類數據之間的兩兩距離總和,令距離越近越好。距離定義成有向距離:相離最近的K個鄰居所構成的softmax函數的平方。因為難以預測新數據的鄰居關係,所以姑且採用原數據的鄰居關係。

https://en.wikipedia.org/wiki/Neighbourhood_components_analysis