文章編號 1004-6410（2012）03-0045-04基于 K 均值聚類的定位算法分析李煒（廣西工學院 計算機學院，廣西 柳州 545006）摘 要：在描述了聚類算法的基本思想和概念的基礎上，介紹了一種常見的聚類算法K 均值和 K 中心點聚類算法，通過處理認知無線電網絡中主用戶定位在海量數據中應用 K 均值聚類算法，對該算法進行分析，仿真結果表明：與傳 統的主用戶定位算法相比，使用 K 均值聚類算法能夠有效地提高定位精度和降低定位算法的復雜度.關鍵詞：聚類分析；K 均值；認知無線電；定位算法中圖分類號：TP391文獻標志碼：A引言數據挖掘（Data mining）是通過數理方法在數據庫中進行知識發現的一個方法.數據挖掘一般是指運用 特定的算法對海量的數據資料進行分析和處理，從而搜索出數據資料中隱藏的、有用的數據信息來為人們 提供有價值的知識. 數據挖掘技術能夠從數據庫和信息庫中的數據資料中發現數據間的隱含關系并提取 出潛在的、有效的模式或者知識，通過統計分析處理、機器學習和模式識別等諸多方法來實現上述目標.聚類分析是數據挖掘在實際應用中的主要方法之一1.一般情況下，在聚類算法中，將數據或者對象的 集合劃分成不同的簇（或者成為聚類集合），每一個簇（聚類）中的數據或者對象擁有較高的相似性，而不同的簇（聚類）中數據或者對象具有較大的差異性.聚類的目標就是依照某種特定相似度量對數據或者對象 進行劃分.聚類算法可以應用到很多學科領域，如計算機科學、統計學、商務、生物學、經濟學等領域.通過聚類算法，人們可以在不同的領域中發現數據分布密集和稀疏的區域，發現數據或者對象間的相互關系，從而對該領域的數據樣本進行有效的劃分.聚類分析計算方法主要有以下幾種：劃分法（Partitioning Methods）、層次法（Hierarchical Methods）、基于 密度的方法（Densitybased Methods）.劃分法就是對給定的 N 個單元或者紀錄的數據集，劃分成 K 個分組， 每一個分組就代表一個聚類，其中 KN.且每一個分組至少包含一個單元或者紀錄，每一個數據單元或者 紀錄屬于且僅屬于一個分組，常見的算法如：K 均值算法，KMEDOIDS 算法、CLARANS 算法等；層次法是 對給定的數據集進行層次似的分解直到滿足某種條件為止，具體又可分為“自底向上”和“自頂向下”兩種 方案，常見算法有：BIRCH 算法、CURE 算法、CHAMELEON 算法等；基于密度的方法區別于其他方法之處 在于，它不是基于各種各樣距離，而是基于密度.這樣算法的優勢在于能夠克服基于距離的算法只能發現 “類圓形”的聚類缺點.該方法的基本思想就是只要一個區域中的點的密度大過某個閥值，就把它加到與之 相近的聚類中去，其代表算法有 DBSCAN 算法、OPTICS 算法等24.在眾多的聚類方法中，均值方法是一種最經典的也是應用最廣泛的聚類方法57，該方法以各類樣本的中心為代表不斷迭代，只適用于數值屬性數據的聚類，對超球形和凸狀數據有很好的聚類效果.0收稿日期：2012-08-28基金項目：廣西自然科目基金（2011gxhsfa018162）資助.作者簡介：李 煒，碩士，助理實驗師，研究方向：信號與信息處理，數據挖掘，E-mail:.1K 均值聚類算法11K 均值聚類算法基本思想K 均值聚類算法是，假設含有 N 個數據（對象）的集合 X（x1，x2，xn），將這個數據集合劃分為 K 個聚K類中心集合 C（c1，c2， ，ck）的問題.假設第 k 類的樣本數目為 Nk，則 N=Nk，每類 Ck 的均值為（m1，m2，k = 1Nk，mk），則 mk= 1 xi，k1，2，K. K 均值聚類算法是基于誤差平方和準則的，即 K 均值聚類算法的最小Ni = 1目標函數為KNkJ= xi-mk2（1）k = 1 i = 1K 均值聚類算法首先在數據集合中隨機選取 K 個數據點作為 K 個聚類的初始類中心，數據集合中每 個數據點根據計算其與各個聚類中心的距離，并將其被劃分到距離最近的聚類中心所在的類中，從而獲得 了 K 個聚類的初始分布狀態集合.當每個數據點劃分到相應的聚類中心后，對分配完的每一個聚類集合計 算新的類中心，然后繼續對集合內的數據點進行數據分配，進行若干次迭代分配，若聚類中心不再發生變 化，則說明集合中的數據對象全部分配到自己所在的類中，那么聚類準則函數收斂，完成了數據集合的聚 類，否則繼續進行迭代過程，直至算法收斂.該聚類算法的一個特點就是在每一次的迭代過程中通過找到 新的聚類中心，對所有數據點進行重新分配和調整，進入下一次的迭代過程，若在某一次迭代過程中，所有 數據點的位置沒有發生變化，也即相應的聚類中心也沒有變化，那么此時說明聚類準則函數已經收斂，實 現了聚類算法.12K 均值聚類算法的基本流程step1 從數據集合 X 中隨機取 K 個元素，作為 K 個聚類的各自的類中心；step2 分別計算集合 X 中剩下的元素到個聚類中心的距離（相異度），將這些元素分別劃分到離其距離 最近（相異度最低）的類中；step3 根據聚類結果，重新計算 K 個聚類各自的類中心，通過是計算聚類中所有元素各自維度的算術 平均值；step4 將 X 中全部元素按照新的中心重新進行分配調整； step5 重復 step2，直到所有數據點和聚類中心不再變化； step6 完成聚類迭代，將結果輸出.2均值聚類在主用戶定位算法中的具體應用21算法模型文獻8詳細介紹了基于信號強度的多主用戶定位的 EM 算法，但是，該 EM 算法需要進行復雜的矩 陣計算，例如求解矩陣的逆運算，算法復雜度很高.如果采用基于均值聚類的主用戶定位算法，可以很好地 降低算法的復雜度，減小主用戶的定位誤差，在工程上可以更好實現.在認知無線電系統結構中，整個電磁空間被劃分為兩個層面：一層為主用戶網絡層；另一層為有認知 用戶構成的認知網絡層.且該系統結構中包含了 M 個待檢測的主用戶發射機和 N 個感知節點.感知節點的 位置已知，而主用戶發射機位置為未知，表示為 =1 2 MT，其中 i=xi，yi表示第 i 個主用戶發射機的 位置.這里假設每個發射機的發射功率相同為 P0，而且主用戶發射機的個數為已知；因此，到達感知節點處 的接收功率可以表示為M2ri= iP0d02， i1，2，N2（ ） +ni（2）m=1 dim其中，ri 表示到達第個感知節點處的功率；i 表示與發射接收天線增益和波長有關的一個損耗常數 1，這里取為 1；d0 為距離主用戶發射機的參考距離，如取為 1 m；d0 為第 i 個感知節點與第 m 個主用戶發射機 之間的二維距離.這里采用一個簡單自由空間中的路徑損耗模型，功率隨路徑距離是平方衰減的關系.ni 為一個零均值高斯隨機變量，其方差為 2.同時假設每個主用戶發射機發射的信號之間及與接收機噪聲信號 之間均為不相關，且已知主用戶和感知節點具體位置，可以計算出在感知節點處接收到的來自該主用戶的功率.22基于聚類的迭代多用戶定位算法對多個主用戶的定位就是根據從若干個感知節點處觀察到的功率 ri，i1，2， ，N，來反推各個主用戶發射機的二維空間位置 ，這一問題實際上可以等效為最大似然參數估計問題，即：尋找一組空間位置，使得在多個已知位置的感知節點處觀察到接收功率為 ri，i1，2，N 的概率最大.即贊=argmax P（r | ）（3）其中， 贊 表示對個發射機二維空間位置的估計值.P（r | ）表示在 N 個感知節點處接收到功率為 r=r1，r2，rN的概率.對式（2）稍作變形，可得MMri=（ iP0d0 22ni ）=ri，m2（ ） + M（4）dim=1mm=1將噪聲帶來的接收功率平均分成 M 份， 分別和來自不同主用戶發射機的功率結合起來， 構成 ri,m=22iP0d0 + ni，m1，2，M，表示只有第 m 個主用戶發射機存在時，在第 i 個感知節點處接收到的功率.2di （m） M）根據公式（2），在已知 M 個主用戶發射機位置的情況下，可以得到對 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 為在一段持續的時間內由感知節點觀察到的多個接收功率樣本.觀察（5）式，當 （n） 與真實的m主用戶發射機位置非常接近時，所得到的ri（n）中前一項為與距離有關的功率分量，第二部分則相當于接收,m機噪聲帶來的功率成分，其在整個功率中所占比重非常小；因此，ri（n）可以近似為與距離成反比的量，r （n）,mi,m 1 2（ iP0d0） 2 ，可得，由d （n）為對發射機 m 與感知節點 i 之間的距離估計（該距離存在偏差）.當 N 個感知節點i,mri（n）i,m到 M 個發射機的距離全部獲得后，將感知節點集合 P set=（X1，Y1），（X2，Y2）， ，（XN，YN）作為圓心，估計出的感知節點到認知用戶發射機之間的距離 D set=r11，r21，rN1，r12，r22，rN2作為半徑畫圓，這時可以得到 N*M 個圓，找出所有圓的交點并將交點的位置保持到集合 C set=（x1 ，x1 ），（x2 ，x2 ）， ，（xj ，xj ）中，對這個交點集合中的交點做 M 個目標的 K 均值聚類，可以得到 M 個主用戶發射機位置集合 R set=（x1，y1），（x2，y2），（xM，yM），通過迭代的方法重復計算主用戶的位置，直到新的位置不再變化，這時可以認為這個位置集合是估計出主用戶發射機的空間位置.仿真結果分析利用上面的思想，提出的多主用戶定位算法的迭代過程如下：1） 隨機生成個主用戶位置的初始估計贊0，設置循環 k 為 1；32） 利用在 N 個感知節點處觀察到的接收功率，計算ri（n），i1，2，N m1，2，M 和d （n）；,mi,m3） 以感知節點為圓心，以di（n），i1，2，N，m1，2， ，M，為半徑可以畫出 N*M 個圓，并求出所有圓之,m間的交點集合，并保存到集合 C 中；4） 對 C 中的點進行 M 個目標的 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，重復 step2）.為了方便仿真多主用戶定位算法， 假設認知無線電環境結構圖中有兩個主用戶發射機和 1020 個認 知用戶節點；并且，主用戶發射機和認知用戶節點隨機分布在一個 1 km*1 km 的平面區域內，而信道參數 i=1，d0=1，P0=1，迭代收斂系數為 =0.02.從圖 1 中可以看出，認知用戶節點的數量和信噪比是影響主用戶數量估計準確性的幾個因素.當信噪比足夠高，則數量估計算法就能保證很高的精度.圖 1 一共有 20 個認知用戶節點.可以看出，估計出的主用 戶位置與其真實的位置十分接近.圖 2 是 EM 算法和迭代 K 均值聚類的主用戶定位算法的均方距離定位誤差，信噪比為 10 dB，從圖中 可以看出上文提出的迭代 K 均值聚類的多主用戶定位算法效果要優于傳統的 EM 定位算法.（n+1） 贊 （n+1）贊 （n+1） T1 0009008007006005004003002001000.25EMK 均值聚類0.05000468101214161820100 200 300 400 500 600 700 800 900 1 000認知節點的數量注： 認知用戶節點的位置； 主用戶的真實位置； 由定位算法估計出的主用戶位置.圖 1 定位算法仿真結果圖結論圖 2 信噪比 10 dB 時 EM 算法和迭代 K 均值聚類算法的性能比較圖4通過在處理認知無線電網絡中主用戶定位是海量數據中應用 K 均值聚類算法對該算法進行分析.仿真結果表明，在認知無線電網絡主用戶定位算法中，聚類算法較傳統的 EM 定位算法的算法復雜度低，定 位精度要高.參考文獻1 賀玲，吳玲達，蔡益朝數據挖掘中的聚類算法綜述J計算機應用研究，2007， 24（1）：10132 謝崇寶，袁宏源最優分類的模糊劃分聚類改進方法J系統工程，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計算機研究與發展，2010， 47（6）：104410525 Kanungo T， Mount D M A Local Search Approximation algorithm for kmeans clusteringJ Computational Geometry， 2004， 28（2 3）：891126 梁鑫聚類分析算法在路面破損檢測中的應用J廣西工學院學報 ，2008，19（4）：51537 歐陽浩模糊聚類分析在產品質量評估中的應用J廣西工學院學報 ，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（下轉第 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