Kmeans聚類算法以及實現(xiàn)

Kmeans聚類算法以及實現(xiàn)一、Kmeans算法k-means算法接受參數(shù)k；然后將事先輸入的n個數(shù)據(jù)對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。K-means算法是最為經(jīng)典的基于劃分的聚類方法，是十大經(jīng)典數(shù)據(jù)挖掘算法之一。K-means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。假設(shè)要把樣本集分為c個類別，算法描述如下：（1）適當選擇c個類的初始中心；（2）在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類；（3）利用均值等方法更新該類的中心值；（4）對于所有的c個聚類中心，如果利用（2）（3）的迭代法更新后，值保持不變，則迭代結(jié)束，否則繼續(xù)迭代。該算法的最大優(yōu)勢在于簡潔和快速。算法的關(guān)鍵在于初始中心的選擇和距離公式二、算法流程首先從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù).k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。Kmeans算法實現(xiàn)的步驟具體描述為：（1）從療個數(shù)據(jù)對象中任意選取k個對象作為初始的聚類中心。⑵分別計算每個對象到各個聚類中心的距離，把對象分配到距離最近的聚類中。（3）所有對象分配完成后，重新計算k個聚類的中心。⑷與前一次計算得到的k個聚類中心比較，如果聚類中心發(fā)生變化，轉(zhuǎn)（2），否則轉(zhuǎn)（5）。（5）輸出聚類結(jié)果。實現(xiàn)的流程框圖為首先從n個數(shù)據(jù)對象中任意選擇k個對象作為初始聚類中心；而對于所剩下的其它對象，則根據(jù)他們與這些聚類中心的相似度（距離），分別將他們分配給與其最相似的（聚類中心所代表的）聚類。然后再計算每個所新聚類的聚類中心（該聚類中所有對象的均值）。不斷重復這一過程直到標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù)，具體定義如下：其中E為數(shù)據(jù)庫中所有對象的均方差之和；p為代表對象的空間中的一個點；m，為聚類G的均值（p和m，均是多維的）.上述公式所示聚類標準旨在使所獲得的k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類間盡可能的分開。三、設(shè)計實現(xiàn)K-Means算法是聚類算法的一種，它通過計算樣本數(shù)據(jù)點之間的邏輯距離來判斷某個樣本數(shù)據(jù)點屬于哪一個簇，算法最終的目的是要把用于算法的樣本數(shù)據(jù)點分配到K個簇中，使簇內(nèi)的點有較大的相似度，而簇間的點有較小的相似度。K-Means中的K表示聚類中心的個數(shù)，在算法運行過程中，要反復掃描所有樣本數(shù)據(jù)點，要計算每個非中心數(shù)據(jù)點與某個聚類中心點的距離，并將這個數(shù)據(jù)點歸為與其距離最小的那個聚類中心對應的簇之中。每掃描一次就要重新計算每個聚類中心點的位置。當聚類中心點的位置變化在一定的閾值之內(nèi)的時候停止處理，最后就可以得到K個簇，并且簇中每個樣本數(shù)據(jù)點到本簇的中心的距離都小于到其它簇中心的距離。本程序使用C++實現(xiàn)算法本身，然后用C#調(diào)用C++函數(shù)完成了數(shù)據(jù)的傳送和接收算法的輸出并可視化結(jié)果。并且數(shù)據(jù)是保存在Access數(shù)據(jù)庫中的一個sample表格中然后通過字符串連接數(shù)據(jù)庫讀入數(shù)據(jù)也可以使用其他數(shù)據(jù)庫，例如sqlserver，修改相應的字符串連接語句即可。下面主要介紹一個導出的函數(shù)DataMining_KMeans，這個函數(shù)要接收C#傳過來的原始數(shù)據(jù)、K值及其它參數(shù)，同時還要將處理的結(jié)果賦值給引用參數(shù)以便在C#中可以接收到處理結(jié)果。DataMining_KMeans函數(shù)的原型如下：/**@Author:YinPSoft*@param:*raw:原始數(shù)據(jù)*count:數(shù)據(jù)點個數(shù)*K:聚類中心個數(shù)*means:初始聚類中心*minOffset:聚類中心的最小偏移量，用于控制聚類處理的精度。*times:最大迭代次數(shù)*c:每個聚類的數(shù)據(jù)點索引值*sizes:每個聚類的容量*finalMeans:最終的聚類中心位置*/voidDataMining_KMeans(double*data,intcount,intK,int*means,doubleminOffset,inttimes,int*c,int*sizes,double*finalMeans);在這個原型聲明中可以看到初始聚類中心點要從外部輸入，從外部輸入這種方式有更大的靈活性，當有特定的初始聚類中心生成策略的時候可能通過這個策略來生成中心點，而沒有策略的時候也可以通過隨機來生成。初始聚類中心的值可以很大程度地影響到整個算法的效率，適當?shù)倪x擇聚類中心點可以減少算法的迭代次數(shù)。接著是初始化：for(i=0;i<K;i++){vector<int>cluster;(cluster);(*(means+i));(*(means+i)).isMean=true;(*(means+i)).isVirtual=false;上面的代碼有兩個目的：一是初始化vector<int>數(shù)組用于存放K個簇的樣本點索引；二是將外部傳進來的K個聚類中心點添加到dots對象之中，dots對象是vector<Dot2D>類型的。在DataMining_KMeans最開始就要通過PreProcessor函數(shù)將外部傳進來的數(shù)據(jù)點封裝成vector<Dot2D>的對象，在這里是dotsoDot2D的定義如下，isMean和isVirtual是數(shù)據(jù)點的兩個標志，前者用于標識這個數(shù)據(jù)點是否是聚類中心，后者用于表示這個點是不是虛擬數(shù)據(jù)點，虛擬數(shù)據(jù)點在這里意為這個點的位置是通過計算得到，而不是原始數(shù)據(jù)中的數(shù)據(jù)點。實際上，在這個算法中，虛擬數(shù)據(jù)點都是在處理過程中得到的聚類中心點，因為每一輪計算完成后要重新計算聚類中心位置，而這個計算出來的位置很可能不同于原始數(shù)據(jù)中的任何一個點，所以要把這些點保存下來用于下一輪的計算：typedefstructDot(doublex;doubley;boolisMean;boolisVirtual;}Dot2D,*Ptr_Dot2D;接下來就是一個while循環(huán)，反復地掃描樣本數(shù)據(jù)點并將其分配K個簇中。在這個while循環(huán)中包括兩大部分，首先就是計算并比較數(shù)據(jù)點與聚類中心的距離并進行分配；其次就是重新計算聚類中心。代碼如下：for(i=0;i<count;i++)(if(!(i).isMean&&!(i).isVirtual)(dist=INFINITE_DISTANCE;for(j=0;j<K;j++)

(term=Distance(dots[i],dots[meanIndex[j]]);if(term<dist)(dist=term;ush_back(i);}}對所有數(shù)據(jù)點的掃描計算的前提是這些數(shù)據(jù)點不是聚類中心并且也不是虛擬數(shù)據(jù)點。然后將中間距離變量設(shè)置一個初值，接下來的for循環(huán)就要計算當前這個數(shù)據(jù)點與每個聚類中心的距離，如果當前點到第K個聚類中心的距離是最小的，那么就把它的索引值存放到clusters的第K個vector<i口七>對象中。當所有的樣本數(shù)據(jù)點都被分配到K個簇中以后就要重新計算中心點的位置，代碼如下：for(i=0;i<K;i++)(maxminvalues=FindMaxMinValues(dots,(i));=(0)+(2))/;=(1)+(3))/;=true;=true;term=Distance(newMean,dots[meanIndex[i]]);flag=(term>minOffset)true:flag;(i)).isMean=false;(newMean);*(finalMeans+i)=;*(finalMeans+i+K)=;(i)()-1;上面的代碼用于計算新的聚類中心點的位置，并覆蓋之前的聚類中心位置。在這個算法中通過計算簇所占有的矩形區(qū)域的中心點來作為新的聚類中心點的位置。在這個for循環(huán)中還有一件事情就是要計算新的聚類中心點與前一輪的聚類中心點的距離或者稱為聚類中心點的位移，在函數(shù)原型中我們設(shè)置了這個位移的最小值，當K個位移都小于這個值的時候就要結(jié)束算法處理。另外每次進入while循環(huán)的時候要清空clusters對象，否則(i)()-1;以上就是K-Means算法實現(xiàn)C++部分的主要代碼，也是這個演示程序的核心部分。除了算法實現(xiàn)部分之外就是算法結(jié)果的展示了。另一個項目用于向算法傳送原始數(shù)據(jù)以及接收算法的輸出并可視化結(jié)果。在項目中要調(diào)用C++函數(shù)，方法是通過.NET的P/Invoke調(diào)用，其代碼如下：///<summary>///K-Means聚類分析///</summary>///<paramname="rawdata">KMeans原始數(shù)據(jù)</param>///<paramname="rows">數(shù)據(jù)點個數(shù)</param>///<paramname="K">聚類個數(shù)</param>///<paramname="means">初始聚類中心</param>///<paramname="minOffset">聚類中心的最小位移量</param>///<paramname="times">最大迭代次數(shù)，-1為不控制</param>///<paramname="result">聚類劃分結(jié)果</param>>///<paramname="finalMeans">返回白勺最終聚類中心</param>///<paramname="size">表示第一個參數(shù)白勺長度</param>///<paramname="finalMeans_size">表示第九個參數(shù)的長度</param>[DllImport(,EntryPoint="DataMining_KMeans",CharSet=]publicstaticexternvoidDataMining_KMeans([MarshalAs,SizeParamIndex=9)]double[]rawdata,introws,intK,[MarshalAs,Siz