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

基于K均值聚类的定位算法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 文章编号 1004-6410,2012,03-0045-04 基于 K 均值聚类的定位算法分析 李炜 ,广西工学院 计算机学院,广西 柳州 545006, 摘 要,在描述了聚类算法的基本思想和概念的基础上,介绍了一种常见的聚类算法—K 均值和 K 中心点聚类算法, 通过处理认知无线电网络中主用户定位在海量数据中应用 K 均值聚类算法,对该算法进行分析,仿真结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明,与传 ,使用 K 均值聚类算法能够有效地提高定位精度和降低定位算法的复杂度. 统的主用户定位算法相比 关键词,聚类分析,K 均值,认知无线电,定位算法 中图分类号,TP391 文献标志码,A 引言0 数据挖掘,Data mining,是通过数理方法在数据库中进行知识发现的一个方法.数据挖掘一般是指运用 特定的算法对海量的数据资料进行分析和处理,从而搜索出数据资料中隐藏的、有用的数据信息来为人们 提供有价值的知识. 数据挖掘技术能够从数据库和信息库中的数据资料中发现数据间的隐含关系并提取 出潜在的、有效的模式或者知识,通过统计分析处理、机器学习和模式识别等诸多方法来实现上述目标. ,1,聚类分析是数据挖掘在实际应用中的主要方法之一.一般情况下,在聚类算法中,将数据或者对象的 集合划分成不同的簇,或者成为聚类集合,,每一个簇,聚类,中的数据或者对象拥有较高的相似性,而不同 的簇,聚类,中数据或者对象具有较大的差异性.聚类的目标就是依照某种特定相似度量对数据或者对象 进行划分.聚类算法可以应用到很多学科领域,如计算机科学、统计学、商务、生物学、经济学等领域.通过聚 类算法,人们可以在不同的领域中发现数据分布密集和稀疏的区域,发现数据或者对象间的相互关系,从而对该领域的数据样本进行有效的划分. 聚类分析计算方法主要有以下几种,划分法,Partitioning Methods,、层次法,Hierarchical Methods,、基于 密度的方法,Density,based Method,s.划分法就是对给定的N 个单元或者纪录的数据集,划分成 K 个分组, 每一个分组就代表一个聚类,其中 K，N.且每一个分组至少包含一个单元或者纪录,每一个数据单元或者 纪录属于且仅属于一个分组,常见的算法如,K 均值算法,K,MEDOIDS 算法、CLARANS 算法等,层次法是 对给定的数据集进行层次似的分解直到满足某种条件为止,具体又可分为“自底向上”和“自顶向下”两种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,常见算法有,BIRCH 算法、CURE 算法、CHAMELEON 算法等,基于密度的方法区别于其他方法之处 在于,它不是基于各种各样距离,而是基于密度.这样算法的优势在于能够克服基于距离的算法只能发现 “类圆形”的聚类缺点.该方法的基本思想就是只要一个区域中的点的密度大过某个阀值,就把它加到与之 ,2,4,相近的聚类中去,其代表算法有 DBSCAN 算法、OPTICS 算法等. ,5,7, 在众多的聚类方法中,均值方法是一种最经典的也是应用最广泛的聚类方法,该方法以各类样本的中心为代表不断迭代,只适用于数值属性数据的聚类,对超球形和凸状数据有很好的聚类效果. 收稿日期,2012-08-28 基金项目,广西自然科目基金,2011gxhsfa018162,资助. 作者简介,李 炜,硕士,助理实验师,研究方向,信号与信息处理,数据挖掘,E-mail:liwehappyman@qq.com.i- 1 K 均值聚类算法 1,1 K 均值聚类算法基本思想 K 均值聚类算法是,假设含有 N 个数据,对象,的集合 X:,x,x,…,x,,将这个数据集合划分为 K 个聚 12n K 类中心集合 ,,,… ,,的问题假设第 类的样本数目为 ,则 ,每类 的均值为,,,C:ccc.k NN=NCmmΣ 12kkkk 12k = 1 Nk 1 …,m,,则 m= x,k,1,2,…,K. K 均值聚类算法是基于误差平方和准则的,即 K 均值聚类算法的最小 ΣkkiN i = 1 目标函数为 K N k2 ,1,J= x-mΣΣ ikk = 1 i = 1 K 均值聚类算法首先在数据集合中随机选取 K 个数据点作为 K 个聚类的初始类中心,数据集合中每 个数据点根据计算其与各个聚类中心的距离,并将其被划分到距离最近的聚类中心所在的类中,从而获得 了 K 个聚类的初始分布状态集合.当每个数据点划分到相应的聚类中心后,对分配完的每一个聚类集合计 算新的类中心,然后继续对集合内的数据点进行数据分配,进行若干次迭代分配,若聚类中心不再发生变 化,则说明集合中的数据对象全部分配到自己所在的类中,那么聚类准则函数收敛,完成了数据集合的聚 类,否则继续进行迭代过程,直至算法收敛.该聚类算法的一个特点就是在每一次的迭代过程中通过找到 新的聚类中心,对所有数据点进行重新分配和调整,进入下一次的迭代过程,若在某一次迭代过程中,所有 数据点的位置没有发生变化,也即相应的聚类中心也没有变化,那么此时说明聚类准则函数已经收敛,实 现了聚类算法. 1,2 K 均值聚类算法的基本流程 step1 从数据集合 X 中随机取 K 个元素,作为 K 个聚类的各自的类中心, step2 分别计算集合 X 中剩下的元素到个聚类中心的距离,相异度,,将这些元素分别划分到离其距离 最近,相异度最低,的类中, step3 根据聚类结果,重新计算 K 个聚类各自的类中心,通过是计算聚类中所有元素各自维度的算术 平均值, step4 将 X 中全部元素按照新的中心重新进行分配调整, step5 重复 step2,直到所有数据点和聚类中心不再变化, step6 完成聚类迭代,将结果输出. 2 均值聚类在主用户定位算法中的具体应用 2,1 算法模型 文献,8,详细介绍了基于信号强度的多主用户定位的 EM 算法,但是,该 EM 算法需要进行复杂的矩 阵计算,例如求解矩阵的逆运算,算法复杂度很高.如果采用基于均值聚类的主用户定位算法,可以很好地 降低算法的复杂度,减小主用户的定位误差,在工程上可以更好实现. 在认知无线电系统结构中,整个电磁空间被划分为两个层面,一层为主用户网络层,另一层为有认知 用户构成的认知网络层.且该系统结构中包含了 M 个待检测的主用户发射机和 N 个感知节点.感知节点的 T位置已知,而主用户发射机位置为未知,表示为 θ=,θθ…θ,,其中 θ=,x,y,表示第 i 个主用户发射机的 1 2 Miii 位置.这里假设每个发射机的发射功率相同为 P,而且主用户发射机的个数为已知,因此,到达感知节点处 0 的接收功率可以表示为 M 2 ξPd2i00 , i,,12,…,Nr= +n,2,Σ ii2 d,θ , m=1 i m 其中,表示到达第个感知节点处的功率,表示与发射接收天线增益和波长有关的一个损耗常数 ,rξ1 i i 这里取为 1,d为距离主用户发射机的参考距离,如取为 1 m,d为第 i 个感知节点与第 m 个主用户发射机 0 0 之间的二维距离.这里采用一个简单自由空间中的路径损耗模型,功率随路径距离是平方衰减的关系.n为 i 2一个零均值高斯随机变量,其方差为 σ.同时假设每个主用户发射机发射的信号之间及与接收机噪声信号 之间均为不相关,且已知主用户和感知节点具体位置,可以计算出在感知节点处接收到的来自该主用户的 功率. 2,2 基于聚类的迭代多用户定位算法 对多个主用户的定位就是根据从若干个感知节点处观察到的功率 r,i,1,2,… ,N,来反推各个主用户 i 发射机的二维空间位置 θ,这一问题实际上可以等效为最大似然参数估计问题,即,寻找一组空间位置,使 得在多个已知位置的感知节点处观察到接收功率为 ,,,…,的概率最大ri,12N .i 即 赞 ,,max θ=argPr | θ,3,θ 赞 其中, 表示对个发射机二维空间位置的估计值,,表示在 个感知节点处接收到功率为 ,, θ.Pr | θN r=r1 r,…,r,的概率.2N 对式,,稍作变形,可得2 M M 2 2 n ξPd i00 i r=, ,=r+ ,4, ΣΣ, iim2 d,θ , M im m=1 m=1 将噪声带来的接收功率平均分成 份, 分别和来自不同主用户发射机的功率结合起来, 构成 M r= i,m 2 2 ξPdni00 i ,m,1,2,…,M,表示只有第 m 个主用户发射机存在时,在第 i 个感知节点处接收到的功率. + 2 d,θ, M , i m 根据公式,,,在已知 个主用户发射机位置的情况下,可以得到对 的估计值2M r: i,m M 2 2 ξPd 1 ξPd,n, i00 i00 r , ,r-,, ,5,=E+ Σ,m ii,, 2,n, 2n ,, d ,θ, Md θm=1 i m i m ,, n其中,为在一段持续的时间内由感知节点观察到的多个接收功率样本观察,,式,当 与真实的r.5θ i m ,n,主用户发射机位置非常接近时,所得到的r中前一项为与距离有关的功率分量,第二部分则相当于接收 i,m ,n,,n,机噪声带来的功率成分,其在整个功率中所占比重非常小,因此,r可以近似为与距离成反比的量,r ?i,m i,m 1 2 ξPd2 ,n,i00 , d , ,可得,由为对发射机 m 与感知节点 i 之间的距离估计,该距离存在偏差,.当 N 个感知节点i,m ,n,r ii,m 到 个发射机的距离全部获得后,将感知节点集合 ,,,,,,,,,… ,,,,,作为圆心,估计M P set=XYXYXY 1122NN 出的感知节点到认知用户发射机之间的距离 ,,,…,,,,…,,作为半径画圆,这时可以得D set=rrrrrr 1121N11222N2 ′ ′ ′ ′′′ 到 个圆,找出所有圆的交点并将交点的位置保持到集合 ,,,,,,,,,… ,,,,,中,对N*M C set=xxxxxx 1 1 2 2 j j 这个交点集合中的交点做 个目标的 均值聚类,可以得到 个主用户发射机位置集合 ,,,,,M K M R se=txy 11,,,,…,,,,,,通过迭代的方法重复计算主用户的位置,直到新的位置不再变化,这时可以认为这个xyxy 22MM 位置集合是估计出主用户发射机的空间位置. 3仿真结果分析 利用上面的思想,提出的多主用户定位算法的迭代过程如下, 赞1, 随机生成个主用户位置的初始估计θ,设置循环 k 为 1, 0 ,n,,n,, 利用在 个感知节点处观察到的接收功率,计算r,,,…,,,…,和d ,2N i,12N m,12M i,m i,m ,n,, 以感知节点为圆心,以d,,,…,,,,… ,,为半径可以画出 个圆,并求出所有圆之3i,12,12MN*M Nmi,m 间的交点集合,并保存到集合 C 中, ,,,,,, ,, 赞n+1赞n+1赞 n+1赞n+ 1 T, 对 中的点进行 个目标的 均值聚类运算,获得新的主用户的位置信息,θ…θ, , 4C M θ=θK1 2 M ,,,,,,,,赞n+1赞n赞n+1赞nT , 计算 ,θθ,,θθ,,求矩阵 的对角线元素之和,即 ,,,,,为矩阵的迹5A=--A e=TraceATraceA.为迭代前后两次的距离收敛程度, ,,,, ,, ,, 赞n+1赞n+1赞n +1 赞 n+1 T, 如果 ,停止迭代,此时的,θ…θ, ,即为所求的 个主用户的空间位置,否则, 6e?εθ=θM 1 2 M 令 k=k+1,重复 step2,. 为了方便仿真多主用户定位算法, 假设认知无线电环境结构图中有两个主用户发射机和 10,20个 认 知用户节点,并且,主用户发射机和认知用户节点随机分布在一个 1 km*1 km 的平面区域内,而信道参数 ξ=1,d=1,P=1,迭代收敛系数为 ε=0.02. i00 从图 1 中可以看出,认知用户节点的数量和信噪比是影响主用户数量估计准确性的几个因素.当信噪比足够高,则数量估计算法就能保证很高的精度.图 1 一共有 20 个认知用户节点.可以看出,估计出的主用 户位置与其真实的位置十分接近. 图 2 是 EM 算法和迭代 K 均值聚类的主用户定位算法的均方距离定位误差,信噪比为 10 dB,从图中 可以看出上文提出的迭代 K 均值聚类的多主用户定位算法效果要优于传统的 EM 定位算法. 1 000 0.25 EM 900 K 均值聚类 0.2 800 700 2 0.15 600 /km500 0.1 400 均方误差300 0.05 200 100 0 04 6 8 10 12 14 16 18 20 0100 200 300 400 500 600 700 800 900 1 000 认知节点的数量 注,, 认知用户节点的位置,? 主用户的真实位置,—— 图 2 信噪比 10 dB 时 EM 算法和迭代 K 均值聚类算 ?— 由定位算法估计出的主用户位置. 法的性能比较图 图 1 定位算法仿真结果图 结论 4 通过在处理认知无线电网络中主用户定位是海量数据中应用 K 均值聚类算法对该算法进行分析.仿 真结果表明,在认知无线电网络主用户定位算法中,聚类算法较传统的 EM 定位算法的算法复杂度低,定 位精度要高. 参考文献 ,1, 贺玲,吴玲达,蔡益朝,数据挖掘中的聚类算法综述,J,,计算机应用研究,2007, 24,1,,10,13, ,2, 谢崇宝,袁宏源,最优分类的模糊划分聚类改进方法,J,,系统工程,1997, 15,1,, 58,3,3,6 ,3, Rudi L,Cilibras i, Paul M,B, VitanyiA, Fast Quartet tree heuristic hierarchicafor l clustering ,J,, Patternrecognitio n, 2011,44,3,, 662,776, ,4, 武佳薇,李雄飞,孙涛,等,邻域平衡密度聚类算法,J,,计算机研究与发展,2010, 47,6,,1044,0521, ,5, Kanungo T, MountD M,A Local Search Approximation algorithmk ,formeans clustering,J,, Computationa Geometr,y 2004, 28,2 , l 3,,89,112, ,6, 梁鑫,聚类分析算法在路面破损检测中的应用,J,,广西工学院学报 ,2008,19,4,,51,53, ,7, 欧阳浩,模糊聚类分析在产品质量评估中的应用,J,,广西工学院学报 ,2008,19,4,,83,85. ,8, J,K ,Nelso n, and M, RGupt, a, ,AnEM Technique forMultiple TransmitterLocalization , in Proc,CIS S,C,, 2007, Baltimor,e MD, ,下转第 76 页, A method for fast pavement cracking detection based on the biological inspired model aabXU ,y,TANG Pei,he, ,ping YiiNIZhi ,a,College of ComputerE ngineering, b,Lushang College,Guangxi University of Technology, Luzhou 545006, China, i Abstract, Due to the c omplexty of shape and apparent dfferences of pavement cracks, it is difficult toii characterze them wth defnite features, The wavelet, Gabor transformand ts functons are usuay predefned and iiiiillicannot adaptto the characteristicsof the pavementcrack images, This paper proposesa novel joint maximization recogniton agorthm in the resent area, which is based on the characteristicsof biologically inspired mode iliilil,BIM,, The algorithm uses the elastic neighborhood, the first adjacent neighbors domain or eight neighborhood image segmentation, Adaboost classifieris introduced in each region to selectand retain key information, get rid of unwanted ornega tive information, Its eigenvectorscan reflect the information in the original image comprehensively and its low computational complexity is helpful in real ,time applications, The experimental results show thatt he overall recognition rate of the proposed methodin pavement cracksis up to 99,13,, and its fast responset ime fully demonstrate the effectiveness of this method, ey words, bo,nspired model, fexbty neighborhoo,d feature extracton Kiiliilii ,责任编辑 李捷, !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! ,上接第 48 页, Localization algorithm analysis based on K,means clustering LI Wei ,College of ComputerEngi neering, Guangxi University of Technology, Liuzhou 545006, China, Abstract, This paper introduces the basic ideas and conceptsof the clustering algorithm and presentsa common clustering algorithm——K ,meansand K ,means centercl ustering algorithm, Then analysis of the primary users ocazaton in cognitve rado s conductedb y usng K ,meansc usterng agorthm, The resuts show thatt he lliiiiiilililproposedK ,means ocazaton agorthm performs ower computatona complexty and smaer ocaton error than lliililililllitraditional schemes, Key words,cluster analysis, K,meansa lgorithm, cognitive radio, localization algorithm ,责任编辑 李捷,