譜聚給你博客園上若干個(gè)博客，讓你將它們分成K類，你會(huì)怎樣做？想必有很多方法，本文要聚類的直觀解釋是根據(jù)樣本間相似度，將它們分成不同組。譜聚類的思想是將樣本看作頂接不同組的邊的權(quán)重盡可能低（這意味著組間相似度要盡可能低（這意味著組內(nèi)相似度要盡可能高如下圖所示：在上圖中，一共有6個(gè)頂點(diǎn)（博客），頂點(diǎn)之間的連線表示兩個(gè)頂點(diǎn)的相似度，現(xiàn)在要將這圖分成兩半（兩個(gè)類（去掉哪邊條？根據(jù)譜聚類的思想，應(yīng)該去掉的邊是用虛線表示的那條。最后，剩下的兩半就分別對(duì)應(yīng)兩個(gè)類了。根據(jù)這個(gè)思想，可以得到unnormalized譜聚類和normalized譜聚類，由于前者比后者簡單，所以本文介紹unnormalized譜聚類的幾個(gè)步驟（假設(shè)要分K個(gè)類）：unnormalizedgraphLaplacianmatrixL(LDW,Ddegree計(jì)算L的前K把這k個(gè)特征向量排列在一起組成一個(gè)N*k的矩陣，將其中每一行看作k中的一個(gè)向量，并使用K-means算法進(jìn)行聚類這一節(jié)主要從大體上解unnormalized譜聚類的四個(gè)步驟是怎么來的，不涉及具體的公譜聚類的思想就是要轉(zhuǎn)化為圖分割問題。因此，第一步就是將原問題轉(zhuǎn)化為圖。轉(zhuǎn)為圖有兩個(gè)問題要解決：一是兩個(gè)頂點(diǎn)的邊要怎樣定義；二是要保留哪些邊。對(duì)于第一個(gè)問題，如果兩個(gè)點(diǎn)在一定程度上相似，就在兩個(gè)點(diǎn)之間添加一條邊。相似的過常用的Gaussiansimilarityfunction法是建立k-nearestneighborgraph。在這種圖中，每個(gè)頂點(diǎn)只與K個(gè)相似度最高的點(diǎn)連邊。unnormalizedgraphLaplacianmatrix(L表示)有很多很好的性質(zhì)，也正是這個(gè)這一組性質(zhì)將在之后的公式推導(dǎo)中起到?jīng)Q定性作用將原問題轉(zhuǎn)化為圖后，接下來的工作就是決定怎樣分。圖分割問題實(shí)際上就是最小割問題(mincutpoblem)。最小割問題可定義為最小化以下目標(biāo)函數(shù)：其中k表示分成k個(gè)組，Ai表示第i個(gè)組，表示第Ai的補(bǔ)集，W(A,B)表示第A組與第組之間的所有邊的權(quán)重之和這個(gè)式子的直觀意義：如果要分成K個(gè)組，那么其代價(jià)就是進(jìn)行分割時(shí)去掉的邊的權(quán)重的總和。可惜的是直接最小化這式子通常會(huì)導(dǎo)致不好的分割。以分成2類為例，這個(gè)式子通常會(huì)將圖分成這樣的兩類：一個(gè)點(diǎn)為一類，剩下的所有點(diǎn)為另一類。顯然，這樣的分割是很不好的。因?yàn)槲覀兤谕總€(gè)類都有合理的大小。所以，要對(duì)這個(gè)式子進(jìn)行改進(jìn)，改進(jìn)后的公式（稱為RatioCut)如下其中|A|表示A組中包含的頂點(diǎn)數(shù)目在RatioCut中，如果某一組包含的頂點(diǎn)數(shù)越少，那么它的值就越大。在一個(gè)最小化問題中，這相當(dāng)于是懲罰，也就是不鼓勵(lì)將組分得太小?，F(xiàn)在只要將最小化RatioCut解出來，分割就完成了。不幸的是，這是個(gè)NP難問題。想要在多項(xiàng)式時(shí)間內(nèi)解出來，就要對(duì)這個(gè)問題作一個(gè)轉(zhuǎn)化了。在轉(zhuǎn)化的過程中，就用到上面提到的L的那一組性質(zhì)，經(jīng)過若干推導(dǎo)，最后可以得到這樣的一個(gè)其中H是一個(gè)矩陣，它的元素的定義(Eq.(5))如果H矩陣的元素不為0，則說明第i個(gè)點(diǎn)屬于第j個(gè)類。也就是說，只要得到H矩陣，就能知道要怎樣分。可惜的是，這個(gè)問題仍然是NP難問題。但是，如果我們讓H矩根據(jù)Rayleigh-Ritztheorem，這個(gè)問題的解是L的前k個(gè)最小的特征向量組成的矩陣H，其中特征向量是按列來排H的每一列，均為一個(gè)特征向量。在第三步中，我們?yōu)榱怂神YNP難問題，讓H矩陣取任意值，因此，解出來的H矩陣不再具有原來的性質(zhì)——元素值能哪個(gè)點(diǎn)屬于哪一類。盡管如此，對(duì)于k-means來說，將H矩k-meansH矩陣進(jìn)行聚類作為譜以下是unnormalied譜聚類的 版實(shí)現(xiàn)（博客園的代碼格式選擇中居然沒有的。。。這里選個(gè)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下線一段時(shí)間，而租DreamHost的事情又Learning相關(guān)的東西，因?yàn)楹芏鄸|西都不懂，所以平時(shí)也找一些資料來看。按Clustering中文翻譯作“聚類”，簡單地說就是把相似的東西分到一組，同Classification(分類)不同，對(duì)于一個(gè)classifier，通常需要你告訴它“這classifier練數(shù)據(jù)的過程通常叫做supervisedlearning(監(jiān)督學(xué)習(xí))，而在聚類的時(shí)候，因此，一個(gè)聚類算法通常只需要知道如何計(jì)算相似度就可以開始工作了，因此clustering通常并不需要使用訓(xùn)練數(shù)據(jù)進(jìn)行學(xué)習(xí)，這在MachineLearning中被稱作unsupervisedlearning(無監(jiān)督學(xué)習(xí))。映射到一個(gè)單獨(dú)的特征之外，一種常見的做法是同時(shí)提取N種特征，將它們放NNclustering大致看出來”，不過，對(duì)于這樣的N維歐氏空間中的點(diǎn)進(jìn)行聚類，有一個(gè)非常k-meansk-meansclustercenter)cluster所有的點(diǎn)到該中心點(diǎn)的距離小于到其他cluster的中心的距離。雖然實(shí)際情況情況是2，通常我們會(huì)將它歸類為左邊的那個(gè)分布，因?yàn)楦怕蚀笠恍?，然而此分性，無法避免。因此，k-means所依賴的這個(gè)假設(shè)看作是合理的。有N個(gè)數(shù)據(jù)點(diǎn)需要分為K個(gè)cluster，k-means要做的就是最小化 在數(shù)據(jù)點(diǎn)n被歸類到clusterk的時(shí)候?yàn)?，否則0。直接尋找 和來最小化 代的辦法：先固定，選擇最優(yōu)的 的。將 對(duì)求導(dǎo)并令導(dǎo)數(shù)等于零，很容易得到 候應(yīng)該滿足：亦即的值應(yīng)當(dāng)是所有clusterk中的數(shù)據(jù)點(diǎn)的平均值。由于每一次迭代都是取到的最小值，因此只會(huì)不斷地減?。ɑ蛘卟蛔儯粫?huì)增加，k-meansk-means到全局最優(yōu)解，但是對(duì)于這樣的問題，像k-meansk-means選定K個(gè)中心的初值。這個(gè)過程通常是針對(duì)具體的問題有一些啟發(fā)式的，或者大多數(shù)情況下采用隨機(jī)選取的辦法。因?yàn)榍懊鎘-means并以有時(shí)候我們會(huì)多次選取初值跑k-means，并取其中最好的一次結(jié)果。cluster按照這個(gè)步驟寫一個(gè)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來做這個(gè)事情確實(shí)不如方便，實(shí)際的k-means的代碼只是4147341到4345473個(gè)中心點(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的一個(gè)變種。將中心點(diǎn)取為當(dāng)前cluster中所有數(shù)據(jù)點(diǎn)的平均值：Rough并且我們已經(jīng)證明在固定了各個(gè)數(shù)據(jù)點(diǎn)的assignment的情況下這樣選取的中 最小化。然而在k-meds中，中心點(diǎn)的選取限制在當(dāng)前cluster所包含的數(shù)據(jù)點(diǎn)的集合中。換句話說，在k-meds算法中，從當(dāng)前cluster中選取這樣一個(gè)點(diǎn)——它到其他所有（當(dāng)前cluster中的）點(diǎn)的距離之和最小——作為中心點(diǎn)。k-means和k-meds之間的差異就類似于一個(gè)數(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ù)中的歐氏距離改為一個(gè)任意的dissimilaritymeasure函數(shù)最常見的方式是構(gòu)造一個(gè)dissimilaritymatrix 來代表，其中的元素表示第 只狗和第只狗之間的差異程度，例如，兩只Samoyed 之間的差異可以設(shè)為0，一只GermanShepherdDog和一只RoughCollie之間的差異是0.7，和一只MiniatureSchnauzer之間的差異是1，等等。除此之外，由于中心點(diǎn)是在已有的數(shù)據(jù)點(diǎn)里面選取的，因此相對(duì)于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在這個(gè)例子上也能得到很好的結(jié)果k-meansk-meansk-meds復(fù)雜度陡然增加了許多：在k-means即可，而在k-meds中則需要枚舉每個(gè)點(diǎn)，并求出它到所有其他點(diǎn)的距離之和，復(fù)雜度為看完了直觀的例子，讓我們再來看一個(gè)稍微實(shí)際一點(diǎn)的例子好了：Clustering——那個(gè)永恒不變的，不過我們這里要做的聚類并不是針對(duì)文檔的而是針對(duì)文檔的語言實(shí)驗(yàn)數(shù)據(jù)是從Europarl 和Swedish這些語言的文本數(shù)據(jù)集。在N-gram-basedtextcategorization這篇paper中描述了一種計(jì)算由不同語言寫成的文檔的相似度的方法。一個(gè)（以字符為單位的）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)建出一個(gè)Profile，在拿到一篇未知文檔的時(shí)候，只要和各個(gè)Profile比較一下，差異最小的那個(gè)Profile所對(duì)應(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我為這七千多個(gè)文檔建立了Profile并構(gòu)造出一個(gè)7038×7038的dissimilaritymatrix，最后在這上面用k-meds進(jìn)行聚類。構(gòu)造的，并且通常只要數(shù)次迭代就能收斂了。實(shí)際的k-meds實(shí)現(xiàn)可以在mltk 并不知道這些cluster應(yīng)該被打上什么，或者說，在這個(gè)問題里，包含了哪種語言的文檔。由于我們的目的是衡量聚類算法的performance，因此直接假定這一步能實(shí)現(xiàn)最優(yōu)的對(duì)應(yīng)關(guān)系，將每個(gè)cluster對(duì)應(yīng)到一種語言上去。一以用Hungarianalgorithm來求解。1111!=我們需要遍歷一次labellist，并數(shù)出真正的label（語言）與聚類得出的并求出accuracy只需要1毫秒的時(shí)間的話，總共也需要11個(gè)小時(shí)才能得到具體的算法了，感的同學(xué)可以參考Wikipedia，這里我直接使用了一個(gè)現(xiàn)有的Python實(shí)現(xiàn)。雖然這個(gè)實(shí)驗(yàn)非常折騰，不過最后的結(jié)果其實(shí)就是一個(gè)數(shù)字：accuracy我這里達(dá)到了88.97%，證明k-meds聚類和N-gramProfile識(shí)別語言這要版的scipy，munkres.py和mltk以及Python2.6。Clustering番外篇Vector本文是“漫談Clustering系列”中的第3篇，參見本系列的其Vectorzation。這項(xiàng)技術(shù)廣泛地用在信號(hào)處理以及數(shù)據(jù)壓縮等領(lǐng)域。事實(shí)上，在JPEG和MPEG-4等多壓縮格式里都有VQ這一步。Vectorzation這個(gè)名字聽起來有些玄乎，其實(shí)它本身并沒有這么高深。比如，[0,1)上的所有值變?yōu)?，[1,2)上的所有值變成1，如此類推。其這就是一個(gè)VQ的過程。一個(gè)比較正式一點(diǎn)的定義是：VQ是將一個(gè)向量空間中一個(gè)典型的例子就是圖像的編碼最簡單的情況考慮一個(gè)灰度 為黑色1為白色，每個(gè)像素的值為[0,1]上的一個(gè)實(shí)數(shù)。現(xiàn)在要把它編碼為256階的灰階，一個(gè)最簡單的做法就是將每一個(gè)像素值x 數(shù)floor(x*255) 現(xiàn)在想要把壓縮這個(gè)，每個(gè)像素只使用4bit（而不是原來的8bit），因此，要將原來的[0,255]區(qū)間上的整數(shù)值用[0,15]上的整數(shù)值來進(jìn)行編碼，一個(gè)簡單的映射方案是x*15/255 不過這樣的映射方案頗有些Naive，雖然能減少顏色數(shù)量起到壓縮的效果，但例如，如果一個(gè)256階灰階完全由0和13兩種顏色組成，那么通過上面的映射就會(huì)得到一個(gè)全黑的，因?yàn)閮蓚€(gè)顏色全都被映射到0了。一個(gè)更好實(shí)際做法就是：將每個(gè)像素點(diǎn)當(dāng)作一個(gè)數(shù)據(jù)，跑一下K-means，得到k個(gè)點(diǎn)的像素值。對(duì)于彩片來說，也可以用同樣的方法來做，例如RGB三色，每一個(gè)像素被當(dāng)作是一個(gè)3用本文開頭那張RechardStallman大神的來做一下實(shí)驗(yàn)好了，VQ2、VQ10和VQ100三張分別顯示聚類數(shù)目為2、10和100時(shí)得到的結(jié)果，可VQ100centroids歡的。考慮一種最簡單的壓縮辦法：單獨(dú)（比如100個(gè)）centroids的顏色信息，然后每個(gè)像素點(diǎn)centroid的索引而不是顏色信息值，如果一個(gè)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通常是最簡單的，而且通常都?jí)蛴昧恕lustering3GaussianMixture本文是“漫談Clustering系列”中的第4篇，參列的其他文章。k-means行的算法：GaussianMixtureModel(GMM)。事實(shí)上，GMMk-meansGMM（GMMclusteringdensityestimation），簡單地說，k-means數(shù)據(jù)點(diǎn)被assign到其中某一個(gè)cluster了，而GMM則給出這些數(shù)據(jù)點(diǎn)被assign每個(gè)cluster概率，又稱作softassignment。以把這個(gè)概率轉(zhuǎn)換為一個(gè)score情況，比如，49%51%50%廢話說了一堆，不過，在回到GMM之前，我們再稍微扯幾句。我們知道，不管如果去掉“線性函數(shù)”這個(gè)歸納偏執(zhí)，因?yàn)閷?duì)于N個(gè)點(diǎn)，我們總是可以構(gòu)造一個(gè)N-1次多項(xiàng)式函數(shù)，讓它完美地穿過所有的這N個(gè)點(diǎn)，或者如果我用任何大大的N，從而得到一個(gè)（或者無窮多個(gè)）“超級(jí)函數(shù)”，能夠fit這個(gè)領(lǐng)域內(nèi)所有的問題。然而這個(gè)（或者這無窮多個(gè)）“超級(jí)函數(shù)”有用嗎？只要我們注意沒有歸納偏執(zhí)或者歸納偏執(zhí)太寬泛會(huì)導(dǎo)致Overfitting，然而另一個(gè)──望的目的，然而絕大多數(shù)模型都會(huì)有那么一些“參數(shù)”（例如K-means中的GMM，GMMGaussianMixtureModel就是假設(shè)數(shù)據(jù)服從MixtureGaussianDistribution，換句話說，數(shù)據(jù)可以看作是從數(shù)個(gè)GaussianDistribution中生成出來的。實(shí)際上我們在K-means和 K-meds兩篇文章中用到的那個(gè)例子就是由三個(gè)Gaussian分布從隨機(jī)選取出來的。實(shí)際上，從中心極限定理可以看出，Gaussian分布（也叫做正態(tài)(Normal)分布）這個(gè)假設(shè)其實(shí)是比較合理的，除此之外，Gaussian分布在計(jì)算上也有一些很好的性質(zhì)，所以，雖然我們可以用不同的分布來隨意地構(gòu)造XXMixtureModel，但是還是GMM最為流行。另外，MixtureModel本身其實(shí)也是可以變得任意復(fù)雜的，通過增加Model的個(gè)數(shù)，每個(gè)GMM由 個(gè)Gaussian分布組成，每個(gè)Gaussian稱為一個(gè)“Component”，這些Component線性加成在一起就組成了GMM的概率密度函根據(jù)上面的式子，如果我們要從GMM以分為兩步：首先隨機(jī)地在這個(gè)ComponentComponent被選中的概率實(shí)際上就是它的系數(shù)，選中了Component之后，再單獨(dú)地考慮從這個(gè)Component的Gaussian分布，轉(zhuǎn)化為了已知的問題。那么如何用GMM來做clustering呢？其實(shí)很簡單，現(xiàn)在我們有了數(shù)據(jù)，假定它們是由GMM生成出來的那么我們只要根據(jù)數(shù)據(jù)推出GMM的概率分布來就可以了然后GMM的 個(gè)Component實(shí)際上就對(duì)應(yīng)了 個(gè)cluster了。根據(jù)數(shù)據(jù)來推算概率密度通常被稱作densityestimation，特別地，當(dāng)我們在 個(gè)數(shù)據(jù)點(diǎn)，并假設(shè)它們服從某個(gè)分布（記作），現(xiàn)在要確定里面的一些參數(shù)的值，例如，在GMM中，我們就需要確定 和這些參數(shù)。我們的想法是，找到這樣一組參數(shù)，它所確定的概率于，我們把這個(gè)乘積稱作似然函數(shù)(LikelihoodFunction)。下溢，因此我們通常會(huì)對(duì)其取對(duì)數(shù)，把乘積變成加 ，得下面讓我們來看一看GMM的log-likelihoodfunction：值。為了解決這個(gè)問題，我們采取之前從GMM實(shí)際上也就類似于K-means的兩步。Component（Component率）：對(duì)于每個(gè)數(shù)據(jù)來說，它由第個(gè)Component生成的概率為由于式子里的和也是需要我們估計(jì)的值，我們采用迭代法，在計(jì)算的時(shí)候我們假定和均已知取上一次迭代所得估計(jì)每個(gè)Component的參數(shù)：現(xiàn)在我們假設(shè)上一步中得到的就是正確的“數(shù)據(jù)由Component生成的概率”，亦可以當(dāng)做該Component在生成這個(gè)數(shù)據(jù)上所做的貢獻(xiàn)，或者說，我們可以看作這個(gè)值其中有這部分是由Component 現(xiàn)在實(shí)際上可以看作Component生成了這些點(diǎn)。由于每個(gè)Component都是一個(gè)標(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 行中最大的那個(gè)概率值所對(duì)應(yīng)的那個(gè)Component為 K-means那個(gè)cluster有一些點(diǎn)跑得比較遠(yuǎn)了。當(dāng)然，因?yàn)檫@個(gè)問題原本就是完全有MixtureGaussianDistribution，GMM（如果能求得全局最優(yōu)解的GMMK-means似（都可以追溯到EM）K-means值，就有可能得到很差的結(jié)果。對(duì)于K-meansGMMK-means個(gè)更流行的做法是先用K-means（已經(jīng)重復(fù)并取最優(yōu)值了）得到一個(gè)粗略的結(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)解，我們會(huì)看到，上一次說到的GaussianMixtureModel的迭代求解方法可以算是EM算法最典型的應(yīng)用，而最開始說的K-means其實(shí)也可以看作是GaussianMixtureModel的一個(gè)變種（固定所有的，并令即可）。然而EM實(shí)際上是一種通用的算法（或者說是框架），可GaussianMixtureModel起吧?；仡櫼幌挛覀冎耙鉀Q的問題：求以下Log-likelihoodfunction的 函數(shù)里面又有加和沒法直接求考慮一下GMM生成sampleGaussianDistribution里進(jìn)行sample。我們可以很自然地引入一個(gè)隱含變 個(gè)Component被選中了，那么 個(gè)元素置為1，其余的全為0。那么，再來看看，如果除了之前的sample 為。注意到 個(gè)元素為1的時(shí)候，亦即 Component被選中的時(shí)候，這個(gè)概率 前是一個(gè)和式再替換到最開始的那個(gè)Log-likelihoodfunction中得到新的同時(shí)關(guān)于sample和隱含變量的Log-likelihood:情況瞬間逆轉(zhuǎn)，現(xiàn)在和求和符號(hào)換了個(gè)位置，直接作用在普通的高斯分布利，完全依賴于一個(gè)我們的假設(shè)：隱含變量的值已知。然而實(shí)際上我們并不0sample的值因此我們可以把這個(gè)信息利用起來針對(duì)后驗(yàn)概率來取期望。前面，的每一個(gè)元素只有0和1兩種取值，因此按照期望的中間用貝葉斯定理變了一下形，最后得到的式子正是我們在漫談GMM中定義的。因此，對(duì)于上面那個(gè)可以直接求解的Log-likelihoodfunction ，我們只要用其期望亦即代替即可。到這里為止看起來是一個(gè)非常完美的方法不過仔細(xì)一看發(fā)現(xiàn)還有一個(gè)：之前的Log-likelihoodfunction可以直接求最大值是建立 是已知況下，現(xiàn)在雖然我們用來代替了 ，但是實(shí)際上是一個(gè)GMM的方法又推導(dǎo)了一遍。EM現(xiàn)在我們的討論將不局限于GMM并使用一些稍微緊湊一點(diǎn)的符號(hào)用 示所有的sample，同時(shí)用 過最大似然的方法估計(jì)出中的參數(shù) 很，但是要優(yōu)化卻很容易。這就是EM算法能夠解決的那一現(xiàn)在我們引入一個(gè)關(guān)于隱含變量的分布。注意到對(duì)于任意的，我們都可以對(duì)Log-likelihoodFunction作如下分解：和之間的Kullback-divergence。由于Kullback-Leiblerdivergence個(gè)分布完全相同的時(shí)候才會(huì)取到0。因此我們可以得到關(guān)系，亦即是的一個(gè)下界?，F(xiàn)在考慮EM的迭代過程，記上一次迭代得出的參數(shù)為，現(xiàn)在我們要取以令最大，由于并不依賴于因此的上限（在固定的時(shí)候）是一個(gè)定值，它取到這個(gè)最大值的條件就是Kullback-Leiblerdivergence為零，亦即等于后驗(yàn)概率。把它帶入到的表達(dá)式中可以得到其中const是常量，而是我們之前所得到的“同時(shí)包含sampleLog-likelihoodfunction這個(gè)對(duì)應(yīng)到EM中的“E”一步。在接下來的“M”一步中，我們講固定住分布，再選取合適的以將最大化，這次其上界也依賴于變量，并會(huì)隨著的增大而增大（因?yàn)槲覀冇星懊娴牟坏仁匠闪ⅲ?。一般情況下增大的量會(huì)比要多一些，這時(shí)候Kullback-Leiblerdivergence在新的參數(shù) 新回到“E”一步去求新的；另一方面，如果這里Kullback-LeiblerEM因此迭代的過程中得到的likelihood會(huì)逐漸近（至少是局部的）最優(yōu)值。另外，在M一步中除了用最大似然之外，也可以引入先驗(yàn)使用umaPosteriori(MAP)的方法來做。還有一些很的問題，甚至在迭代的過程中GeneralizedEM(GEM)。面我們就來舉一個(gè)用EM來做中文分詞的例子。這個(gè)例子來源于論文Self-supervisedChineseWordSegmentation。我在上次MSTC搜索引現(xiàn)在我們有一個(gè)字符序列，并希望得到一個(gè)模型（依賴于參數(shù)）能用來將其詞的序列。按照生成模型的方式來考慮，將看成是由生成的序列的話，我們自然希望找到那個(gè)生 的可能性最大的，亦即通過最大似然的方式來估計(jì)參數(shù) 然而我們不知道似然函數(shù)應(yīng)該如何去優(yōu)化因此我們引入latent 最大化即完成了EM的一次迭代。具體的做法通常是 的集合）按照N-gram分割（N-gram在講K-meds的那篇文章中介紹過）為，形成一個(gè)最初的辭典而模型的參數(shù)實(shí)際上就描述了各個(gè)N-gram的概率，初始值可以直接取為頻率值。有了辭典之后對(duì)于任意的，我們可以根據(jù)辭典枚舉出所有可能的分割，而每個(gè)分割的后驗(yàn)概率就是其中的單詞的概率乘積。其他的就是標(biāo)準(zhǔn)的EM算法的迭代步驟了。就是），并且這個(gè)過程是全自動(dòng)的，主要有兩個(gè)優(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é)果也就是一個(gè)accuracy，一個(gè)數(shù)字又不能畫成圖表之類的，看起來實(shí)在是沒意思，而且K-means結(jié)果來自clusteringusinglocalityindexing這篇，這篇實(shí)際上是提的另一種聚類方法（下次如果有機(jī)會(huì)也會(huì)講到），K-meansSpectralClusteringk Reuters-K-K-2349TDT2Reuters-21578K-meansSC(SpectralClustering)抽取了這兩個(gè)數(shù)據(jù)集中若干個(gè)類別（從210類）的數(shù)據(jù)進(jìn)行聚類，得出Clustering這里完勝K-means。以看到SpectralClustering算法的全貌：根據(jù)數(shù)據(jù)構(gòu)造一個(gè)Graph，Graph的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)數(shù)據(jù)點(diǎn)，將相似的點(diǎn)連接起來，并且邊的權(quán)重用于表示數(shù)據(jù)之間的相似度。把這個(gè)Graph用鄰接矩 K-meds中用的相似度矩陣作為 果中每一行所屬的類別就是原來Graph中的節(jié)點(diǎn)亦即最初的 其實(shí)，如果你熟悉DimensionalReduction（降維）的話，大概已經(jīng)看出來了，SpectralClusteringLaplacianEigenmap之后再做K-means的一個(gè)過程──聽起來土多了。不過，為什么要?jiǎng)偤媒档骄S呢？其實(shí)整個(gè)模型還可以從另一個(gè)角度導(dǎo)出來，所以，讓我們不妨先ImageProcessing（我好像之前有聽說我對(duì)這個(gè)領(lǐng)域深惡痛絕？）里有一個(gè)問題就是對(duì)圖像進(jìn)行Segmentation（區(qū)域分割），也就是讓相似的像素組成ImageProcessing這個(gè)問題，并且有不少方法和Clustering有密切聯(lián)系。比如我們在談Vectorzation的時(shí)候就曾經(jīng)用K-means來把顏色相似的像素聚類到一起，不feature（R、G、B一個(gè)像素，現(xiàn)在加入x、y兩個(gè)新的值）即可。另一方面，還有一個(gè)經(jīng)常被研究的問題就是GraphCut，簡單地說就是把一個(gè)Graph的一些邊切斷，讓他被打散成一些獨(dú)立的sub-Graph，而這些被切斷的邊的權(quán)值的總和就被稱為Cut值。如果用一張中的所有像素來組成一個(gè)Graph，并把（比如，顏色和位置上）相似的節(jié)點(diǎn)連接起來，邊上的權(quán)值表示相似程度，那么把分割為幾個(gè)區(qū)域的問題實(shí)際上等價(jià)于把Graph分sub-GraphCut切斷，表示比較相似的點(diǎn)被保留在了同一個(gè)sub-Graph中，而彼此之間聯(lián)系不cut（最小割）本身就是一個(gè)被廣泛研究的問題，并且有成算法來求解。只多替代的算法提出來，如RatioCut、NormalizedCut等。述清楚。將Graph表示為鄰接矩陣的形式，記為 ，其中是節(jié) 到節(jié)點(diǎn)的權(quán)值，如果兩個(gè)節(jié)點(diǎn)不是相連的，權(quán)值為零設(shè)和 為Graph的兩個(gè)子集（沒有交集），那么兩者之間的cut可先考慮最簡單的情況，如果把一個(gè)GraphMinimumcut就是要最小化（其中表示的補(bǔ)集）。但是由于這樣經(jīng)常會(huì)出現(xiàn)孤立節(jié)點(diǎn)被分割出來的情況，因此又出現(xiàn)了RatioCut：以及NormalizedCut其中表示中的節(jié)點(diǎn)數(shù)目，而。兩者都可算作的“大小”的一種度量，通過在分母上放置這樣的項(xiàng)，就可以有效地防止孤立點(diǎn)的情況出現(xiàn)，達(dá)到相對(duì)平均一些的分割。事實(shí)上，JianboShi的這篇PAMIpaper：NormalizedCutsandImageSegmentation正是把NormalizedCut用在圖像分割上了。搬出RatioCutNormalizedCutSpectralClustering是一個(gè)NP難問題，不方便求解，為了找到解決辦法，讓我們先來做做變形。令表示Graph的所有節(jié)點(diǎn)的集合，首先定義一個(gè)維向量 Usually,everyauthorjustcalls“his”matrixthegraph個(gè)有一個(gè)性質(zhì)就是：這個(gè)是對(duì)任意向量都成立的，很好證明，只要按照定義展開就可以得到了。把我們剛才定義的那個(gè)帶進(jìn)去，就可以得到1到和。由于是一個(gè)常量，因最小化RatioCut就等價(jià)于最小化，當(dāng)然，要記得加上附加條 以及問題轉(zhuǎn)化到這個(gè)樣子就好求了，因?yàn)橛幸粋€(gè)叫做Rayleighquotient的東西：征值并且極值 等于對(duì)應(yīng)的特征向量時(shí)取到由于是常數(shù)因此最小化實(shí)際上也就等價(jià)于最小化，不過由于的最小的特征值為零，并且對(duì)應(yīng)的特征向量正好為（我們這里僅考慮Graph是的情況），不滿足的條件，因此我們?nèi)〉诙€(gè)小的特征值，以及對(duì)應(yīng)的特征向量。們耍了一個(gè)把戲：之前的問題之所以NP難是因?yàn)橄蛄康脑刂荒苋芍岛椭械囊粋€(gè)，是一個(gè)離散的問題，而我們求的特征向量其中的元素可以是任意實(shí)數(shù)，就是說原來的問題限制放寬了。那如何得到原來的解呢？一個(gè)最簡單的辦法就是看零還是小于零，將他們分別對(duì)應(yīng)到離散情況的和不過我們也可以采取稍微復(fù)雜一點(diǎn)的辦法，用的K-means來將到此為止，已經(jīng)有SpectralClustering的了：求特征值，再對(duì)特征向量K-meansk（數(shù)學(xué)推導(dǎo)我就不再詳細(xì)寫了），我們就得到了和之前的SpectralClustering一模一樣的步驟：求特征值并取前k個(gè)最小的，將對(duì)應(yīng)的特征向量排列起來，再按行進(jìn)行K-means用類似的辦法，NormalizedCut也可以等價(jià)到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的時(shí)候?yàn)榱朔奖氵M(jìn)行聚類，更加強(qiáng)到“局部”的連通性，亦抓住了主要，忽略了次要的東西，Performance比傳統(tǒng)的K-means要好。SpectralClusteringK-means用LaplacianEigenmap進(jìn)行降維的后的結(jié)果，如果有機(jī)會(huì)，下次談DimensionalityReductionk（k很大），在這些低維的數(shù)據(jù)上做K-means運(yùn)算量非常小。但是對(duì)于原始數(shù)據(jù)直接做K-means的話，雖然最初的數(shù)據(jù)是稀疏矩陣，但是K-means中有一個(gè)求Centroid的運(yùn)算，就是求一個(gè)平均值：許多稀疏的向量的平均值求出來并不一致普通的K-means巨慢無比，而SpectralClustering等工序的算法則迅Clustering名字來源于Spectraltheory，也就是用特征分解來分析問題的UPDATE2011.11.23:LEKmeansSpectralCluster1thresholdingK類的情況，自然的類比就是降到K-1維，這也是和LDA保持一致。因?yàn)長aplacian（0），所以可以K0關(guān)于示例代碼：注意除非我在這里注明了是發(fā)布某個(gè)software或者package自己試驗(yàn)一下具體實(shí)現(xiàn)和改進(jìn)，否則可以直接找網(wǎng)上現(xiàn)成的的package，比如SpectralClustering可以考慮這個(gè)包。Clustering番外篇Dimensionality本文是“漫談Clustering系列”中的第7篇，參列的其他文章。例如，一個(gè)最簡單的將一個(gè)文本轉(zhuǎn)化為向量的方法如下：假設(shè)待提取的文檔是“Tobe,ornottobe:thatisthequestion:”，首先對(duì)其進(jìn)行一些預(yù)處理，例如去掉單詞的時(shí)態(tài)后綴、濾掉標(biāo)點(diǎn)符號(hào)等，得到“tobeornottobethatbethequestion”。統(tǒng)計(jì)三個(gè)維度所對(duì)應(yīng)的單詞出現(xiàn)的頻率：to2，be3次，the1該文檔對(duì)應(yīng)的向量即[2,3,1]不過事實(shí)上我們通常會(huì)做更復(fù)雜一些的處理例如如果你是在做sentimentysis那么你通常會(huì)更加關(guān)注語氣很重的詞比如“bad”“terrible”、“awesome”等的重要性就比普通的詞要大此時(shí)你可以為每一個(gè)維度設(shè)一個(gè)權(quán)重，例如，給“bad”設(shè)置權(quán)重2，那么出現(xiàn)3次的話，向量在該維度對(duì)應(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)值的維度，并且處理過后一個(gè)函數(shù)，其輸入是一個(gè)D維的向量，輸出是一個(gè)M維的向量。reconstructionerror reconstructionerror另外式是簡單地使用variance來衡量所包含信息量，例如，我們要把D1variance 是降維函數(shù)。推而廣之，如果是降為2維，那么我希望第2維去關(guān)注第1維之外的variance，所以要求它在與第一維垂直的情況下也達(dá)到variance最大化。以此類推。然而當(dāng)我們把降維函數(shù)限定維線性的時(shí)候兩種途徑會(huì)得到同樣的結(jié)果，就是被廣泛使用的PrincipalComponentsysis(PCA)。PCA的降維函數(shù) 來表示，因此，一個(gè)D維的 經(jīng)過線性變換之后得到一個(gè)M維向量，就是降維的結(jié)果。 維的數(shù)據(jù)矩陣，目標(biāo)是使其covariance （covariance），當(dāng)然矩陣不是一個(gè)數(shù)，不能直接最化，如果我們采用矩陣的Trace 求最大化只需要求出的特征值和特征向量將M個(gè) 這也就是PCA的求解過程，得到的降維矩陣 如果熟悉LatentSemanticysis(LSA)的話，大概已經(jīng)看出PCA和SingularValueposition(SVD)以及LSA之間的關(guān)系了。以下這張圖（引自《TheElementsofStatisticalLearning》）可以直觀地看出來PCA做了什么，對(duì)于一些原始為二維的數(shù)據(jù)，PCAvariancePCA檢索等各個(gè)領(lǐng)域，其地位類似于聚類中的K-means，在現(xiàn)在關(guān)于降維等算法的baseline，PCA個(gè)就是PCA降維是線性變換，雖然線性變換計(jì)算方便，并且可以很容易地推廣其中一個(gè)就是KernelPCA，用KernelTrick來將PCA推廣到非線性的情況。另外，PCAGaussianlatentvariable模型，它假定數(shù)據(jù)的mean和variance是重要的特征，并依靠covariance一個(gè)典型的問題就是做聚類或分類，回想我們之前談過的SpectralClustering，就是使用LaplacianeigenmapK-meansPCAreconstructionerror分不同類別的。如果我們有訓(xùn)練數(shù)據(jù)的類別，則可以用FisherLinearDiscriminantysis來處理這個(gè)問題。同PCA一樣，F(xiàn)isherLinearDiscriminantysis也是一個(gè)線性映射模型VariancevariancevariancePatternClassification》這本書的第三章ComponentysisandDiscriminants。LinearDiscriminantysis就沒有辦法了。不過，如果我們假設(shè)原始的數(shù)MDS三維或者二維，用于做visualization。MDSSpectralClusteringLaplacianEigenmapMDS，LE相似度矩陣，不過這里通常要求這個(gè)相似度矩陣具有局部性質(zhì)，亦即只考慮局部領(lǐng)域內(nèi)的相似性，如果點(diǎn)和距離太遠(yuǎn)的話，應(yīng)該為零。1.對(duì)每個(gè)點(diǎn)選取k個(gè)最接近的點(diǎn)作為鄰居，與其他的點(diǎn)的相似性則置為零。這里需要注意的是LE要求相似度矩陣具有對(duì)稱性，因此，我們通常會(huì)在 于的k個(gè)最接近的鄰居且/或反之的時(shí)候，就保留的值，否則置為 那么會(huì)相對(duì)比較大，這樣如果映射過后 就會(huì)被權(quán)重放大，因此最小化目標(biāo)函數(shù)就保證了原來相近的點(diǎn)在映射過后令為將的每一行加起來所得到的對(duì)角陣，而 稱作是拉斯矩陣，通過求解如下的特征值問題易知最小的那個(gè)特征值肯定是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ù)分布在一個(gè)嵌套在高中的低維流LaplacianMatrix則是流形的LaplaceBeltramioperator的LaplacianEigenmap這里做地展開了，下面看一個(gè)比較直觀的例子SwissRoll。SwissRoll是一個(gè)像面包圈一樣的結(jié)構(gòu)，可以看作一個(gè)嵌套在三中的二SwissRollSwissRollLaplacianEigenmapPCASwissRoll看到LE成功地把這個(gè)流形展開把在流形上屬于不同位置的點(diǎn)映射到了不同的地方，而PCA的結(jié)果則很糟糕，幾種顏色都混雜在了一起。LocallyLinearEmbeddingLE 應(yīng)當(dāng)?shù)扔诹?。這之后再把 際上，從理論上也可以得出二者之間的聯(lián)系（LE對(duì)應(yīng)于 而LLE對(duì)應(yīng)于），如果感的話，可以參考LaplacianEigenmapsforDimensionalityReductionandDataRepresentation這篇里的對(duì)比。下面是兩種方法在SwissRoll數(shù)據(jù)上的結(jié)果，也是非常相似的：影矩陣，這個(gè)結(jié)果可以保存下來，在之后對(duì)任意向量進(jìn)行投影，而LE和LLEPCALELLE別叫做LocalityPreservingProjection和NeighborhoodPreservingEmbedding。LPPPCA陣來表示，于是LE的目標(biāo)函數(shù)變?yōu)榈玫降陌凑仗卣髦祻男〉酱笈判虻奶卣飨蛄烤徒M成映射矩陣LELE里的矩陣在乘以之后通常就不再稀疏了，計(jì)算量會(huì)變得比較大，這個(gè)問題可以使用SpectralRegression的方法來解決，參見SpectralRegression:AUnifiedApproachforSparseSubspaceLearningpaperKernelTrickLPPLELLENPE另外，雖然LE是unsupervised的，但是如果訓(xùn)練數(shù)據(jù)確實(shí)有可用，也是的決策過程其實(shí)人是可以“看到”或者說“理解”的，但是SVM就不那么法發(fā)展出“智能”來啊^_^bbClustering5Hierarchical本文是“漫談Clustering系列”中的第8篇，見本系列的其他文不過覺得HierarchicalClustering這個(gè)話題我能說的東西應(yīng)該不多，所以還是先寫了吧（我準(zhǔn)備這次一個(gè)公式都不貼）。Hierarchicalnaive不過言歸正傳，這里要說的HierarchicalClustering聽上去很，不過其實(shí)HierarchicalClustering的想法很簡單，主要分為兩大類：agglomerative（自底向上）divisive（自頂向下）。首先說前者，看起來很簡單吧？其實(shí)確實(shí)也是比較簡單的，不過還是有兩個(gè)問題需要problemdependentSingleLinkage：又叫做nearest-neighbor的兩個(gè)點(diǎn)的距離作為這兩個(gè)集合的距離，容易造成一種叫做Chaining的效離比較近就被合并了，并且這樣合并之后Chaining效應(yīng)會(huì)進(jìn)一步擴(kuò)大，最后會(huì)得到比較松散的cluster。CompleteLinkage：這個(gè)則完全是SingleLinkage的，取兩個(gè)集SingleLinkageCompleteLinkage的方法。整個(gè)agglomerativehierarchicalclustering的算法就是這個(gè)離最近的兩個(gè)點(diǎn)，需要一個(gè)雙重循環(huán)，而且GroupAverage計(jì)算距離的時(shí)候也123456789123456789def#makeacopy,donottouchtheoriginallistnodes