HDSNN— 基于节点优先级的聚类算法

《HDSNN— 基于节点优先级的聚类算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.paper.edu.cnHDSNN—基于节点优先级的聚类算法张业嘉诚大连理工大学，软件学院，辽宁省大连市（116620）E-mail：linazyjch@hotmail.com摘要：聚类算法是数据挖掘领域的重要研究课题。设计能够处理高维，不同形状，密度分布不均匀的数据集的聚类算法成为目前的研究热点。HDSNN的提出有效的解决了数据集密度分布不均匀等问题。HDSNN首先利用最近邻居节点的方法构建出数据集中节点间的自然链接关系，再建立节点间优先级对数据节点的有效关系进行排序，生成顺序

2、表。最后，通过对顺序表的深度优先搜索生成最终的簇。通过对公共数据集的实验结果证明，HDSNN能够得到正确的聚类结果，很好的解决了密度分布不均匀的数据集的处理，具有优于DBSCAN和OPTICS等基于密度聚类算法的执行效率。关键词:聚类分析;密度分布不均匀;顺序表文献标识码:A中图法分类号:TP311引言聚类分析就是将数据集划分成具有实际意义的、真实的数据节点的集合[1]。K-means是最为通用的聚类算法之一，但是它不能有效的解决噪音点和对不同形状，大数据量的数据集的聚类[2]。分层聚类算法也是聚类算

3、法研究的一个重要分支。它可以有效处理不同形状的数据集，但它对噪音敏感，同时它无法处理密度分布不均匀的数据集[3,4]。DBSCAN是一种基于密度的聚类算法。它能够处理高维，大容量的数据集。同时可以有效的处理任意形状的数据集，并且对噪音不敏感。但DBSCAN无法处理密度分布不均匀的数据集。DBSCAN设定参数Eps（节点的搜索半径）和MinPts（密度阀值）。当数据集中某个节点满足Eps和MinPts，则此节点为中心点，并进行搜索，直到搜索完毕。所以DBSCAN能够查找任意形状的数据集，但它不能处理密度

4、分布不均匀的数据集。因为它的密度是基于中心点的密度阀值，无法确定不同密度簇的中心点。如图1，如果在给定Eps和MinPts的前提下，高密度的数据节点将聚类成为簇，而低密度的数据集将被视为噪音被排除，或者将每个低密度节点视为一个独立的簇。这和真实的聚类结果是违背的。因此，针对DBSCAN的缺陷，提出了OPTICS。它可以有效的解决密度分布不均匀的数据集的聚类问题。但OPTICS的设计复杂，执行效率低。因此，针对DBSCAN和OPTICS等算法的缺陷，提出了基于密度的HDSNN聚类算法。它利用最近邻居节点

5、，建立节点间的优先关系和深度优先搜索等技术对数据集建立自然链接并生成优先级。利用优先级确定最终的聚类结果。实验证明，HDSNN有效解决了DBSCAN和OPTICS存在的问题，能够得到广泛的应用。-1-http://www.paper.edu.cn图1密度分布不均匀数据集Fig1.Datasetofdifferentdensity2HDSNN在高维数据集中，随着维度的增加，单元容量迅速增大。除非节点数量随着维度的增加成指数倍增加，否则密度趋近于0，传统的基于Euclidean距离的密度没有意义。因此，随

6、着维度增加，传统的DBSCAN等基于密度聚类算法的使用难度增加。所以，HDSNN使用了优先级这一相似度测量方法来提高基于密度聚类算法的实际应用。HDSNN的目的是查找数据节点的优先级，通过优先级的比较进行深度优先搜索。这一算法可以自动完成密度分布不均匀的数据集的聚类，可以避免出现无法利用DBSCAN对图1中数据集进行聚类的情况。2.1节点间关系建立HDSNN利用K邻居节点，建立节点间的关系。将数据节点描述为具有依赖关系的网状图。被其它节点所指向的节点具有Authority值，指向其它节点的节点具有Hu

7、b值。未被任何节点所指向的节点标记为噪音点。在聚类过程中，排除这些噪音点。在此利用图1中数据集举例，从而说明HDSNN的聚类过程。K邻居节点是一种有效的启发式方法，可以方便、有效的建立节点间的链接关系。假设节点p和q，则p的K邻居节点为{qq

8、∈Neighborp()}。将数据集表示为节点间具有相互联系的k图，GV(,E)。其中V为数据集中节点的集合，为节点间的连线。E当对节点进行K邻居节点查找，K邻居节点关系建立，如图2。图2数据集K邻居节点图Fig2.GraphofdatasetinKneighb

9、ors设定K=3，则图2中的节点查找各自的最近3个邻居节点，形成网状结构。在这些节点中-2-http://www.paper.edu.cn包含噪音点，因此需要将噪音点排除，生成最终的待排序节点的集合，如图3。图3数据集为去除噪音后待排序的数据集，接下来可以对数据集中节点计算优先级。图3待排序数据集Fig3.weightingdataset2.2数据集排序2.2.1优先级HDSNN采用优先级作为相似度度量方法，可以有效的避免距离矢量在高维数据集聚类中失效的