http://www.cnki.com.cn/Article/CJFDTotal-ZKYB200706008.htm
| |
| | 基于优化初始类中心点的K-means改进算法 |
| | 秦钰;荆继武;向继;张爱华 |
| | K-means算法是一种重要的聚类算法,在网络信息处理领域有着广泛的应用.由于K-means算法终止于一个局部最优状态,所以初始类中心点的选择 会在很大程度上影响其聚类效果.提出了一种K-means算法的改进算法,首先探测数据集中的相对密集区域,再利用这些密集区域生成初始类中心点.该方法 能够很好地排除类边缘点和噪声点的影响,并且能够适应数据集中各个实际类别密度分布不平衡的情况,最终获得较好的聚类效果.
【作者单位】：信息安全国家重点实验室(中国科学院研究生院) 北京100049
【关键词】：聚类;K-means;初始类中心点
【分类号】：TP311.13;TP18
【DOI】：CNKI:SUN:ZKYB.0.2007-06-008
【正文快照】：
1引言聚类分析是一种重要的数据挖掘技术,在网络信息检索、过滤、分类等方面得到了广泛的应用.现有的聚类算法大致可分为层次聚类、划分聚类、基于密度 的聚类、基于网格的聚类、基于模型的聚类等几种[1],其中层次聚类和划分聚类应用最为广泛.层次聚类依据数据对象之间的相似程� |
| |  推荐 CAJ下载  PDF下载 |
| | CAJViewer7.0阅读器支持所有CNKI文件格式，AdobeReader仅支持PDF格式 |
|
| | An improved K-means algorithm based on optimizing initial points |
| | QIN Yu JING Ji-Wu XIANG Ji ZHANG Ai-Hua(The State Key Laboratory of Information Security (Graduate University of Chinese Academy of Sciences);Beijing 100049;China) |
| | K-means is an important clustering algorithm. It is widely used in Internet information processing technologies. Because the procedure terminates at a local optimum, K-means is sensitive to initial starting condition. An improved algorithm is proposed, which searches for the relative density parts of the database and then generates initial points based on them. The method can achieve higher clustering accuracies by well excluding the effects of edge points and outliers, as well as adapt to databases which have very skewed density distributions.
【Keyword】：clustering, K-means, initial points |
|
| |
| | | 1 | TDT3Multilanguage Text Corpus,Version2.0 [M];; 2001年 | | 2 | Pena J, Lozano J, Larranaga P; An Empirical Comparison of Four InitializationMethods for the K-Means A lgorithm [M];Pattern Recognition; 1999年 | | 3 | He J,Lan M,Tan CL,et al; Initialization of cluster refinement algorithms:Areviewand comparative study [M];Proceedings of2004IEEE International Joint Conference on Neural Networks(IJCNN).; 2004年 | | 4 | Ankerst M,Breunig MM,Kriegel HP,et al; OPTICS:Ordering points to identify the clustering structure [M];Proceedings of the International Conference on Management of Data(SIGMOD); 1999年 | | 5 | [M];http://www.nist.gov/speech/tests/tdt/; 年 | | 6 | Bradley PS,Fayyad UM; Refininginitial points forK-means clustering [M];Proceedings of the15thInternational Conference on Machine Learning(ICML); 1998年 | | 7 | Cutting DR,Karger DR,Pedersen JO,et al; Scatter/Gather:Acluster-based approachto browsinglarge document collections [M];Proceedings of the15thInternational Conference on Research and Development in Information Retrieval(SIGIR); 1992年 | | 8 | Pantel P,Lin D; Document clustering with committees [M];Proceedings of the25thInternational Conference on Research and Development in Information Retrieval(SIGIR); 2002年 | | 9 | Steinbach M,Karypis G,Kumar V; Acomparison of document clusteringtechniques [M];Proceedings of KDD Workshop on Text Mining; 2000年 |
|
|
| |
| | | 1 | 李鹏,王晓龙,刘远超,王宝勋; 一种基于混合策略的失衡数据集分类方法 [J];电子学报; 2007年11期 | | 2 | 陈爽,陈福,杜天苍; 一种启发式网络信息采集系统设计与实现 [J];北京石油化工学院学报; 2007年04期 | | 3 | 张博锋,白冰,苏金树; 基于自训练EM算法的半监督文本分类 [J];国防科技大学学报; 2007年06期 | | 4 | 刘洋,张秋余; 基于LSI和SVM相结合的文本分类研究 [J];计算机工程与设计; 2007年23期 | | 5 | 徐燕,李锦涛,王斌,孙春明; 基于区分类别能力的高性能特征选择方法 [J];软件学报; 2008年01期 | | 6 | 吕佳; 文本分类中基于方差的改进特征提取算法 [J];计算机工程与设计; 2007年24期 |
|
|
| |
| | | 1 | 贾彦国,李培德; Web检索结果聚类算法的改进 [A];2006北京地区高校研究生学术交流会——通信与信息技术会议论文集（上） [C]; 2006年 | | 2 | 汪民乐,高晓光,李勇; 新型遗传模糊C-均值聚类算法及其在导弹目标选择中的应用 [A];2007年中国智能自动化会议论文集 [C]; 2007年 | | 3 | 宿太学,吕天阳,张锡哲,王钲旋,徐长青; 一个集成多种聚类技术实验平台的整体设计方案和基本模块实现 [A];第十二届全国图象图形学学术会议论文集 [C]; 2005年 | | 4 | 王晓辉,周越,王永刚,杨杰; 基于Quaternion-Gabor滤波器的彩色纹理分割算法研究 [A];2006中国科协年会——数字成像技术及影像材料科学学术交流会论文集 [C]; 2006年 | | 5 | 王晓辉,周越,王永刚,杨杰; 基于Quaternion-Gabor滤波器的彩色纹理分割算法研究 [A];提高全民科学素质、建设创新型国家——2006中国科协年会论文集（下册） [C]; 2006年 | | 6 | 曹慧; 一种xml文档相似性距离的计算方法 [A];山东省计算机学会2005年信息技术与信息化研讨会论文集（一） [C]; 2005年 | | 7 | 陈晓辉; 最近邻聚类学习算法的改进初探 [A];第二十二届中国控制会议论文集（下） [C]; 2003年 | | 8 | 彭小宏,阳东升,刘忠; 基于聚类算法的组织协作网设计 [A];2006中国控制与决策学术年会论文集 [C]; 2006年 | | 9 | 方莹,杨尔弘; 基于多特征的句子聚类方法研究 [A];全国第八届计算语言学联合学术会议（JSCL-2005）论文集 [C]; 2005年 | | 10 | 朱翚,芮延年,马纲; 基于模糊灰色理论心电图评价可靠性 [A];第十七届全国过路控制会议论文集 [C]; 2006年 |
|
http://www.cqvip.com/qk/83379X/200711/index.shtml本刊为1999年创刊的中国工程院院刊。它立足于30多个工程科技领域，以科学发现，技术创新，科技前沿，研究成果，典型工程设计及经验总结，重大工程咨询调研报告等为主要报道内容，是荟萃专家学者创新精华，融百...
本刊为1999年创刊的中国工程院院刊。它立足于30多个工程科技领域，以科学发现，技术创新，科技前沿，研究成果，典型工程设计及经验总结，重大工程咨 询调研报告等为主要报道内容，是荟萃专家学者创新精华，融百花为一园，集综合一体的学术期刊。其撰稿人的30%以上来自两院院士，52%来自研究员、教授 级专家，10.2%来自博（硕）士研究生。可以毫不夸张地说，《中国工程科学》是广大专家、学者、科技人员"从里寻她千百度"的、独具智力资源优势的刊 物。
更多简介 >>> 中国工程科学 2007年 第11期目录
无
超高面板坝的关键技术问题马洪琪 曹克明 (4)
非饱和土的塑性体应变与剪应变的相互作用原理王靖涛 (11)
金属矿床地下自动开采的前沿技术及其发展途径李仲学 李翠平 刘双跃 (16)
基于灰色模糊数的公交线网优化研究邓卫 胡启洲 (21)
论新时代的创新人才甘自恒 金又琳 (26)
鄂尔多斯盆地特低渗透砂岩储层裂缝压力敏感性及其开发意义曾联波 史成恩 王永康 李书恒 万晓龙 崔攀峰 (35)
基于调频电台非合作式双基地雷达试验系统研究王炎 (39)
独头巷道空气年龄及通风有效性评价研究王海桥 田峰 黄俊歆 陈涛 (43)
模糊基函数神经网络在线跟踪自学习算法研究许飞云 钟秉林 黄仁 (48)
单站无源定位可观测性评述邓新蒲 (54)
基于并联机构及MR阻尼器的多维减振平台半主动控制研究朱伟 马履中 陈修祥 吴伟光 谢俊 (63)
基于车辆动力学的轨迹跟踪器设计陈杨 刘大学 贺汉根 戴斌 (68)
基于层次的K—means初始化算法汤九斌 陆建峰 唐振民 杨静宇 (74)
旅客列车硬座车厢内气流模拟与浓度场分析张登春 翁培奋 (80)
《中国工程科学》2007年第12期要目预告
|
| |
| | | 1 | TDT3Multilanguage Text Corpus,Version2.0 [M];; 2001年 | | 2 | Pena J, Lozano J, Larranaga P; An Empirical Comparison of Four InitializationMethods for the K-Means A lgorithm [M];Pattern Recognition; 1999年 | | 3 | He J,Lan M,Tan CL,et al; Initialization of cluster refinement algorithms:Areviewand comparative study [M];Proceedings of2004IEEE International Joint Conference on Neural Networks(IJCNN).; 2004年 | | 4 | Ankerst M,Breunig MM,Kriegel HP,et al; OPTICS:Ordering points to identify the clustering structure [M];Proceedings of the International Conference on Management of Data(SIGMOD); 1999年 | | 5 | [M];http://www.nist.gov/speech/tests/tdt/; 年 | | 6 | Bradley PS,Fayyad UM; Refininginitial points forK-means clustering [M];Proceedings of the15thInternational Conference on Machine Learning(ICML); 1998年 | | 7 | Cutting DR,Karger DR,Pedersen JO,et al; Scatter/Gather:Acluster-based approachto browsinglarge document collections [M];Proceedings of the15thInternational Conference on Research and Development in Information Retrieval(SIGIR); 1992年 | | 8 | Pantel P,Lin D; Document clustering with committees [M];Proceedings of the25thInternational Conference on Research and Development in Information Retrieval(SIGIR); 2002年 | | 9 | Steinbach M,Karypis G,Kumar V; Acomparison of document clusteringtechniques [M];Proceedings of KDD Workshop on Text Mining; 2000年 |
|
|
| |
| | | 1 | 李伟,黄颖; 文本聚类算法的比较 [J];科技情报开发与经济; 2006年22期; 240-242 | | 2 | 谭勇,荣秋生; 一个基于K-means的聚类算法的实现 [J];湖北民族学院学报(自然科学版); 2004年01期; 72-74 | | 3 | 赵姝,张燕平,张铃,张媛,陈传明; 覆盖聚类算法 [J];安徽大学学报(自然科学版); 2005年02期; 31-35 | | 4 | 吕佳; 可能性C-Means聚类算法的仿真实验 [J];重庆师范大学学报(自然科学版); 2005年03期; 135-138 | | 5 | 周晓云,孙志挥,张柏礼; 一种大规模高维数据集的高效聚类算法 [J];应用科学学报; 2006年04期; 70-74 | | 6 | 王伟东,芦金婵,张讲社; 基于视觉原理的密度聚类算法 [J];工程数学学报; 2005年02期; 163-166 | | 7 | 刘远超,王晓龙,刘秉权; 一种改进的k-means文档聚类初值选择算法 [J];高技术通讯; 2006年01期; 15-19 | | 8 | 马希荣; 有关面向对象数据库聚类技术的研究 [J];宁夏大学学报(自然科学版); 1997年04期; 66-70 | | 9 | 李凡,高雅卿; 一个模糊分割聚类算法 [J];科学通报; 1990年07期; 81-82 | | 10 | 黄永平,王丽珍; 考虑对象方向关系的密度聚类算法 [J];云南大学学报(自然科学版); 2004年03期; 39-42 |
|
|
| |
| | | 1 | 孙广玲,唐降龙; 一种快速k-均值聚类算法 [A];第六届全国计算机应用联合学术会议论文集 [C]; 2002年 | | 2 | 彭小宏,阳东升,刘忠; 基于聚类算法的组织协作网设计 [A];2006中国控制与决策学术年会论文集 [C]; 2006年 | | 3 | 贾彦国,李培德; Web检索结果聚类算法的改进 [A];2006北京地区高校研究生学术交流会——通信与信息技术会议论文集（上） [C]; 2006年 | | 4 | 李世峰,黄磊,刘昌平; 几种聚类方法的比较 [A];第八届全国汉字识别学术会议论文集 [C]; 2002年 | | 5 | 汪民乐,高晓光,李勇; 新型遗传模糊C-均值聚类算法及其在导弹目标选择中的应用 [A];2007年中国智能自动化会议论文集 [C]; 2007年 | | 6 | 原忠义,唐文忠,许小林; 基于孤立点检测方法对于数据库异常入侵的分析 [A];2006中国控制与决策学术年会论文集 [C]; 2006年 | | 7 | 刘明政,殷建平,张国敏,祝恩; 基于相异增量的聚类算法在彩色图像分割中的应用 [A];2005年全国理论计算机科学学术年会论文集 [C]; 2005年 | | 8 | 宿太学,吕天阳,张锡哲,王钲旋,徐长青; 一个集成多种聚类技术实验平台的整体设计方案和基本模块实现 [A];第十二届全国图象图形学学术会议论文集 [C]; 2005年 | | 9 | 袁里驰,钟义信; 一种新颖的词聚类算法 [A];中国自动化学会、中国仪器仪表学会2004年西南三省一市自动化与仪器仪表学术年会论文集 [C]; 2004年 | | 10 | 黄永光,刘挺,车万翔,胡晓光; 面向变异短文本的快速聚类算法 [A];全国网络与信息安全技术研讨会'2005论文集（下册） [C]; 2005年 |
|
基于层次的K—means初始化算法
摘 要:
K—means算法是一种常用的聚类算法，但是聚类中心的初始化是其中的一个难点。笔者提出了一个基于层次思 想的初始化方法。一般聚类问题均可看作加权聚类，通过层层抽样减少数据量，然后采用自顶向下的方式，从抽样结束层到原始数据层，每层都进行聚类，其中每层 初始聚类中心均通过对上层聚类中心进行换算得到，重复该过程直到原始数据层，可得原始数据层的初始聚类中心。模拟数据和真实数据的实验结果均显示基于层次 抽样初始化的K—means算法不仅收敛速度快、聚类质量高，而且对噪声不敏感，其性能明显优于现有的相关算法。[著者文摘]
2008)11—0o74—06 1 引言聚类分析在模式识别、数据挖掘等领域，起着非常重要的作用。近些年来，随着数据挖掘研究的深人，聚类分析日益受到重视J。K—means算法是较常用 的聚类算法之一，其中聚类中心的初始化对该算法的性能影响很大。若选取的初始聚类中心不合适，将不仅影响收敛速度，还有可能使算法陷人局部最优，但目前许 多参考文献往往绕开该问题。迄今为止，对聚类算法中聚类中心初始化的研究相对较少，且没有简单通用的好方案，重复不同的随机选择似乎成为了事实上的方法。 Pena等对目前常用的初始化算法从聚类质量(有效性)、聚类方法的敏感性(鲁棒性)和收敛速度(即效率)等方面进行了实验比较研究_3』，结果表明随机 初始化方法和Kaufmma方法(KA)在有效性和鲁棒性方面均优于Forgy方法(FA)和Macqueen方法(MA)，其中KA在收敛速度方面优于 随机化方法。最近，Bradly和Fayyad等人对目前的一些初始点选择的方法进行了评述，并指出"在离散数......
Engineering Science
文章编号:
10009-1742（2008）11-0074-06
相关文章:
参考文献(10篇) 主题相关
2008)11—0o74—06 1 引言聚类分析在模式识别、数据挖掘等领域，起着非常重要的作用。近些年来，随着数据挖掘研究的深人，聚类分析日益受到重视J。K—means算法是较常用 的聚类算法之一，其中聚类中心的初始化对该算法的性能影响很大。若选取的初始聚类中心不合适，将不仅影响收敛速度，还有可能使算法陷人局部最优，但目前许 多参考文献往往绕开该问题。迄今为止，对聚类算法中聚类中心初始化的研究相对较少，且没有简单通用的好方案，重复不同的随机选择似乎成为了事实上的方法。 Pena等对目前常用的初始化算法从聚类质量(有效性)、聚类方法的敏感性(鲁棒性)和收敛速度(即效率)等方面进行了实验比较研究_3』，结果表明随机 初始化方法和Kaufmma方法(KA)在有效性和鲁棒性方面均优于Forgy方法(FA)和Macqueen方法(MA)，其中KA在收敛速度方面优于 随机化方法。最近，Bradly和Fayyad等人对目前的一些初始点选择的方法进行了评述，并指出"在离散数......
[参考文献]
- [1]Keim D A,Hinneburg A.Clustering techniques for large data sets-from the past to the future[A].In:Proc Tutorial Notes 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Diego,1999.141 -181
- [2]Duda R O,Hart P E.Pattern Classification and Scene Analysis[M].New York:John Wiley and Sons,1973
- [3]Pena J M,Lozano J A,Larranaga P.An empirical comparison of four initialization methods for the K-means algorithm[J].Pattern Recognition Letters,1999,20(10):27 -40
- [4]Kaufman L,Rousseeuw P J.Finding Groups in Data:An Introduction to Cluster Analysis[M].Wiley,Canada,1990
- [5]Forgy E.Cluster analysis of multivariate data:efficiency vs interpretability of classifications[J].Biometrics 1965,21:768
- [6]MacQueen J B.Some methods for classification and analysis of multivariate observations[A].In:Proc Symposium on Mathematics and Probability,5th,Berkely,Vol 1,AD 669871[M].University of California Press,Berkeley,CA,1967.281-297
- [7]Fayyad U M,Renia C A,Bradley P S.Initialization of iterative refinement clustering algorithm[A].In:Proceedings of the International Conference on Knowledge Discovery and Data Mining(KDD98)[C].New York,1998.94 -98
- [8]Bradley P S,Fayyad U.Refining INITIAL Points for K-means clustering[A].In:Proc 5th Int Conf Machine Learning[C].Morgan Kaumann,1998
- [9]Khan S S,Ahmad A.Cluster center initialization algorithm for K-means clustering[J].Pattern Recognition Letters,2004,25(11):1293 -1302
- [10]Du Q,Faber V,Gunzburger M.Centroidal voronoi tessellations,theory,applications and algorithms[J].SIAM Review,1999,41 (4):637 -676
A Hierarchical-Based Initialization Method for K- Means Algorithm
Tang Jiubin, Lu Jianfeng, Tang Zhenmin, Yang Jingyu （Department of Computer, Nanjing University of Science and Technology, Nanjing 210094, China）
Abstract:
K - means algorithm is one of common clustering algorithms, but the cluster center initialization is a hard problem. In this paper, a hierarchical-based initialization approach is proposed for K -Means algorithm. The general clustering problem is treated as weighted clustering problem, the original data is sampled level by level to reduce the data amount. Then clustering is carried out at each level by top-down. The initial center of each level is mapped from the clustering center of upper level and this procedure is repeated until the original data level is reached. As a result, the initial center for the original data is obtained. Both the experimental results on simulated data and real data show that the proposed method has high converging speed, high quality of clustering and is insensitive to noise, which is superior to some existing clustering algorithms.[著者文摘]
Key words:
hierarchical technique; initial cluster centers; weighted data, K- means clustering
收稿日期: 2006-07-14
修订日期: 2006-09-15
作者简介:
汤九斌（1969-），男，湖北黄石市人，南京理工大学博士生，主要研究领域为模式识别、数据挖掘、专家系统
--
[垃圾桶] 裡沒有會話群組。 當您有超過 6423.752806 MB (還在增加中) 的免費儲存空間時，誰還需要刪除郵件？！
沒有留言:
張貼留言