基于K均值聚類的定位算法分析.doc

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