一种基于密度和层次的聚类算法的研究

《一种基于密度和层次的聚类算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中文图书分类号：TP391密级：公开UDC：004学校代码：10005硕士专业学位论文PROFESSIONALMASTERDISSERTATION论文题目：一种基于密度和层次的聚类算法的研究论文作者：吴浩同专业类别/领域：计算机技术指导教师：王丹教授论文提交日期：2017年5月UDC：004学校代码：10005中文图书分类号：TP391学号：S201407122密级：公开北京工业大学硕士专业学位论文（全日制）题目：一种基于密度和层次的聚类算法的研究英文题目：RESEARCHONACLUSTERINGALGORITHMBASEDON

2、DENSITYANDHIERARCHY论文作者：吴浩同专业类别/领域：计算机技术研究方向：计算机软件与理论申请学位：工程硕士专业学位指导教师：王丹教授所在单位：信息学部答辩日期：2017年5月授予学位单位：北京工业大学独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢

3、意。签名：吴浩同日期：2017年5月17日关于论文使用授权的说明本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。（保密的论文在解密后应遵守此规定）签名：吴浩同日期：2017年5月17日导师签名：王丹日期：2017年5月17日摘要摘要聚类算法作为数据挖掘算法中常用的一类方法正受到越来越多的关注。其中基于密度峰值查找的快速聚类算法CFSFDP（Clusteringbyfastsearchandfin

4、dofdensitypeaks）算法是一种密度型的聚类算法，通过绘制并观察决策图获取密度峰值，将密度峰值点作为聚类中心，再根据聚类中心进行聚类。CFSFDP算法速度快，容易理解并实现，可以探测到不同形状的数据。但是该算法也有两点不足：（1）CFSFDP算法在聚类时由于人为指定截断距离??的缘故，可能会产生多个密度峰值，违背了一个密度峰值对应着一个类簇的聚类中心的算法本意，如果一个类簇出现多个密度峰值，在进行聚合时则会出现一定偏差。（2）聚类中心的选取依赖于算法中生成的决策图，用户通过观察决策图然后人为地挑选出聚类中心。这种方法不仅

5、会中断整个算法流程，使得算法效率降低，同时也可能出现多选或漏选密度峰值的问题。为了应对上述两个问题，本文以CFSFDP算法为基础，提出了一种基于密度和层次的聚类算法。通过引入系统演化算法的聚合判别算法，让改进后的CFSFDP算法先获得初步聚类结果，然后利用判别算法对初步聚合结果以层次聚类的方式再进行二次聚合，将本该归于同一类簇的对象聚合在一起。本文的主要工作如下：1、提出了一种新的基于密度和层次的聚类算法。算法主要分为两个阶段，第一阶段首先用基于密度的CFSFDP算法对数据进行初步的聚类，在得到聚合结果之后，利用引入系统演化算法中

6、的判别算法对结果中的多个类簇进行聚合判别，通过计算类簇间边缘区域的分离度和类簇聚合前后的离散度，从而判断两个类簇能否进行聚合，将应该属于同一类簇的多个小类簇进行聚合。2、提出了一种基于权值差计算的自动获取CFSFDP算法中聚类中心的方法。通过计算数据集中每个点的权值并降序排序，然后计算排序后相邻点的权值差，基于权值差，找到最后一次出现权值较大变化的临界点，将权值比临界点大的点设为聚类中心。同时为了防止数据集中密度不一对聚类中心选取造成的影响，本文设置了多个截断距离，目的是为了尽可能获取多个聚类中心，然后将距离较近的中心合并成一个。

7、3、引入了系统演化算法的聚合判别算法用于层次聚类中类簇的聚合判断。为了提高聚合判别算法的计算效率，本文修改了原算法中对边界区域和次边界区域中点的选取方式，相比原方法减少了比较的次数；通过增加一个最近点距离表，使得算法在求最小平均距离时，同样可以减少一定的比较次数。为了解决原算法-I-北京工业大学工程硕士专业学位论文不能处理轻微重叠类簇的聚合问题，将计算类簇聚合前后误差平方和的变化率作为补充方法，帮助原算法解决对轻微重叠类簇的聚合判断问题。4、针对CFSFDP算法有时可能会将一个类簇分成两个或多个的问题，本文利用改进后的聚合判别算法

8、，设计了两个链表数组作为类簇的存储结构，依托两个链表数组，通过层次聚类的方式实现对改进后CFSFDP算法聚类结果的二次聚类。5、通过多组实验证明本文提出的新的基于密度和层次的聚类算法相比原算法在准确度上得到了一定的提升，同时针对于多种形状和不同密度