文章編號 1004-6410（2012）03-0045-04基于 K 均值聚類的定位算法分析李煒（廣西工學(xué)院 計算機學(xué)院，廣西 柳州 545006）摘 要：在描述了聚類算法的基本思想和概念的基礎(chǔ)上，介紹了一種常見的聚類算法K 均值和 K 中心點聚類算法，通過處理認(rèn)知無線電網(wǎng)絡(luò)中主用戶定位在海量數(shù)據(jù)中應(yīng)用 K 均值聚類算法，對該算法進(jìn)行分析，仿真結(jié)果表明：與傳 統(tǒng)的主用戶定位算法相比，使用 K 均值聚類算法能夠有效地提高定位精度和降低定位算法的復(fù)雜度.關(guān)鍵詞：聚類分析；K 均值；認(rèn)知無線電；定位算法中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A引言數(shù)據(jù)挖掘（Data mining）是通過數(shù)理方法在數(shù)據(jù)庫中進(jìn)行知識發(fā)現(xiàn)的一個方法.數(shù)據(jù)挖掘一般是指運用 特定的算法對海量的數(shù)據(jù)資料進(jìn)行分析和處理，從而搜索出數(shù)據(jù)資料中隱藏的、有用的數(shù)據(jù)信息來為人們 提供有價值的知識. 數(shù)據(jù)挖掘技術(shù)能夠從數(shù)據(jù)庫和信息庫中的數(shù)據(jù)資料中發(fā)現(xiàn)數(shù)據(jù)間的隱含關(guān)系并提取 出潛在的、有效的模式或者知識，通過統(tǒng)計分析處理、機器學(xué)習(xí)和模式識別等諸多方法來實現(xiàn)上述目標(biāo).聚類分析是數(shù)據(jù)挖掘在實際應(yīng)用中的主要方法之一1.一般情況下，在聚類算法中，將數(shù)據(jù)或者對象的 集合劃分成不同的簇（或者成為聚類集合），每一個簇（聚類）中的數(shù)據(jù)或者對象擁有較高的相似性，而不同的簇（聚類）中數(shù)據(jù)或者對象具有較大的差異性.聚類的目標(biāo)就是依照某種特定相似度量對數(shù)據(jù)或者對象 進(jìn)行劃分.聚類算法可以應(yīng)用到很多學(xué)科領(lǐng)域，如計算機科學(xué)、統(tǒng)計學(xué)、商務(wù)、生物學(xué)、經(jīng)濟(jì)學(xué)等領(lǐng)域.通過聚類算法，人們可以在不同的領(lǐng)域中發(fā)現(xiàn)數(shù)據(jù)分布密集和稀疏的區(qū)域，發(fā)現(xiàn)數(shù)據(jù)或者對象間的相互關(guān)系，從而對該領(lǐng)域的數(shù)據(jù)樣本進(jìn)行有效的劃分.聚類分析計算方法主要有以下幾種：劃分法（Partitioning Methods）、層次法（Hierarchical Methods）、基于 密度的方法（Densitybased Methods）.劃分法就是對給定的 N 個單元或者紀(jì)錄的數(shù)據(jù)集，劃分成 K 個分組， 每一個分組就代表一個聚類，其中 KN.且每一個分組至少包含一個單元或者紀(jì)錄，每一個數(shù)據(jù)單元或者 紀(jì)錄屬于且僅屬于一個分組，常見的算法如：K 均值算法，KMEDOIDS 算法、CLARANS 算法等；層次法是 對給定的數(shù)據(jù)集進(jìn)行層次似的分解直到滿足某種條件為止，具體又可分為“自底向上”和“自頂向下”兩種 方案，常見算法有：BIRCH 算法、CURE 算法、CHAMELEON 算法等；基于密度的方法區(qū)別于其他方法之處 在于，它不是基于各種各樣距離，而是基于密度.這樣算法的優(yōu)勢在于能夠克服基于距離的算法只能發(fā)現(xiàn) “類圓形”的聚類缺點.該方法的基本思想就是只要一個區(qū)域中的點的密度大過某個閥值，就把它加到與之 相近的聚類中去，其代表算法有 DBSCAN 算法、OPTICS 算法等24.在眾多的聚類方法中，均值方法是一種最經(jīng)典的也是應(yīng)用最廣泛的聚類方法57，該方法以各類樣本的中心為代表不斷迭代，只適用于數(shù)值屬性數(shù)據(jù)的聚類，對超球形和凸?fàn)顢?shù)據(jù)有很好的聚類效果.0收稿日期：2012-08-28基金項目：廣西自然科目基金（2011gxhsfa018162）資助.作者簡介：李 煒，碩士，助理實驗師，研究方向：信號與信息處理，數(shù)據(jù)挖掘，E-mail:.1K 均值聚類算法11K 均值聚類算法基本思想K 均值聚類算法是，假設(shè)含有 N 個數(shù)據(jù)（對象）的集合 X（x1，x2，xn），將這個數(shù)據(jù)集合劃分為 K 個聚K類中心集合 C（c1，c2， ，ck）的問題.假設(shè)第 k 類的樣本數(shù)目為 Nk，則 N=Nk，每類 Ck 的均值為（m1，m2，k = 1Nk，mk），則 mk= 1 xi，k1，2，K. K 均值聚類算法是基于誤差平方和準(zhǔn)則的，即 K 均值聚類算法的最小Ni = 1目標(biāo)函數(shù)為KNkJ= xi-mk2（1）k = 1 i = 1K 均值聚類算法首先在數(shù)據(jù)集合中隨機選取 K 個數(shù)據(jù)點作為 K 個聚類的初始類中心，數(shù)據(jù)集合中每 個數(shù)據(jù)點根據(jù)計算其與各個聚類中心的距離，并將其被劃分到距離最近的聚類中心所在的類中，從而獲得 了 K 個聚類的初始分布狀態(tài)集合.當(dāng)每個數(shù)據(jù)點劃分到相應(yīng)的聚類中心后，對分配完的每一個聚類集合計 算新的類中心，然后繼續(xù)對集合內(nèi)的數(shù)據(jù)點進(jìn)行數(shù)據(jù)分配，進(jìn)行若干次迭代分配，若聚類中心不再發(fā)生變 化，則說明集合中的數(shù)據(jù)對象全部分配到自己所在的類中，那么聚類準(zhǔn)則函數(shù)收斂，完成了數(shù)據(jù)集合的聚 類，否則繼續(xù)進(jìn)行迭代過程，直至算法收斂.該聚類算法的一個特點就是在每一次的迭代過程中通過找到 新的聚類中心，對所有數(shù)據(jù)點進(jìn)行重新分配和調(diào)整，進(jìn)入下一次的迭代過程，若在某一次迭代過程中，所有 數(shù)據(jù)點的位置沒有發(fā)生變化，也即相應(yīng)的聚類中心也沒有變化，那么此時說明聚類準(zhǔn)則函數(shù)已經(jīng)收斂，實 現(xiàn)了聚類算法.12K 均值聚類算法的基本流程step1 從數(shù)據(jù)集合 X 中隨機取 K 個元素，作為 K 個聚類的各自的類中心；step2 分別計算集合 X 中剩下的元素到個聚類中心的距離（相異度），將這些元素分別劃分到離其距離 最近（相異度最低）的類中；step3 根據(jù)聚類結(jié)果，重新計算 K 個聚類各自的類中心，通過是計算聚類中所有元素各自維度的算術(shù) 平均值；step4 將 X 中全部元素按照新的中心重新進(jìn)行分配調(diào)整； step5 重復(fù) step2，直到所有數(shù)據(jù)點和聚類中心不再變化； step6 完成聚類迭代，將結(jié)果輸出.2均值聚類在主用戶定位算法中的具體應(yīng)用21算法模型文獻(xiàn)8詳細(xì)介紹了基于信號強度的多主用戶定位的 EM 算法，但是，該 EM 算法需要進(jìn)行復(fù)雜的矩 陣計算，例如求解矩陣的逆運算，算法復(fù)雜度很高.如果采用基于均值聚類的主用戶定位算法，可以很好地 降低算法的復(fù)雜度，減小主用戶的定位誤差，在工程上可以更好實現(xiàn).在認(rèn)知無線電系統(tǒng)結(jié)構(gòu)中，整個電磁空間被劃分為兩個層面：一層為主用戶網(wǎng)絡(luò)層；另一層為有認(rèn)知 用戶構(gòu)成的認(rèn)知網(wǎng)絡(luò)層.且該系統(tǒng)結(jié)構(gòu)中包含了 M 個待檢測的主用戶發(fā)射機和 N 個感知節(jié)點.感知節(jié)點的 位置已知，而主用戶發(fā)射機位置為未知，表示為 =1 2 MT，其中 i=xi，yi表示第 i 個主用戶發(fā)射機的 位置.這里假設(shè)每個發(fā)射機的發(fā)射功率相同為 P0，而且主用戶發(fā)射機的個數(shù)為已知；因此，到達(dá)感知節(jié)點處 的接收功率可以表示為M2ri= iP0d02， i1，2，N2（ ） +ni（2）m=1 dim其中，ri 表示到達(dá)第個感知節(jié)點處的功率；i 表示與發(fā)射接收天線增益和波長有關(guān)的一個損耗常數(shù) 1，這里取為 1；d0 為距離主用戶發(fā)射機的參考距離，如取為 1 m；d0 為第 i 個感知節(jié)點與第 m 個主用戶發(fā)射機 之間的二維距離.這里采用一個簡單自由空間中的路徑損耗模型，功率隨路徑距離是平方衰減的關(guān)系.ni 為一個零均值高斯隨機變量，其方差為 2.同時假設(shè)每個主用戶發(fā)射機發(fā)射的信號之間及與接收機噪聲信號 之間均為不相關(guān)，且已知主用戶和感知節(jié)點具體位置，可以計算出在感知節(jié)點處接收到的來自該主用戶的功率.22基于聚類的迭代多用戶定位算法對多個主用戶的定位就是根據(jù)從若干個感知節(jié)點處觀察到的功率 ri，i1，2， ，N，來反推各個主用戶發(fā)射機的二維空間位置 ，這一問題實際上可以等效為最大似然參數(shù)估計問題，即：尋找一組空間位置，使得在多個已知位置的感知節(jié)點處觀察到接收功率為 ri，i1，2，N 的概率最大.即贊=argmax P（r | ）（3）其中， 贊 表示對個發(fā)射機二維空間位置的估計值.P（r | ）表示在 N 個感知節(jié)點處接收到功率為 r=r1，r2，rN的概率.對式（2）稍作變形，可得MMri=（ iP0d0 22ni ）=ri，m2（ ） + M（4）dim=1mm=1將噪聲帶來的接收功率平均分成 M 份， 分別和來自不同主用戶發(fā)射機的功率結(jié)合起來， 構(gòu)成 ri,m=22iP0d0 + ni，m1，2，M，表示只有第 m 個主用戶發(fā)射機存在時，在第 i 個感知節(jié)點處接收到的功率.2di （m） M）根據(jù)公式（2），在已知 M 個主用戶發(fā)射機位置的情況下，可以得到對 ri,m 的估計值:M iP0d0 1 iP0d0 22（ri- d 2（n） ） ）ri（n）,m =E d 2（n） ） + M（5）i mm=1i m其中，ri 為在一段持續(xù)的時間內(nèi)由感知節(jié)點觀察到的多個接收功率樣本.觀察（5）式，當(dāng) （n） 與真實的m主用戶發(fā)射機位置非常接近時，所得到的ri（n）中前一項為與距離有關(guān)的功率分量，第二部分則相當(dāng)于接收,m機噪聲帶來的功率成分，其在整個功率中所占比重非常小；因此，ri（n）可以近似為與距離成反比的量，r （n）,mi,m 1 2（ iP0d0） 2 ，可得，由d （n）為對發(fā)射機 m 與感知節(jié)點 i 之間的距離估計（該距離存在偏差）.當(dāng) N 個感知節(jié)點i,mri（n）i,m到 M 個發(fā)射機的距離全部獲得后，將感知節(jié)點集合 P set=（X1，Y1），（X2，Y2）， ，（XN，YN）作為圓心，估計出的感知節(jié)點到認(rèn)知用戶發(fā)射機之間的距離 D set=r11，r21，rN1，r12，r22，rN2作為半徑畫圓，這時可以得到 N*M 個圓，找出所有圓的交點并將交點的位置保持到集合 C set=（x1 ，x1 ），（x2 ，x2 ）， ，（xj ，xj ）中，對這個交點集合中的交點做 M 個目標(biāo)的 K 均值聚類，可以得到 M 個主用戶發(fā)射機位置集合 R set=（x1，y1），（x2，y2），（xM，yM），通過迭代的方法重復(fù)計算主用戶的位置，直到新的位置不再變化，這時可以認(rèn)為這個位置集合是估計出主用戶發(fā)射機的空間位置.仿真結(jié)果分析利用上面的思想，提出的多主用戶定位算法的迭代過程如下：1） 隨機生成個主用戶位置的初始估計贊0，設(shè)置循環(huán) k 為 1；32） 利用在 N 個感知節(jié)點處觀察到的接收功率，計算ri（n），i1，2，N m1，2，M 和d （n）；,mi,m3） 以感知節(jié)點為圓心，以di（n），i1，2，N，m1，2， ，M，為半徑可以畫出 N*M 個圓，并求出所有圓之,m間的交點集合，并保存到集合 C 中；4） 對 C 中的點進(jìn)行 M 個目標(biāo)的 K 均值聚類運算，獲得新的主用戶的位置信息贊（n+1）=贊12M ；（n+1）贊 （n+1）贊 （n+1） T5） 計算 A=（贊（n+1）-贊（n）（贊（n+1）-贊（n）T，求矩陣 A 的對角線元素之和，即 e=Trace（A），Trace（A）為矩陣的跡.為迭代前后兩次的距離收斂程度；6） 如果 e，停止迭代，此時的贊（n+1）=贊12M ，即為所求的 M 個主用戶的空間位置，否則，令 k=k+1，重復(fù) step2）.為了方便仿真多主用戶定位算法， 假設(shè)認(rèn)知無線電環(huán)境結(jié)構(gòu)圖中有兩個主用戶發(fā)射機和 1020 個認(rèn) 知用戶節(jié)點；并且，主用戶發(fā)射機和認(rèn)知用戶節(jié)點隨機分布在一個 1 km*1 km 的平面區(qū)域內(nèi)，而信道參數(shù) i=1，d0=1，P0=1，迭代收斂系數(shù)為 =0.02.從圖 1 中可以看出，認(rèn)知用戶節(jié)點的數(shù)量和信噪比是影響主用戶數(shù)量估計準(zhǔn)確性的幾個因素.當(dāng)信噪比足夠高，則數(shù)量估計算法就能保證很高的精度.圖 1 一共有 20 個認(rèn)知用戶節(jié)點.可以看出，估計出的主用 戶位置與其真實的位置十分接近.圖 2 是 EM 算法和迭代 K 均值聚類的主用戶定位算法的均方距離定位誤差，信噪比為 10 dB，從圖中 可以看出上文提出的迭代 K 均值聚類的多主用戶定位算法效果要優(yōu)于傳統(tǒng)的 EM 定位算法.（n+1） 贊 （n+1）贊 （n+1） T1 0009008007006005004003002001000.25EMK 均值聚類0.05000468101214161820100 200 300 400 500 600 700 800 900 1 000認(rèn)知節(jié)點的數(shù)量注： 認(rèn)知用戶節(jié)點的位置； 主用戶的真實位置； 由定位算法估計出的主用戶位置.圖 1 定位算法仿真結(jié)果圖結(jié)論圖 2 信噪比 10 dB 時 EM 算法和迭代 K 均值聚類算法的性能比較圖4通過在處理認(rèn)知無線電網(wǎng)絡(luò)中主用戶定位是海量數(shù)據(jù)中應(yīng)用 K 均值聚類算法對該算法進(jìn)行分析.仿真結(jié)果表明，在認(rèn)知無線電網(wǎng)絡(luò)主用戶定位算法中，聚類算法較傳統(tǒng)的 EM 定位算法的算法復(fù)雜度低，定 位精度要高.參考文獻(xiàn)1 賀玲，吳玲達(dá)，蔡益朝數(shù)據(jù)挖掘中的聚類算法綜述J計算機應(yīng)用研究，2007， 24（1）：10132 謝崇寶，袁宏源最優(yōu)分類的模糊劃分聚類改進(jìn)方法J系統(tǒng)工程，1997， 15（1）： 583633 Rudi L Cilibrasi， Paul MB VitanyiA Fast Quartet tree heuristic for hierarchical clustering J Pattern recognition， 2011，44（3）：6626774 武佳薇，李雄飛，孫濤，等鄰域平衡密度聚類算法J計算機研究與發(fā)展，2010， 47（6）：104410525 Kanungo T， Mount D M A Local Search Approximation algorithm for kmeans clusteringJ Computational Geometry， 2004， 28（2 3）：891126 梁鑫聚類分析算法在路面破損檢測中的應(yīng)用J廣西工學(xué)院學(xué)報 ，2008，19（4）：51537 歐陽浩模糊聚類分析在產(chǎn)品質(zhì)量評估中的應(yīng)用J廣西工學(xué)院學(xué)報 ，2008，19（4）：8385.8 J K Nelson， and M R Gupta， An EM Technique for Multiple Transmitter Localization in Proc CISSC， 2007 Baltimore， MD（下轉(zhuǎn)第 76 頁）均方誤差/km2A method for fast pavement cracking detection based on the biologicalinspired modelXU Yiyia，TANG Peihea，NI Zhipingb（aCollege of Computer Engineering； bLushang College，Guangxi University of Technology，Liuzhou 545006， China）Abstract： Due to the complexity of shape and apparent differences of pavement cracks， it is difficult tocharacterize them with definite features The wavelet， Gabor transform and its functions are usually predefined and cannot adapt to the characteristics of the pavement crack images This paper proposes a novel joint maximization recognition algorithm in the resilient area， which is based on the characteristics of biologically inspired model（BIM） The algorithm uses the elastic neighborhood， the first adjacent neighbors domain or eight neighborhood image segmentation Adaboost classifier is introduced in each region to select and retain key information， get rid of unwanted or negative information Its eigenvectors can reflect the information in the original image comprehensively and its low computational complexity is helpful in real time applications The experimental results show that the overall recognition rate of the proposed method in pavement cracks is up to 9913， and its fast response time fully demonstrate the effectiveness of this methodKey words