雜貨店-聚類方法綜述

譜聚給你博客園上若干個博客，讓你將它們分成K類，你會怎樣做？想必有很多方法，本文要聚類的直觀解釋是根據(jù)樣本間相似度，將它們分成不同組。譜聚類的思想是將樣本看作頂接不同組的邊的權(quán)重盡可能低（這意味著組間相似度要盡可能低（這意味著組內(nèi)相似度要盡可能高如下圖所示：在上圖中，一共有6個頂點(diǎn)（博客），頂點(diǎn)之間的連線表示兩個頂點(diǎn)的相似度，現(xiàn)在要將這圖分成兩半（兩個類（去掉哪邊條？根據(jù)譜聚類的思想，應(yīng)該去掉的邊是用虛線表示的那條。最后，剩下的兩半就分別對應(yīng)兩個類了。根據(jù)這個思想，可以得到unnormalized譜聚類和normalized譜聚類，由于前者比后者簡單，所以本文介紹unnormalized譜聚類的幾個步驟（假設(shè)要分K個類）：unnormalizedgraphLaplacianmatrixL(LDW,Ddegree計(jì)算L的前K把這k個特征向量排列在一起組成一個N*k的矩陣，將其中每一行看作k中的一個向量，并使用K-means算法進(jìn)行聚類這一節(jié)主要從大體上解unnormalized譜聚類的四個步驟是怎么來的，不涉及具體的公譜聚類的思想就是要轉(zhuǎn)化為圖分割問題。因此，第一步就是將原問題轉(zhuǎn)化為圖。轉(zhuǎn)為圖有兩個問題要解決：一是兩個頂點(diǎn)的邊要怎樣定義；二是要保留哪些邊。對于第一個問題，如果兩個點(diǎn)在一定程度上相似，就在兩個點(diǎn)之間添加一條邊。相似的過常用的Gaussiansimilarityfunction法是建立k-nearestneighborgraph。在這種圖中，每個頂點(diǎn)只與K個相似度最高的點(diǎn)連邊。unnormalizedgraphLaplacianmatrix(L表示)有很多很好的性質(zhì)，也正是這個這一組性質(zhì)將在之后的公式推導(dǎo)中起到?jīng)Q定性作用將原問題轉(zhuǎn)化為圖后，接下來的工作就是決定怎樣分。圖分割問題實(shí)際上就是最小割問題(mincutpoblem)。最小割問題可定義為最小化以下目標(biāo)函數(shù)：其中k表示分成k個組，Ai表示第i個組，表示第Ai的補(bǔ)集，W(A,B)表示第A組與第組之間的所有邊的權(quán)重之和這個式子的直觀意義：如果要分成K個組，那么其代價就是進(jìn)行分割時去掉的邊的權(quán)重的總和?？上У氖侵苯幼钚』@式子通常會導(dǎo)致不好的分割。以分成2類為例，這個式子通常會將圖分成這樣的兩類：一個點(diǎn)為一類，剩下的所有點(diǎn)為另一類。顯然，這樣的分割是很不好的。因?yàn)槲覀兤谕總€類都有合理的大小。所以，要對這個式子進(jìn)行改進(jìn)，改進(jìn)后的公式（稱為RatioCut)如下其中|A|表示A組中包含的頂點(diǎn)數(shù)目在RatioCut中，如果某一組包含的頂點(diǎn)數(shù)越少，那么它的值就越大。在一個最小化問題中，這相當(dāng)于是懲罰，也就是不鼓勵將組分得太小?，F(xiàn)在只要將最小化RatioCut解出來，分割就完成了。不幸的是，這是個NP難問題。想要在多項(xiàng)式時間內(nèi)解出來，就要對這個問題作一個轉(zhuǎn)化了。在轉(zhuǎn)化的過程中，就用到上面提到的L的那一組性質(zhì)，經(jīng)過若干推導(dǎo)，最后可以得到這樣的一個其中H是一個矩陣，它的元素的定義(Eq.(5))如果H矩陣的元素不為0，則說明第i個點(diǎn)屬于第j個類。也就是說，只要得到H矩陣，就能知道要怎樣分?？上У氖?，這個問題仍然是NP難問題。但是，如果我們讓H矩根據(jù)Rayleigh-Ritztheorem，這個問題的解是L的前k個最小的特征向量組成的矩陣H，其中特征向量是按列來排H的每一列，均為一個特征向量。在第三步中，我們?yōu)榱怂神YNP難問題，讓H矩陣取任意值，因此，解出來的H矩陣不再具有原來的性質(zhì)——元素值能哪個點(diǎn)屬于哪一類。盡管如此，對于k-means來說，將H矩k-meansH矩陣進(jìn)行聚類作為譜以下是unnormalied譜聚類的 版實(shí)現(xiàn)（博客園的代碼格式選擇中居然沒有的。。。這里選個C++的）：functionfunction[C,L,D,Q,V]=SpectralClustering(W,%spectralclustering%input:adjacencymatrixW;numberofcluster%%return:clusterindicatorvectorsascolumnsinC;unnormalizedLaplacianL;degreematrixD; eigenvectorsmatrixQ;eigenvaluesmatrix%calculatedegreematrixdegs=sum(W,2);D=sparse(1:size(W,1),1:size(W,2),%computeunnormalizedLaplacianL=D-W;%computetheeigenvectorscorrespondingtotheksmallest%diagonalmatrixVisNcutL'sksmallestmagnitude%matrixQwhosecolumnsarethecorrespondingeigenvectors.[Q,V]=eigs(L,k,'SA');%usethek-meansalgorithmtoclusterVrow-%Cwillbean-by-1matrixcontainingtheclusternumberforeachdatapointC=kmeans(Q,k);%convertCtoan-by-kmatrixcontainingthekindicatorvectorsascolumnsC=sparse(1:size(D,1),C,1);[1]ATutorialonSpectralClustering[2]ClusteringClustering1k-本文是“漫談Clustering系列”中的第1篇，參列的其他文章。好久沒有寫blog了，一來是blog下線一段時間，而租DreamHost的事情又Learning相關(guān)的東西，因?yàn)楹芏鄸|西都不懂，所以平時也找一些資料來看。按Clustering中文翻譯作“聚類”，簡單地說就是把相似的東西分到一組，同Classification(分類)不同，對于一個classifier，通常需要你告訴它“這classifier練數(shù)據(jù)的過程通常叫做supervisedlearning(監(jiān)督學(xué)習(xí))，而在聚類的時候，因此，一個聚類算法通常只需要知道如何計(jì)算相似度就可以開始工作了，因此clustering通常并不需要使用訓(xùn)練數(shù)據(jù)進(jìn)行學(xué)習(xí)，這在MachineLearning中被稱作unsupervisedlearning(無監(jiān)督學(xué)習(xí))。映射到一個單獨(dú)的特征之外，一種常見的做法是同時提取N種特征，將它們放NNclustering大致看出來”，不過，對于這樣的N維歐氏空間中的點(diǎn)進(jìn)行聚類，有一個非常k-meansk-meansclustercenter)cluster所有的點(diǎn)到該中心點(diǎn)的距離小于到其他cluster的中心的距離。雖然實(shí)際情況情況是2，通常我們會將它歸類為左邊的那個分布，因?yàn)楦怕蚀笠恍?，然而此分性，無法避免。因此，k-means所依賴的這個假設(shè)看作是合理的。有N個數(shù)據(jù)點(diǎn)需要分為K個cluster，k-means要做的就是最小化 在數(shù)據(jù)點(diǎn)n被歸類到clusterk的時候?yàn)?，否則0。直接尋找 和來最小化 代的辦法：先固定，選擇最優(yōu)的 的。將 對求導(dǎo)并令導(dǎo)數(shù)等于零，很容易得到 候應(yīng)該滿足：亦即的值應(yīng)當(dāng)是所有clusterk中的數(shù)據(jù)點(diǎn)的平均值。由于每一次迭代都是取到的最小值，因此只會不斷地減?。ɑ蛘卟蛔儯?，而不會增加，k-meansk-means到全局最優(yōu)解，但是對于這樣的問題，像k-meansk-means選定K個中心的初值。這個過程通常是針對具體的問題有一些啟發(fā)式的，或者大多數(shù)情況下采用隨機(jī)選取的辦法。因?yàn)榍懊鎘-means并以有時候我們會多次選取初值跑k-means，并取其中最好的一次結(jié)果。cluster按照這個步驟寫一個k-means實(shí)現(xiàn)其實(shí)相當(dāng)容易了，在SciPy或者k-meansk-means123456789123456789fromfuture importcPickleaspicklefrommatplotlibimportfromnumpyimportzeros,array,tilefromscipy.linalgimportnormimportnumpy.matlibasmldefkmeans(X,k,observer=None,threshold=1e-15,maxiter=300):N=len(X)labels=zeros(N,centers=array(random.sample(X,k))iter=0defsum=foriinreturndefdistmat(X,Y):n=len(X)m=xx=ml.sum(X*X,axis=1)yy=ml.sum(Y*Y,axis=1)xy=ml.dot(X,Y.T)returntile(xx,(m,1)).T+tile(yy,(n,1))-Jprev=calc_J()whileTrue:#notifytheifobserverisnotNone:#calculatedistancefromxtoeach#distance_matrixisonlyavailableinscipynewerthan0.7#dist=distance_matrix(X,centers)dist=distmat(X,centers)#assignxtonearst#re-calculateeachcenterforjinrange(k):idx_j=(labels==j).nonzero()iter+=1ifJprev-J<threshold:Jprev=#finalifobserverisnotNone:if =='main#loadpreviouslygeneratedpointswithopen('cluster.pkl')asinf:samples=N=forsmpinX=zeros((N,2))idxfrm=0foriinidxto=idxfrm+len(samples[i][0])X[idxfrm:idxto,0]=samples[i][0]X[idxfrm:idxto,1]=samples[i][1]idxfrm=idxtodefobserver(iter,labels,centers):print"iter%d."%itercolors=array([[1,0,0],[0,1,0],[0,0, #clearpreviousplot#drawdata_colors=[colors[lbl]forlblinpyplot.scatter(X[:,0],X[:,1],c=data_colors,alpha=0.5)#drawcenterskmeans(X,3,代碼有些長，不過因?yàn)橛肞ython來做這個事情確實(shí)不如方便，實(shí)際的k-means的代碼只是4147341到4345473個中心點(diǎn)，結(jié)果不過正如前面所說的那樣k-meansk-means都還是很令人滿意的，算是一種簡單高效應(yīng)用廣泛的clustering方法。Update2010.04.25:很多人都問我要cluster.pkl，脆把它上傳上來吧，其實(shí)是很容易自己生成的，點(diǎn)擊這里。漫談Clustering(2):k-me本文是“漫談Clustering系列”中的第2篇，參見本系列的其clusteringk-means事實(shí)也確實(shí)如此，k-meds可以算是k-means的一個變種。將中心點(diǎn)取為當(dāng)前cluster中所有數(shù)據(jù)點(diǎn)的平均值：Rough并且我們已經(jīng)證明在固定了各個數(shù)據(jù)點(diǎn)的assignment的情況下這樣選取的中 最小化。然而在k-meds中，中心點(diǎn)的選取限制在當(dāng)前cluster所包含的數(shù)據(jù)點(diǎn)的集合中。換句話說，在k-meds算法中，從當(dāng)前cluster中選取這樣一個點(diǎn)——它到其他所有（當(dāng)前cluster中的）點(diǎn)的距離之和最小——作為中心點(diǎn)。k-means和k-meds之間的差異就類似于一個數(shù)據(jù)樣本的均值(mean)和中位數(shù)(median)之間的差k-means(dissimilarity)可以很自然地用這樣的方式來處理，但是類別(categorical)類型的特征就不組成的空間中進(jìn)行，k-means就為力了，因?yàn)闅W氏距離在里不能用了：一只Samoyed減去一只RoughCollie然后在平方一下？天知道那是什么！再加上一只GermanShepherdDog然后求一下平均值？根本沒法算，k-means在這里寸步難行！在k-meds中，我們把原來的目標(biāo)函數(shù)中的歐氏距離改為一個任意的dissimilaritymeasure函數(shù)最常見的方式是構(gòu)造一個dissimilaritymatrix 來代表，其中的元素表示第 只狗和第只狗之間的差異程度，例如，兩只Samoyed 之間的差異可以設(shè)為0，一只GermanShepherdDog和一只RoughCollie之間的差異是0.7，和一只MiniatureSchnauzer之間的差異是1，等等。除此之外，由于中心點(diǎn)是在已有的數(shù)據(jù)點(diǎn)里面選取的，因此相對于k-means來說，不容易受到那些由于誤差之類的原因產(chǎn)生的Outlier robust一些。forjinidx_j=(labels==j).nonzero()distsum=ml.sum(distj,axis=1)icenter=distsum.argmin()centers[j]=扯了這么forjinidx_j=(labels==j).nonzero()distsum=ml.sum(distj,axis=1)icenter=distsum.argmin()centers[j]=可以看到k-meds在這個例子上也能得到很好的結(jié)果k-meansk-meansk-meds復(fù)雜度陡然增加了許多：在k-means即可，而在k-meds中則需要枚舉每個點(diǎn)，并求出它到所有其他點(diǎn)的距離之和，復(fù)雜度為看完了直觀的例子，讓我們再來看一個稍微實(shí)際一點(diǎn)的例子好了：Clustering——那個永恒不變的，不過我們這里要做的聚類并不是針對文檔的而是針對文檔的語言實(shí)驗(yàn)數(shù)據(jù)是從Europarl 和Swedish這些語言的文本數(shù)據(jù)集。在N-gram-basedtextcategorization這篇paper中描述了一種計(jì)算由不同語言寫成的文檔的相似度的方法。一個（以字符為單位的）N-gram就相當(dāng)于長度為N的一系列連續(xù)子串。例如，由o產(chǎn)生的3-gram為：hel、ell和lloN-gram之前在開頭和末尾加上空格（這里用下劃線表示）：_he、hel、ell、llo、lo_和o。按照Zipf’slaw：Thenthmostcommonwordinahumanlanguagetextoccurswithafrequencyinverselyproportionalton.N-gramword國家的那些類英語的語言寫成的文檔，不論或長短，通常得出來的Profile要很長）文檔構(gòu)建出一個Profile，在拿到一篇未知文檔的時候，只要和各個Profile比較一下，差異最小的那個Profile所對應(yīng)的語言就可以認(rèn)定是這篇123456789123456789classdefinit(self,path,N=3,psize=400):self.N=Nself.psize=sepgrams={}withopen(path)asinf:forlineininf:fortokinself.sep.split(line):forninrange(self.N):#keeponlythetopmostpsizeitemsgrams=file=foriinrange(len(grams)):defgetitem(self,ifidxisNone:returnreturndis=0file.keys():returndeffeed_ngram(self,grams,tok,n):ifn!=0:tok='_'+toktok=tok+'_'*(n-1)foriinrange(len(tok)-n+1):gram=tok[i:i+n]grams[gram]+=europarl數(shù)據(jù)集共有11600我為這七千多個文檔建立了Profile并構(gòu)造出一個7038×7038的dissimilaritymatrix，最后在這上面用k-meds進(jìn)行聚類。構(gòu)造的，并且通常只要數(shù)次迭代就能收斂了。實(shí)際的k-meds實(shí)現(xiàn)可以在mltk 并不知道這些cluster應(yīng)該被打上什么，或者說，在這個問題里，包含了哪種語言的文檔。由于我們的目的是衡量聚類算法的performance，因此直接假定這一步能實(shí)現(xiàn)最優(yōu)的對應(yīng)關(guān)系，將每個cluster對應(yīng)到一種語言上去。一以用Hungarianalgorithm來求解。1111!=我們需要遍歷一次labellist，并數(shù)出真正的label（語言）與聚類得出的并求出accuracy只需要1毫秒的時間的話，總共也需要11個小時才能得到具體的算法了，感的同學(xué)可以參考Wikipedia，這里我直接使用了一個現(xiàn)有的Python實(shí)現(xiàn)。雖然這個實(shí)驗(yàn)非常折騰，不過最后的結(jié)果其實(shí)就是一個數(shù)字：accuracy我這里達(dá)到了88.97%，證明k-meds聚類和N-gramProfile識別語言這要版的scipy，munkres.py和mltk以及Python2.6。Clustering番外篇Vector本文是“漫談Clustering系列”中的第3篇，參見本系列的其Vectorzation。這項(xiàng)技術(shù)廣泛地用在信號處理以及數(shù)據(jù)壓縮等領(lǐng)域。事實(shí)上，在JPEG和MPEG-4等多壓縮格式里都有VQ這一步。Vectorzation這個名字聽起來有些玄乎，其實(shí)它本身并沒有這么高深。比如，[0,1)上的所有值變?yōu)?，[1,2)上的所有值變成1，如此類推。其這就是一個VQ的過程。一個比較正式一點(diǎn)的定義是：VQ是將一個向量空間中一個典型的例子就是圖像的編碼最簡單的情況考慮一個灰度 為黑色1為白色，每個像素的值為[0,1]上的一個實(shí)數(shù)?，F(xiàn)在要把它編碼為256階的灰階，一個最簡單的做法就是將每一個像素值x 數(shù)floor(x*255) 現(xiàn)在想要把壓縮這個，每個像素只使用4bit（而不是原來的8bit），因此，要將原來的[0,255]區(qū)間上的整數(shù)值用[0,15]上的整數(shù)值來進(jìn)行編碼，一個簡單的映射方案是x*15/255 不過這樣的映射方案頗有些Naive，雖然能減少顏色數(shù)量起到壓縮的效果，但例如，如果一個256階灰階完全由0和13兩種顏色組成，那么通過上面的映射就會得到一個全黑的，因?yàn)閮蓚€顏色全都被映射到0了。一個更好實(shí)際做法就是：將每個像素點(diǎn)當(dāng)作一個數(shù)據(jù)，跑一下K-means，得到k個點(diǎn)的像素值。對于彩片來說，也可以用同樣的方法來做，例如RGB三色，每一個像素被當(dāng)作是一個3用本文開頭那張RechardStallman大神的來做一下實(shí)驗(yàn)好了，VQ2、VQ10和VQ100三張分別顯示聚類數(shù)目為2、10和100時得到的結(jié)果，可VQ100centroids歡的?？紤]一種最簡單的壓縮辦法：單獨(dú)（比如100個）centroids的顏色信息，然后每個像素點(diǎn)centroid的索引而不是顏色信息值，如果一個VQ實(shí)現(xiàn)代碼很簡單直接使用了SciPy 提供的kmeans 寫用了PythonImageLibrary：123123456789fromscipy.cluster.vqimportkmeans,vqfromnumpyimportarray,reshape,zerosfrommltkimportimagevqclst=[2,10,100,data=image.read('example.jpg')(height,width,channel)=data.shapeforkinprint'Generatingvq-%d...'%k(centroids,distor)=kmeans(data,k)(code,distor)=vq(data,centroids)print'distor:%.6f'%distor.sum()im_vq=centroids[code,:](height,width,當(dāng)然，Vectorzation并不一定要用K-means來做，各種能用的聚類方法都可以用，只是K-means通常是最簡單的，而且通常都夠用了。Clustering3GaussianMixture本文是“漫談Clustering系列”中的第4篇，參列的其他文章。k-means行的算法：GaussianMixtureModel(GMM)。事實(shí)上，GMMk-meansGMM（GMMclusteringdensityestimation），簡單地說，k-means數(shù)據(jù)點(diǎn)被assign到其中某一個cluster了，而GMM則給出這些數(shù)據(jù)點(diǎn)被assign每個cluster概率，又稱作softassignment。以把這個概率轉(zhuǎn)換為一個score情況，比如，49%51%50%廢話說了一堆，不過，在回到GMM之前，我們再稍微扯幾句。我們知道，不管如果去掉“線性函數(shù)”這個歸納偏執(zhí)，因?yàn)閷τ贜個點(diǎn)，我們總是可以構(gòu)造一個N-1次多項(xiàng)式函數(shù)，讓它完美地穿過所有的這N個點(diǎn)，或者如果我用任何大大的N，從而得到一個（或者無窮多個）“超級函數(shù)”，能夠fit這個領(lǐng)域內(nèi)所有的問題。然而這個（或者這無窮多個）“超級函數(shù)”有用嗎？只要我們注意沒有歸納偏執(zhí)或者歸納偏執(zhí)太寬泛會導(dǎo)致Overfitting，然而另一個──望的目的，然而絕大多數(shù)模型都會有那么一些“參數(shù)”（例如K-means中的GMM，GMMGaussianMixtureModel就是假設(shè)數(shù)據(jù)服從MixtureGaussianDistribution，換句話說，數(shù)據(jù)可以看作是從數(shù)個GaussianDistribution中生成出來的。實(shí)際上我們在K-means和 K-meds兩篇文章中用到的那個例子就是由三個Gaussian分布從隨機(jī)選取出來的。實(shí)際上，從中心極限定理可以看出，Gaussian分布（也叫做正態(tài)(Normal)分布）這個假設(shè)其實(shí)是比較合理的，除此之外，Gaussian分布在計(jì)算上也有一些很好的性質(zhì)，所以，雖然我們可以用不同的分布來隨意地構(gòu)造XXMixtureModel，但是還是GMM最為流行。另外，MixtureModel本身其實(shí)也是可以變得任意復(fù)雜的，通過增加Model的個數(shù)，每個GMM由 個Gaussian分布組成，每個Gaussian稱為一個“Component”，這些Component線性加成在一起就組成了GMM的概率密度函根據(jù)上面的式子，如果我們要從GMM以分為兩步：首先隨機(jī)地在這個ComponentComponent被選中的概率實(shí)際上就是它的系數(shù)，選中了Component之后，再單獨(dú)地考慮從這個Component的Gaussian分布，轉(zhuǎn)化為了已知的問題。那么如何用GMM來做clustering呢？其實(shí)很簡單，現(xiàn)在我們有了數(shù)據(jù)，假定它們是由GMM生成出來的那么我們只要根據(jù)數(shù)據(jù)推出GMM的概率分布來就可以了然后GMM的 個Component實(shí)際上就對應(yīng)了 個cluster了。根據(jù)數(shù)據(jù)來推算概率密度通常被稱作densityestimation，特別地，當(dāng)我們在 個數(shù)據(jù)點(diǎn)，并假設(shè)它們服從某個分布（記作），現(xiàn)在要確定里面的一些參數(shù)的值，例如，在GMM中，我們就需要確定 和這些參數(shù)。我們的想法是，找到這樣一組參數(shù)，它所確定的概率于，我們把這個乘積稱作似然函數(shù)(LikelihoodFunction)。下溢，因此我們通常會對其取對數(shù)，把乘積變成加 ，得下面讓我們來看一看GMM的log-likelihoodfunction：值。為了解決這個問題，我們采取之前從GMM實(shí)際上也就類似于K-means的兩步。Component（Component率）：對于每個數(shù)據(jù)來說，它由第個Component生成的概率為由于式子里的和也是需要我們估計(jì)的值，我們采用迭代法，在計(jì)算的時候我們假定和均已知取上一次迭代所得估計(jì)每個Component的參數(shù)：現(xiàn)在我們假設(shè)上一步中得到的就是正確的“數(shù)據(jù)由Component生成的概率”，亦可以當(dāng)做該Component在生成這個數(shù)據(jù)上所做的貢獻(xiàn)，或者說，我們可以看作這個值其中有這部分是由Component 現(xiàn)在實(shí)際上可以看作Component生成了這些點(diǎn)。由于每個Component都是一個標(biāo)準(zhǔn)的Gaussian分布，可以很容易分布求出最其中，并且也順理成章地可以估計(jì)為考PatternRecognitionandMachineLearning這本書的第九章。有了實(shí)際的步驟，再實(shí)現(xiàn)起來就很簡單了。代碼如下：矩陣singular的情況，可以參見這篇文章。123123456789K=%randomlypickcentroidsrndp=randperm(N);centroids=X(rndp(1:K),:);K=size(K_or_centroids,1);centroids=K_or_centroids;threshold=1e-[N,D]=%PX:N-by-Kmatrixindicatingtheprobabilityofeachcomponentgeneratingeachpoint.MODEL:astructurecontainingtheparametersforaGMM:MODEL.Miu:aK-by-Dmatrix.MODEL.Pi:a1-by-KX:N-by-DdataK_OR_CENTROIDS:eitherKindicatingthenumberofcomponentsoraK-by-DmatrixindicatingthechoosingoftheinitialK%%%%%%%%%%%%GaussianMixture%%PX=GMM(X,%[PXMODEL]=GMM(X,%%functionvarargout=gmm(X,%%initial[pMiupPipSigma]=whiletruePx=%newvalueforpGammapGamma=Px.*repmat(pPi,N,1);pGamma=pGamma./repmat(sum(pGamma,2),1,%newvalueforparametersofeachComponentNk=sum(pGamma,1);pMiu=diag(1./Nk)*pGamma'*X;pPi=Nk/N;forkk=Xshift=X-repmat(pMiu(kk,:),N,pSigma(:,:,kk)=(Xshift'*(diag(pGamma(:,kk))*Xshift))/%checkforconvergenceL=sum(log(Px*pPi'));ifL-Lprev<thresholdLprev=ifnargout==varargout=model=[];model.Sigma=pSigma;model.Pi=pPi;varargout={Px,model};function[pMiupPipSigma]=init_params()pMiu=centroids;pPi=zeros(1,K);pSigma=zeros(D,D,K);%hardassignxtoeachdistmat=repmat(sum(X.*X,2),1,K)+repmat(sum(pMiu.*pMiu,2)',N,1)-...[dummylabels]=min(distmat,[],forXk=X(labels==k,:);pPi(k)=size(Xk,1)/N;pSigma(:,:,k)=cov(Xk);functionPx=calc_prob()Px=zeros(N,K);fork=1:KXshift=X-repmat(pMiu(k,:),N,1);inv_pSigma=inv(pSigma(:,:,k));tmp=sum((Xshift*inv_pSigma).*Xshift,2);coef=(2*pi)^(-D/2)*Px(:,k)=coef*exp(-函數(shù)返回的Px 行中最大的那個概率值所對應(yīng)的那個Component為 K-means那個cluster有一些點(diǎn)跑得比較遠(yuǎn)了。當(dāng)然，因?yàn)檫@個問題原本就是完全有MixtureGaussianDistribution，GMM（如果能求得全局最優(yōu)解的GMMK-means似（都可以追溯到EM）K-means值，就有可能得到很差的結(jié)果。對于K-meansGMMK-means個更流行的做法是先用K-means（已經(jīng)重復(fù)并取最優(yōu)值了）得到一個粗略的結(jié)果，然后將其作為初值（只要將K-means所得的centroids傳入gmm函數(shù)即可），再用GMM進(jìn)行細(xì)致迭代。如我們最開始所討論的，GMM所得的結(jié)果（Px）不僅僅是數(shù)據(jù)點(diǎn)的label，而Clustering番外篇Expectation本文是“漫談Clustering系列”中的第5篇，參列的其他文章。Expectationization(EM)是一種以迭代的方式來解決一類特殊最大似然(umLikelihood)問題的方法，這類問題通常是無法直接求得最優(yōu)解，我們會看到，上一次說到的GaussianMixtureModel的迭代求解方法可以算是EM算法最典型的應(yīng)用，而最開始說的K-means其實(shí)也可以看作是GaussianMixtureModel的一個變種（固定所有的，并令即可）。然而EM實(shí)際上是一種通用的算法（或者說是框架），可GaussianMixtureModel起吧?；仡櫼幌挛覀冎耙鉀Q的問題：求以下Log-likelihoodfunction的 函數(shù)里面又有加和沒法直接求考慮一下GMM生成sampleGaussianDistribution里進(jìn)行sample。我們可以很自然地引入一個隱含變 個Component被選中了，那么 個元素置為1，其余的全為0。那么，再來看看，如果除了之前的sample 為。注意到 個元素為1的時候，亦即 Component被選中的時候，這個概率 前是一個和式再替換到最開始的那個Log-likelihoodfunction中得到新的同時關(guān)于sample和隱含變量的Log-likelihood:情況瞬間逆轉(zhuǎn)，現(xiàn)在和求和符號換了個位置，直接作用在普通的高斯分布利，完全依賴于一個我們的假設(shè)：隱含變量的值已知。然而實(shí)際上我們并不0sample的值因此我們可以把這個信息利用起來針對后驗(yàn)概率來取期望。前面，的每一個元素只有0和1兩種取值，因此按照期望的中間用貝葉斯定理變了一下形，最后得到的式子正是我們在漫談GMM中定義的。因此，對于上面那個可以直接求解的Log-likelihoodfunction ，我們只要用其期望亦即代替即可。到這里為止看起來是一個非常完美的方法不過仔細(xì)一看發(fā)現(xiàn)還有一個：之前的Log-likelihoodfunction可以直接求最大值是建立 是已知況下，現(xiàn)在雖然我們用來代替了 ，但是實(shí)際上是一個GMM的方法又推導(dǎo)了一遍。EM現(xiàn)在我們的討論將不局限于GMM并使用一些稍微緊湊一點(diǎn)的符號用 示所有的sample，同時用 過最大似然的方法估計(jì)出中的參數(shù) 很，但是要優(yōu)化卻很容易。這就是EM算法能夠解決的那一現(xiàn)在我們引入一個關(guān)于隱含變量的分布。注意到對于任意的，我們都可以對Log-likelihoodFunction作如下分解：和之間的Kullback-divergence。由于Kullback-Leiblerdivergence個分布完全相同的時候才會取到0。因此我們可以得到關(guān)系，亦即是的一個下界?，F(xiàn)在考慮EM的迭代過程，記上一次迭代得出的參數(shù)為，現(xiàn)在我們要取以令最大，由于并不依賴于因此的上限（在固定的時候）是一個定值，它取到這個最大值的條件就是Kullback-Leiblerdivergence為零，亦即等于后驗(yàn)概率。把它帶入到的表達(dá)式中可以得到其中const是常量，而是我們之前所得到的“同時包含sampleLog-likelihoodfunction這個對應(yīng)到EM中的“E”一步。在接下來的“M”一步中，我們講固定住分布，再選取合適的以將最大化，這次其上界也依賴于變量，并會隨著的增大而增大（因?yàn)槲覀冇星懊娴牟坏仁匠闪ⅲＲ话闱闆r下增大的量會比要多一些，這時候Kullback-Leiblerdivergence在新的參數(shù) 新回到“E”一步去求新的；另一方面，如果這里Kullback-LeiblerEM因此迭代的過程中得到的likelihood會逐漸近（至少是局部的）最優(yōu)值。另外，在M一步中除了用最大似然之外，也可以引入先驗(yàn)使用umaPosteriori(MAP)的方法來做。還有一些很的問題，甚至在迭代的過程中GeneralizedEM(GEM)。面我們就來舉一個用EM來做中文分詞的例子。這個例子來源于論文Self-supervisedChineseWordSegmentation。我在上次MSTC搜索引現(xiàn)在我們有一個字符序列，并希望得到一個模型（依賴于參數(shù)）能用來將其詞的序列。按照生成模型的方式來考慮，將看成是由生成的序列的話，我們自然希望找到那個生 的可能性最大的，亦即通過最大似然的方式來估計(jì)參數(shù) 然而我們不知道似然函數(shù)應(yīng)該如何去優(yōu)化因此我們引入latent 最大化即完成了EM的一次迭代。具體的做法通常是 的集合）按照N-gram分割（N-gram在講K-meds的那篇文章中介紹過）為，形成一個最初的辭典而模型的參數(shù)實(shí)際上就描述了各個N-gram的概率，初始值可以直接取為頻率值。有了辭典之后對于任意的，我們可以根據(jù)辭典枚舉出所有可能的分割，而每個分割的后驗(yàn)概率就是其中的單詞的概率乘積。其他的就是標(biāo)準(zhǔn)的EM算法的迭代步驟了。就是），并且這個過程是全自動的，主要有兩個優(yōu)點(diǎn)：Wikipedia（繁體中文）上抓下來的一些數(shù)據(jù)跑過一下小規(guī)模的試驗(yàn)，結(jié)果還可EM是怎么一回事，此為止了。Clustering4Spectral本文是“漫談Clustering系列”中的第6篇，參列的其他文章。如果說K-means和 GMM這些聚類的方法是古代流行的算法的話那么這次要講的SpectralClustering就可以算是現(xiàn)代流行的算法了，中文通常稱為SpectralClustering（K-means）和K-meds 類似，SpectralClustering只需要數(shù)據(jù)之間的相似度矩陣就可以了，而不必像K-means那樣要求數(shù)據(jù)必須是N維歐氏空間中的向量。于不規(guī)則的誤差數(shù)據(jù)不是那么敏感，而且performance也要好一些。許多實(shí)作為baseline而存在的。K-meansK-meansK-means馬，先拉出來溜溜再說。不過，在K-meds那篇文章中曾經(jīng)實(shí)際跑過K-meds算法，最后的結(jié)果也就是一個accuracy，一個數(shù)字又不能畫成圖表之類的，看起來實(shí)在是沒意思，而且K-means結(jié)果來自clusteringusinglocalityindexing這篇，這篇實(shí)際上是提的另一種聚類方法（下次如果有機(jī)會也會講到），K-meansSpectralClusteringk Reuters-K-K-2349TDT2Reuters-21578K-meansSC(SpectralClustering)抽取了這兩個數(shù)據(jù)集中若干個類別（從210類）的數(shù)據(jù)進(jìn)行聚類，得出Clustering這里完勝K-means。以看到SpectralClustering算法的全貌：根據(jù)數(shù)據(jù)構(gòu)造一個Graph，Graph的每一個節(jié)點(diǎn)對應(yīng)一個數(shù)據(jù)點(diǎn)，將相似的點(diǎn)連接起來，并且邊的權(quán)重用于表示數(shù)據(jù)之間的相似度。把這個Graph用鄰接矩 K-meds中用的相似度矩陣作為 果中每一行所屬的類別就是原來Graph中的節(jié)點(diǎn)亦即最初的 其實(shí)，如果你熟悉DimensionalReduction（降維）的話，大概已經(jīng)看出來了，SpectralClusteringLaplacianEigenmap之后再做K-means的一個過程──聽起來土多了。不過，為什么要剛好降到維呢？其實(shí)整個模型還可以從另一個角度導(dǎo)出來，所以，讓我們不妨先ImageProcessing（我好像之前有聽說我對這個領(lǐng)域深惡痛絕？）里有一個問題就是對圖像進(jìn)行Segmentation（區(qū)域分割），也就是讓相似的像素組成ImageProcessing這個問題，并且有不少方法和Clustering有密切聯(lián)系。比如我們在談Vectorzation的時候就曾經(jīng)用K-means來把顏色相似的像素聚類到一起，不feature（R、G、B一個像素，現(xiàn)在加入x、y兩個新的值）即可。另一方面，還有一個經(jīng)常被研究的問題就是GraphCut，簡單地說就是把一個Graph的一些邊切斷，讓他被打散成一些獨(dú)立的sub-Graph，而這些被切斷的邊的權(quán)值的總和就被稱為Cut值。如果用一張中的所有像素來組成一個Graph，并把（比如，顏色和位置上）相似的節(jié)點(diǎn)連接起來，邊上的權(quán)值表示相似程度，那么把分割為幾個區(qū)域的問題實(shí)際上等價于把Graph分sub-GraphCut切斷，表示比較相似的點(diǎn)被保留在了同一個sub-Graph中，而彼此之間聯(lián)系不cut（最小割）本身就是一個被廣泛研究的問題，并且有成算法來求解。只多替代的算法提出來，如RatioCut、NormalizedCut等。述清楚。將Graph表示為鄰接矩陣的形式，記為 ，其中是節(jié) 到節(jié)點(diǎn)的權(quán)值，如果兩個節(jié)點(diǎn)不是相連的，權(quán)值為零設(shè)和 為Graph的兩個子集（沒有交集），那么兩者之間的cut可先考慮最簡單的情況，如果把一個GraphMinimumcut就是要最小化（其中表示的補(bǔ)集）。但是由于這樣經(jīng)常會出現(xiàn)孤立節(jié)點(diǎn)被分割出來的情況，因此又出現(xiàn)了RatioCut：以及NormalizedCut其中表示中的節(jié)點(diǎn)數(shù)目，而。兩者都可算作的“大小”的一種度量，通過在分母上放置這樣的項(xiàng)，就可以有效地防止孤立點(diǎn)的情況出現(xiàn)，達(dá)到相對平均一些的分割。事實(shí)上，JianboShi的這篇PAMIpaper：NormalizedCutsandImageSegmentation正是把NormalizedCut用在圖像分割上了。搬出RatioCutNormalizedCutSpectralClustering是一個NP難問題，不方便求解，為了找到解決辦法，讓我們先來做做變形。令表示Graph的所有節(jié)點(diǎn)的集合，首先定義一個維向量 Usually,everyauthorjustcalls“his”matrixthegraph個有一個性質(zhì)就是：這個是對任意向量都成立的，很好證明，只要按照定義展開就可以得到了。把我們剛才定義的那個帶進(jìn)去，就可以得到1到和。由于是一個常量，因最小化RatioCut就等價于最小化，當(dāng)然，要記得加上附加條 以及問題轉(zhuǎn)化到這個樣子就好求了，因?yàn)橛幸粋€叫做Rayleighquotient的東西：征值并且極值 等于對應(yīng)的特征向量時取到由于是常數(shù)因此最小化實(shí)際上也就等價于最小化，不過由于的最小的特征值為零，并且對應(yīng)的特征向量正好為（我們這里僅考慮Graph是的情況），不滿足的條件，因此我們?nèi)〉诙€小的特征值，以及對應(yīng)的特征向量。們耍了一個把戲：之前的問題之所以NP難是因?yàn)橄蛄康脑刂荒苋芍岛椭械囊粋€，是一個離散的問題，而我們求的特征向量其中的元素可以是任意實(shí)數(shù)，就是說原來的問題限制放寬了。那如何得到原來的解呢？一個最簡單的辦法就是看零還是小于零，將他們分別對應(yīng)到離散情況的和不過我們也可以采取稍微復(fù)雜一點(diǎn)的辦法，用的K-means來將到此為止，已經(jīng)有SpectralClustering的了：求特征值，再對特征向量K-meansk（數(shù)學(xué)推導(dǎo)我就不再詳細(xì)寫了），我們就得到了和之前的SpectralClustering一模一樣的步驟：求特征值并取前k個最小的，將對應(yīng)的特征向量排列起來，再按行進(jìn)行K-means用類似的辦法，NormalizedCut也可以等價到SpectralClustering不過這次我就不再講那么多了感的（還包括其他一些形式的GraphLaplacian以SpectralClustering和Randomwalk的關(guān)系TutorialATutorialonSpectralClustering。SpectralClusteringfunctionfunctionidx=spectral_clustering(W,k)D=diag(sum(W));L=D-opt=struct('issym',true,'isreal',true);[Vdummy]=eigs(L,D,k,'SM',idx=kmeans(V,SpectralClustering 是我們構(gòu)造出來的Graph的鄰接矩陣表示，通常我們在構(gòu)造Graph的時候?yàn)榱朔奖氵M(jìn)行聚類，更加強(qiáng)到“局部”的連通性，亦抓住了主要，忽略了次要的東西，Performance比傳統(tǒng)的K-means要好。SpectralClusteringK-means用LaplacianEigenmap進(jìn)行降維的后的結(jié)果，如果有機(jī)會，下次談DimensionalityReductionk（k很大），在這些低維的數(shù)據(jù)上做K-means運(yùn)算量非常小。但是對于原始數(shù)據(jù)直接做K-means的話，雖然最初的數(shù)據(jù)是稀疏矩陣，但是K-means中有一個求Centroid的運(yùn)算，就是求一個平均值：許多稀疏的向量的平均值求出來并不一致普通的K-means巨慢無比，而SpectralClustering等工序的算法則迅Clustering名字來源于Spectraltheory，也就是用特征分解來分析問題的UPDATE2011.11.23:LEKmeansSpectralCluster1thresholdingK類的情況，自然的類比就是降到K-1維，這也是和LDA保持一致。因?yàn)長aplacian（0），所以可以K0關(guān)于示例代碼：注意除非我在這里注明了是發(fā)布某個software或者package自己試驗(yàn)一下具體實(shí)現(xiàn)和改進(jìn)，否則可以直接找網(wǎng)上現(xiàn)成的的package，比如SpectralClustering可以考慮這個包。Clustering番外篇Dimensionality本文是“漫談Clustering系列”中的第7篇，參列的其他文章。例如，一個最簡單的將一個文本轉(zhuǎn)化為向量的方法如下：假設(shè)待提取的文檔是“Tobe,ornottobe:thatisthequestion:”，首先對其進(jìn)行一些預(yù)處理，例如去掉單詞的時態(tài)后綴、濾掉標(biāo)點(diǎn)符號等，得到“tobeornottobethatbethequestion”。統(tǒng)計(jì)三個維度所對應(yīng)的單詞出現(xiàn)的頻率：to2，be3次，the1該文檔對應(yīng)的向量即[2,3,1]不過事實(shí)上我們通常會做更復(fù)雜一些的處理例如如果你是在做sentimentysis那么你通常會更加關(guān)注語氣很重的詞比如“bad”“terrible”、“awesome”等的重要性就比普通的詞要大此時你可以為每一個維度設(shè)一個權(quán)重，例如，給“bad”設(shè)置權(quán)重2，那么出現(xiàn)3次的話，向量在該維度對應(yīng)的值就為2*3=6 是tf-idfInverseFrequency，通常使用如下公式進(jìn)行計(jì)算feature一些，手工設(shè)置維度的權(quán)重固然是很人力，其實(shí)tf-idf也是在假定了原始feature是、term這樣的形式（或者類似的模型）的情況下才適用featurefeatureselectiondimensionalityreductiontopic出重要的feature的維度（并拋棄不重要的維度），而后者則是更廣泛意義上的值已經(jīng)不一定是原始的值，也可以把featureselection看作是dimensionalityreductiontf-idffeatureselection（通常）并沒有丟棄低權(quán)值的維度，并且處理過后一個函數(shù)，其輸入是一個D維的向量，輸出是一個M維的向量。reconstructionerror reconstructionerror另外式是簡單地使用variance來衡量所包含信息量，例如，我們要把D1variance 是降維函數(shù)。推而廣之，如果是降為2維，那么我希望第2維去關(guān)注第1維之外的variance，所以要求它在與第一維垂直的情況下也達(dá)到variance最大化。以此類推。然而當(dāng)我們把降維函數(shù)限定維線性的時候兩種途徑會得到同樣的結(jié)果，就是被廣泛使用的PrincipalComponentsysis(PCA)。PCA的降維函數(shù) 來表示，因此，一個D維的 經(jīng)過線性變換之后得到一個M維向量，就是降維的結(jié)果。 維的數(shù)據(jù)矩陣，目標(biāo)是使其covariance （covariance），當(dāng)然矩陣不是一個數(shù)，不能直接最化，如果我們采用矩陣的Trace 求最大化只需要求出的特征值和特征向量將M個 這也就是PCA的求解過程，得到的降維矩陣 如果熟悉LatentSemanticysis(LSA)的話，大概已經(jīng)看出PCA和SingularValueposition(SVD)以及LSA之間的關(guān)系了。以下這張圖（引自《TheElementsofStatisticalLearning》）可以直觀地看出來PCA做了什么，對于一些原始為二維的數(shù)據(jù)，PCAvariancePCA檢索等各個領(lǐng)域，其地位類似于聚類中的K-means，在現(xiàn)在關(guān)于降維等算法的baseline，PCA個就是PCA降維是線性變換，雖然線性變換計(jì)算方便，并且可以很容易地推廣其中一個就是KernelPCA，用KernelTrick來將PCA推廣到非線性的情況。另外，PCAGaussianlatentvariable模型，它假定數(shù)據(jù)的mean和variance是重要的特征，并依靠covariance一個典型的問題就是做聚類或分類，回想我們之前談過的SpectralClustering，就是使用LaplacianeigenmapK-meansPCAreconstructionerror分不同類別的。如果我們有訓(xùn)練數(shù)據(jù)的類別，則可以用FisherLinearDiscriminantysis來處理這個問題。同PCA一樣，F(xiàn)isherLinearDiscriminantysis也是一個線性映射模型VariancevariancevariancePatternClassification》這本書的第三章ComponentysisandDiscriminants。LinearDiscriminantysis就沒有辦法了。不過，如果我們假設(shè)原始的數(shù)MDS三維或者二維，用于做visualization。MDSSpectralClusteringLaplacianEigenmapMDS，LE相似度矩陣，不過這里通常要求這個相似度矩陣具有局部性質(zhì)，亦即只考慮局部領(lǐng)域內(nèi)的相似性，如果點(diǎn)和距離太遠(yuǎn)的話，應(yīng)該為零。1.對每個點(diǎn)選取k個最接近的點(diǎn)作為鄰居，與其他的點(diǎn)的相似性則置為零。這里需要注意的是LE要求相似度矩陣具有對稱性，因此，我們通常會在 于的k個最接近的鄰居且/或反之的時候，就保留的值，否則置為 那么會相對比較大，這樣如果映射過后 就會被權(quán)重放大，因此最小化目標(biāo)函數(shù)就保證了原來相近的點(diǎn)在映射過后令為將的每一行加起來所得到的對角陣，而 稱作是拉斯矩陣，通過求解如下的特征值問題易知最小的那個特征值肯定是0NN類似地推廣到M0M的特征向量，轉(zhuǎn)置之后按行排列起來，就是降維后的結(jié)果。用代碼寫出來如下所示（使用了knn來構(gòu)造相似度矩陣，并且沒有用heatkernel）：1212345678910111281%LaplacianEigenmapALGORITHM(usingKnearest%%[Y]=%%X=dataasDxNmatrix(D=dimensionality,N=%K=numberof%dmax=maxembedding%Y=embeddingasdmaxxNfunction[Y]=[D,N]=fprintf(1,'LErunningon%dpointsin%d%STEP1:COMPUTEPAIRWISEDISTANCES&FINDX2=[sorted,index]=sort(distance);neighborhood=index(2:(1+K),:);920920212223242526272829303132333435%STEP2:ConstructsimilaritymatrixWW=zeros(N,N);forii=1:NW(ii,neighborhood(:,ii))=1;W(neighborhood(:,ii),ii)=%STEP3:COMPUTEEMBEDDINGFROMEIGENVECTSOFL=D-W;%CALCULATIONOFoptions.disp=0;options.isreal=1;options.issym=1;[Y,eigenvals]=eigs(L,d+1,0,options);Y=Y(:,2:d+1)'*sqrt(N);%bottomevectis[1,1,1,1...]witheval3363738394044748495051522事實(shí)上，LaplacianEigenmap假設(shè)數(shù)據(jù)分布在一個嵌套在高中的低維流LaplacianMatrix則是流形的LaplaceBeltramioperator的LaplacianEigenmap這里做地展開了，下面看一個比較直觀的例子SwissRoll。SwissRoll是一個像面包圈一樣的結(jié)構(gòu)，可以看作一個嵌套在三中的二SwissRollSwissRollLaplacianEigenmapPCASwissRoll看到LE成功地把這個流形展開把在流形上屬于不同位置的點(diǎn)映射到了不同的地方，而PCA的結(jié)果則很糟糕，幾種顏色都混雜在了一起。LocallyLinearEmbeddingLE 應(yīng)當(dāng)?shù)扔诹恪＿@之后再把 際上，從理論上也可以得出二者之間的聯(lián)系（LE對應(yīng)于 而LLE對應(yīng)于），如果感的話，可以參考LaplacianEigenmapsforDimensionalityReductionandDataRepresentation這篇里的對比。下面是兩種方法在SwissRoll數(shù)據(jù)上的結(jié)果，也是非常相似的：影矩陣，這個結(jié)果可以保存下來，在之后對任意向量進(jìn)行投影，而LE和LLEPCALELLE別叫做LocalityPreservingProjection和NeighborhoodPreservingEmbedding。LPPPCA陣來表示，于是LE的目標(biāo)函數(shù)變?yōu)榈玫降陌凑仗卣髦祻男〉酱笈判虻奶卣飨蛄烤徒M成映射矩陣LELE里的矩陣在乘以之后通常就不再稀疏了，計(jì)算量會變得比較大，這個問題可以使用SpectralRegression的方法來解決，參見SpectralRegression:AUnifiedApproachforSparseSubspaceLearningpaperKernelTrickLPPLELLENPE另外，雖然LE是unsupervised的，但是如果訓(xùn)練數(shù)據(jù)確實(shí)有可用，也是的決策過程其實(shí)人是可以“看到”或者說“理解”的，但是SVM就不那么法發(fā)展出“智能”來啊^_^bbClustering5Hierarchical本文是“漫談Clustering系列”中的第8篇，見本系列的其他文不過覺得HierarchicalClustering這個話題我能說的東西應(yīng)該不多，所以還是先寫了吧（我準(zhǔn)備這次一個公式都不貼）。Hierarchicalnaive不過言歸正傳，這里要說的HierarchicalClustering聽上去很，不過其實(shí)HierarchicalClustering的想法很簡單，主要分為兩大類：agglomerative（自底向上）divisive（自頂向下）。首先說前者，看起來很簡單吧？其實(shí)確實(shí)也是比較簡單的，不過還是有兩個問題需要problemdependentSingleLinkage：又叫做nearest-neighbor的兩個點(diǎn)的距離作為這兩個集合的距離，容易造成一種叫做Chaining的效離比較近就被合并了，并且這樣合并之后Chaining效應(yīng)會進(jìn)一步擴(kuò)大，最后會得到比較松散的cluster。CompleteLinkage：這個則完全是SingleLinkage的，取兩個集SingleLinkageCompleteLinkage的方法。整個agglomerativehierarchicalclustering的算法就是這個離最近的兩個點(diǎn)，需要一個雙重循環(huán)，而且GroupAverage計(jì)算距離的時候也123456789123456789def#makeacopy,donottouchtheoriginallistnodes