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

文章编号 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