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

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