《基于k近邻隶属度的聚类算法研究-马闯.pdf》由会员分享，可在线阅读，更多相关《基于k近邻隶属度的聚类算法研究-马闯.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基于K近邻隶属度的聚类算法研究马 闯，吴涛，段梦雅MA Chuang，WU Tao，DUAN Mengya安徽大学数学科学学院，合肥23060 1Department of Mathematical Sciences，Anhui University,Hefei 23060 I，ChinaMA Chuang，WU Tao，DUAN MengyaClustering algorithm based on membership degree of K-nearest neighbocComputer Engineering and Applications，2016，52(10)：5558Abst
2、ract：Classic fuzzy C-means algorithm(FCM)iS based on Euclidean distanceit includes a problem that differentsize of class cluster is not clustered correctlyAiming at the problem，this paper presents a fuzzy Cmeans algorithm basedon the membership degree of Knearest neighbor(KNNFCM)Then the paper discu
3、sses rough Cmeans clustering algorithm and rough fuzzy C-means clustering algorithm，which are both based on the membership degree of K-nearest neighbo rThese algorithms avoide a question of threshold selection in traditional rough C-means clustering algorithm and roughfuzzy C-means clustering algori
4、thmCompare the KNNFCM、KNNRCM、KNNRFCM with FCM、RFM、RFCM inUCI dataset，the experimental result shows that the method is feasible and effectiveKey words：membership degree ofK-nearest neighbor；clustering；fuzzy Cmeans；rough Cmeans；rough fuzzy Cmeans摘 要：经典模糊c均值聚类算法(FCM)基于欧氏距离，存在不同规模类簇不能正确聚类问题，针对此问题提出一种基于K
5、近邻隶属度的模糊c均值聚类算法(KNN FCM)。讨论了基于K近邻隶属度的粗糙c均值聚类算法(KNN RCM)和粗糙模糊c均值聚类算法(KNN RFCM)，此方法避免了传统粗糙c均值聚类算法(RCM)和粗糙模糊c均值聚类算法(RFCM)中阈值选择问题。将KNN FCM、KNN RCM、KNN RFCM分别与FCMRFM、RFCM在ucI数据集上进行仿真比较，结果表明新方法是可行、有效的。关键词：K近邻隶属度；聚类；模糊c均值；粗糙c均值；粗糙模糊C均值文献标志码：A 中图分类号：TP3016 doi：103778巧issn10028331140603731 引言传统的聚类分析是一种硬划分，将某
6、个样本严格地划分到某个类别中。如K均值聚类算法”】，就是一个典型的硬划分聚类。但在实际应用中，不同的类簇之间往往存在相互重叠的部分，也就是说重叠部分的样本就不能明确地说它属于还是不属于某个类簇，这就需要一些处理不确定理论的工具进行软划分。1965年，Zadeh提出了模糊集的概念。】，用隶属度来表示对象属于集合的程度。把隶属度引入到世均值聚类算法中，就可以有效地表示一个样本同属于多个类簇的情况，这就是模糊C均值聚类(FCM)9。4】。粗糙集”1用上近似、下近似来刻画不确定信息，也是一种处理不确定理论的数学工具。Lingras最早将粗糙集引入到K均值聚类中，提出了粗糙C均值聚类(RCM)“。而粗糙
7、集和模糊集可以互为补充，于是Mitra将模糊聚类的隶属度引入粗糙c均值聚类中，提出了粗糙模糊C均值聚类(RFCM)。而在传统的模糊聚类中，隶属度的确定只取决于各个样本到各个类簇中心的欧氏距离，存在等划分趋势，及每个类簇规模(包括数量及样本分布空间)必须建立基金项目：国家自然科学基金(No71371011)；安徽省高等学校省级自然科学研究重点项目(NoKJ20 J3A033)；安徽大学研究生学术创新研究项目。作者简介：马闯(1990一)，男，硕士研究生，研究领域为智能计算和不确定理论，Email：chuang_m126，com；吴涛(1970一)，男，博士，教授，研究领域为智能计算和不确定理论；
8、段梦雅(1 990一)，女，硕士研究生，研究领域为智能计算和不确定理论。收稿日期：20140625 修回日期：2014-0804 文章编号：10028331(2016)10-005504CNKI网络优先出版：2015-0116，http：wwwcnkinetkcmsdetail112127TE201501161122003html万方数据ComputerEngineeringandApplications计算机工程与应用在相似的假设条件下睁”，。K近邻是一种常见的有监督的学习算法”。本文利用K近邻思想，考虑样本周围元素的影响，定义一种隶属度，用于无监督学习聚类分析中，得到基于该隶属度的模糊C均
9、值聚类算法。由于该隶属度又可以直接生成粗糙集，于是本文接着介绍了基于该隶属度的粗糙C均值聚类算法，这种算法无需阈值，避免了传统粗糙C均值聚类算法中对阈值的选择问题。最后给出了只基于该隶属度的粗糙模糊C均值聚类算法。通过实验仿真比较，表明所提方法的有效性。2基础知识21 模糊C均值聚类(FCM)假定x=“，xf一，x。)是n个样本集合，c=cl，cf，c。)是k个类簇中心集合，其中cf为类簇C；的中心。FCM算法将n个样本分别划分到k个模糊子集中，并且使得下面目标函数最小：“F=1(=1，2，以) (2)式中m是大于1的数，用来控制模糊程度；U，表示样本_隶属类簇C，的程度，且00) (9)，=
10、xu=1 (10)B，=Cf一。 (11)式中U。由公式(8)求得；c，虿，分别表示第i个类簇的下、上近似；Bi表示边界。把该粗糙集引入到粗糙聚类算法中可以得到基于K近邻的粗糙C均值聚类算法(KNN RCM)。其中类簇C，的中心C；的计算公式为：xj _W|ow X酋+苜B，翊加，翊jC x；(12)式中。，睨。分别代表在计算类簇中心时，下、上近似中的对象对中心位置的影响权重，其中。+Wu。=1；瞄I表示类簇c，下近似中元素的个数；IB，I表示类簇C，边界中元素的个数。算法2 KNNRCM算法步骤l初始化聚类中心C，K，。，Wu。步骤2按公式(8)计算出所有样本到各个类簇的隶属度。步骤3使用公
11、式(9)，(10)，(11)求上、下近似和边界。步骤4使用公式(12)更新聚类中心。步骤5重复步骤2至步骤4直到算法收敛。最后，可以看到在K近邻确定隶属度的基础上，同时又可以定义每个类簇的粗糙集。因此得到一种基于K近邻的粗糙模糊C均值聚类算法(删N RFCM)。其中类簇Ci的中心Ci的计算公式为：口)”_ 口)”_专矿喁专矿，xig xlEBifBf0CaBC=B=(13)算法3 KNN RFCM算法步骤1初始化聚类中心C，K，。，帆。+步骤2按公式(8)计算出所有样本到各个类簇的隶属度。步骤3按公式(9)，(10)，(11)求上、下近似和边界。步骤4按公式(13)更新聚类中心。步骤5重复步骤
12、2至步骤4直到算法收敛。4实验41数据准备与处理本文采用UCI数据库中Iris、Wine、Wine Quality、Statlog(Heart)、Ionosphere(前8个属性)和Statlog(Aus-tralian Credit Approval)(ACA)六组数据集进行对比试验，数据集的特征如表1所示。表l 实验数据集的构成描述首先需要对数据进行标准化处理，消除量纲。设每个样本有，个特征：x，=x1xj2，xjf)=1，2，z，则标准化后得”2】：，。一 垒二竺兰堕：垫二垒!。_max(xlf，x2f，x小)一min(xlf，z2r，z月f)，=1，2，n；t=1，2， (14)n一，
13、n一，一一堕社泓生似TXcSj彩囝CC一堕瞄坐防万方数据58 2016，52(10) ComputerEngineeringandApplications计算机工程与应用在实际聚类中，有些数据消除量纲，能提高聚类效果，而有些数据消除量纲的同时，也消除了各个属性对聚类贡献的差异性，影响聚类效果。因此根据各数据特征，对Iris、Wine Quality和Ionosphere数据集直接聚类，对Wine、Statlog(Heart)和Statlog(Australian Credit Approval)(ACA)数据集标准化后再聚类。42实验结果为了消除参数选取对算法比较带来影响，参考了文献1314，
14、相应地设置m=2，。=09，Wu。=o1。这三个参数值在传统聚类算法中已验证可以得到较优的结果，因此在这里把它们用于改进算法，以此检验改进算法是否优于传统算法。对于参数K的取值，除了大数据集Wine Quality K取100，其他数据集K均取30。用传统的模糊C均值聚类算法(FcM)、粗糙C均值聚类算法(RCM)和粗糙模糊C均值聚类算法(RFCM)分别与本文的KNN FCM、KNN RCM及KNN RFCM进行仿真比较。实验结果如表2、表3、表4所示，其中DB”51指标越小越好，准确度越大越好。表2两种FCM算法结果比较表2可以看出，在两种模糊聚类算法中，除了wine数据集的KNN_FCM算
15、法的DB指标略差外，其他各个数据集的各个指标都优于FCM。表4两种RFCM类算法结果比较表3、表4可以看出，由K近邻隶属度引出的KNNRCM算法，KNNRFCM算法虽然在DB指标上都略差于RCM，RFCM算法，但是在准确度和收敛效果基本上全都优于RCM，RFCM算法。由图3可以更清楚地看出改进算法的准确度基本高于传统算法。图3mFCM-KNN FCM-RCM心篷p聚类算法准确率比较5结束语本文提出了一种基于K近邻的隶属度计算方法。因为在此隶属度上可直接设计模糊、粗糙、粗糙模糊C均值聚类算法，并通过实验比较验证其有效性与准确性，所以该系列算法存在很好的兼容性，既可以融入其他模糊聚类算法中，又可以
16、融入其他粗糙聚类算法中，这将是下一步的研究方向。参考文献：I】Hartigan J A，Wong M AAlgorithm AS 136：A k-meansclustering algorithmJApplied Statistics，1979：100-1082Zadeh L AFuzzy setsJInformation and Control，1 965，8(3)：3383533】Dunn J CA fuzzy relative of the ISODATA process andits use in detecting compact wellseparated clustersJJou
17、rnalof Cybernetics，1 974 4】Bezdek J CPattem recognition with fuzzy objective functionalgorithmsM【s1：Kluwer Academic Publishers，1981(下转117页)二二rnU一坩朴U=寰妒Q-JL摹i-，一一噜11111妒眦眈翔狲支了母晋墨lI万方数据张文杰，茧育宁，王新珩：一种利用RFID和块聚类的室内定位方法 2016，52(10) 117Springer，200 1：1 8-348Tran Q，Tantra J W，Foh C H，et a1Wireless indoor p
18、osi-tioning system with enhanced nearest neighbors in signalspace algorithmCVehicular Technology Conference，IEEE64th 2006IEEE2006：l一59Lin T N，Lin P CPerformance comparison of indoor positioning techniques based on location fingerprinting in wireless networksC2005 International Conference oil Wireles
19、s Networks，Communications and Mobile ComputingIEEE，2005，2：1569157410Ma J，Li X，Tao X，et a1Cluster filtered KNN：A WLANbased indoor positioning schemeC2008 InternationalSymposium on World of Wireless，Mobile and MultimediaNetworksIEEE，2008：卜811】Ni L M，Liu Y，Lau Y C，et a1LANDMARC：indoorlocation sensing u
20、sing active RFIDJWireless Networks，2004，10(6)：70l一710费业泰误差理论与数据处理M6版北京：机械工业出版社，1987：4451Li M JNg M K，Cheung Y，et a1Agglomerative fuzzyk-means clustering algorithm with selection of numberof clustersJIEEE Transactions on Knowledge and DataEngineering，2008，20(11)：1519-1534Lee C W，Lin T N，Fang S H，et a
21、1A novel clusteringbased approach of indoor location fingerprintingC20 1 3 IEEE 24th International Symposium on PersonalIndoor and Mobile Radio Communications(PIMRC)IEEE2013：31913196Pritt NIndoor positioning with maximum likelihood classification of WiFi signalsC20 1 3 IEEE on SensorsIEEE，2013：l一4(上
22、接58页)5】Pawlak zRough setsJInternational Journal of Computer&lnformation Sciences，1982，11(5)：3413566Lingras P，West CInterval set clustering of web users withrough k-meansJJournal of Intelligent Information Systerns，2004，23(1)：5-167Mitra S，Banka H，Pedrycz WRoughfuzzy collaborativeclusteringJIEEE Trans
23、actions on Systems，Man，andCybernetics：Part B，2006，36(4)：7958058】Maji P，Pal S KRough set based generalized fuzzy cmeansalgorithm and quantitative indicesJIEEE Transactions onSystems，Man，and Cybernetics：Part B，2007，37(6)：152915409】楼晓俊，李隽颖，刘海涛距离修正的模糊c均值聚类算法J计算机应用，2012。32(3)：64664810王建锋，金健，王晶晶一种具有影响力因子的
24、硬聚类算法J计算机工程与应用，2009，45(19)：177180【11Cover T，Hart PNearest neighbor paUern classjfication【JIEEE Transactions on Information Theory，1 967，1 3(1)：2l一2712朱剑英应用模糊聚类法应注意的若干关键问题J】模糊系统与数学，1987，1(1)：10411113王学恩，韩德强，韩崇昭采用不确定性度量的粗糙模糊C均值聚类参数获取方法J】西安交通大学学报，2013，47(6)：556014郭晋华，苗夺谦，周杰基于阴影集的粗糙聚类阈值选择J计算机科学，2011，38(
25、10)：209210，1 5Davies D L，Bouldin D WA cluster separation measureJIEEE Transactions on Pattern Analysis and MachineIntelligence，1979，l(2)：224227(上接103页)【8Yao Yuan，Rao Lei，Liu XuePerformance and reliabilityanalysis of IEEE 8021 lp safety communication in ahighway environmentJ，IEEE Transactions on Vehi
26、cularTechnology，2013，62(9)：419842129Sheu T L，Wu Y JJammingbased medium access controlwith dynamic priority adjustment in wireless Ad-hoc net-worksCIET Communications，2007，1(1)：3440【10】SahebgharaniS S MA scheduling algorithm for downloading data from RSU using multicast techniqueCNinth International
27、Conference on Information Technology：New Generations(ITNG)，2012：809814I 1孙健车辆自组织网络中安全消息的优先级调度和拥塞控制【D】西安：西安电子科技大学，20121 2Wang C D，Thompson J P,Apparatus and method formotion detection and tracking of objects in a regionfor collision avoidance utilizing a realtime adaptiveprobabilistic neural networkP
28、US Patent，1997：3-18，1 3Willke T L，Tientrakool P，Maxemchuk N FA survey ofintervehicle communication protocols and their applicationsJCommunications Surveys&Tutorials，2009，1 l(2)：320【14】朱钧宇，黄传河，徐利亚，等，VANET中一种链路稳定度的计算方法J计算机工程与科学，2013，35(1)：576015Liu Jianhang，Ge Yuming，Bi Jingping，et a1Dynamic optimization model for cooperative downloading strategy ofVANETJ，Journal of Internet Technology，201 3，14(6)：963972纠列卅习r【r【r【rL万方数据