基于数据分区的最近邻优先聚类算法

《基于数据分区的最近邻优先聚类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据计算机科学2005"401．32N0．12基于数据分区的最近邻优先聚类算法王鑫王洪国张建喜谷建军(山东师范大学信息管理学院济南250014)摘要聚类是教据舵掘领域的一十重要研究方向。最近邻优先吸收(NNAF)算法可以快速进行聚类并且能有效处理噪声点，但当数据密度和聚类间的距离不均匀时聚类质量较差。本文在分析NNAF算法不足的基础上，提出了一种基于数据分lg．的NNAF算法一PNNAF算法，较好地改善了聚类质量。美键词数据挖掘．聚类，数据分区，最近邻优先吸收AData-Partitioning-BasedNear∞t-N

2、eilghbors-n'stClusteringAlgorithmWANGXinWANGHong。GuoZHANGJiarrXiGUJiarrJun(InformationManagementSchoolofShandongNormalUniversity，Jinan250014)AbstractClusteringis8nimportantresearchdirectioninthefieldofDataMining．ThispaperanalysestheNearestNeighborsAbsorbedFirst(NNAF

3、)clusteringalgorithm．Thisalgorithmcanclusterquicklywithnoisy．However，clusteringqualitywilldegndewhentheclusterdensityanddistancebetweenclustersarenoteVellInthispaper，aNea—rest-NeighborwFirstclusteringalgorithmbasedOildatapartitioningispmposed．TheDewalgorithmimproves

4、thequall—tyofclustering．KeywordsDataMining，Clustering，风tapartitioning，Nearestneighborfirst1引言近lO年来，数据挖掘Ⅲ逐渐成为数据库和人工智能等研究领域的一个热点。聚类(Clustering)是数据挖掘中重要的研究课题之一。所谓聚类，就是将物理或抽象对象的集合组成为由类似的对象组成的多个类或簇的过程。由聚类所生成的簇是一组数据对象的集合，同一簇中的对象尽可能相似，而不同簇中的对象尽可能相异。1．1相关工作迄今为止，数据库研究人员已经提出了

5、许多聚类算法，主要有以下几类：划分方法{主要有K-Means口]，K-Medioda(PAM)以及它们的变种CLARA和cIARANS。层次方法：主要有BIRCH算法口]、CUR群4]算法、最短距离法和CHA-MALEON算法等。基于密度的方法l主要有DBSCAN[”，OVHCS，DENCLUE等。基于网格的方法I主要有STINGL“方法，WaveCluster算法，CLIQUE算法。基于模型的方法：典型的基于模型的聚类方法有神经网络方法和统计的方法。1．2本文的工作首先介绍了最近邻优先吸收算法NNAF(NearestNeig

6、h—borsAbsorbedFirst)的基本思想，分析其不足；然后针对这些不足提出了基于数据分区(data-partitioning)的最近邻优先吸收算法一PNNAF算法；接着对新算法进行分析，最后得出了结论。2最近邻优先吸收(NNAF)算法NNAF算法是基于“同类相近”的思想提出的一种改进的最短距离聚类算法。最短距离法又称最近邻连接法，其基本思想是把两个类的距离定义为两类中距离最近的元索之间的距离。并依此逐次选择最“靠近”的类聚集，直到满足终止条件。NNAF(NearestNe曙hborsAbsorbedHrst)算法的基

7、本思想是：空间中的每一点和与之最近的点属于同一类的可能性最大。如果两个距离最近的点之间的距离小于J(用户输人的距离阐值)，那幺就认为它们属于同一类。当某一聚类所包含的元素个数大于q(用户输人的数量阈值)时，则该类数据成为一个真正的聚类；否则为噪声数据集合。定义1设V是高维数据空间中的点集合，v一{m，血，⋯，A}，P-∈VtPzC-V，Pl和p2之间的距离记为D(p，，血)；给定距离罔值d，d2>O，则：】)如果D(A，A)

8、)如果MN(p1)=血，并且D(向，声2)≤d，那么Pz与A属于同一类。即：当Pt点属于第一类，而伽尚没有归类时，则把P。点也归为第一类；当P-尚没有归类，而Pz点属于第一类时，则把A点也归为第一类；当芦，点属于第一类，而加属于第二类时，则把第一类和第二类合并为一个新类，并把