主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
丁军娣,马儒宁,陈松灿.基于多项式核的结构化有向树数据聚类算法.软件学报,2008,19(12):3147-3160
基于多项式核的结构化有向树数据聚类算法
Polynomial Kernel Based Structural Clustering Algorithm by Building Directed Trees
投稿时间:2007-10-20  修订日期:2008-03-28
DOI:
中文关键词:  数据聚类  多项式核  邻域密度因子  有向树  图论  重叠数据  结构性作用  结构化聚类
英文关键词:data clustering  polynomial kernel  neighborhood-based density factor  directed tree  graph theory  overlapping data  structural role  structural clustering
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60632050 (国家自然科学基金)
作者单位
丁军娣 南京理工大学 计算机科学与技术学院,江苏 南京 210094
南京航空航天大学 信息科学与技术学院,江苏 南京 210016 
马儒宁 南京航空航天大学 理学院,江苏 南京 210016 
陈松灿 南京航空航天大学 信息科学与技术学院,江苏 南京 210016 
摘要点击次数: 4408
全文下载次数: 4809
中文摘要:
      各个点在数据内部的组织结构中自然地扮演着3种不同的结构性角色,分别是毂、质心和野值.在基于邻域的聚类算法中,邻域密度因子能够识别分离数据集中的毂、质心和野值.但是,邻域密度因子对有噪声和重叠的数据往往失效.为了解决该问题,引入了基于多项式核的邻域密度因子,并在有向树框架下,提出了一种结构化的数据聚类算法,其计算复杂度线性于输入数据的大小.对带有噪声和重叠的数据集,该算法能够找到所有显著的、任意形状的不均衡聚类.在人工和真实数据集上的实验结果都证实了该算法的有效性和快速性.
英文摘要:
      Within the internal organization of the data, the data points respectively play three different structural roles: the hub, centroid and outlier. The neighborhood-based density factor (NDF) used in the neighborhood based clustering (NBC) algorithm has the ability of identifying which points act as hubs, centriods or outliers in separated-well data set. However, NDF often works poorly in the circumstances of noise and overlapping. This paper introduces a polynomial kernel based neighborhood density factor (PKNDF) to address this issue. Relying on the PKNDF, a structural data clustering algorithm is further presented which can find all salient clusters with arbitrary shapes and unbalanced sizes in a noisy or overlapping data set. It builds clusters into the framework of directed trees in graph theory and thereby each point is scanned only once in the process of clustering. Hence, its computational complexity is nearly linear in the size of the input data. Experimental results on both synthetic and real-world datasets have demonstrated its effectiveness and efficiency.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利