基于自然邻居的聚类分析和离群检测算法研究_程东东黄金龙朱庆生著.pdf

书 书 书内容提要本书是有关数据挖掘中基于邻域概念的聚类分析和离群检测算法的专著。主要内容如下：在自然邻居概念的基础上提出了局部核心点、准聚类中心、自然核心点等概念；在局部核心点、准聚类中心和自然核心点概念的基础上提出了适用于复杂流形结构数据集的基于中心的聚类算法、层次的聚类算法和最小生成树聚类算法；对聚类评价标准概念及其现状进行分析，并提出了新的适用于复杂流形数据的聚类评价标准；还提出了无参的离群点检测算法，并利用互为领域图的信息，提出了离群簇检测算法。本书可供具有一定数据挖掘基础，并对聚类离群感兴趣的学生和研究者参考。图书在版编目（C I P）数据基于自然邻居的聚类分析和离群检测算法研究 程东东，黄金龙，朱庆生著.上海：上海交通大学出版社，2 0 1 9I SBN9 7 8 7 3 1 3 2 2 0 7 0 7.基.程黄朱.数据采集 研究.TP 2 7 4中国版本图书馆C I P数据核字（2 0 1 9）第2 3 0 9 8 6号基于自然邻居的聚类分析和离群检测算法研究J I YUZ I RANL I NJUDEJUL E IF ENX IHEL I QUNJ I ANCESUANFAYANJ I U 著 者：程东东 黄金龙 朱庆生出版发行：上海交通大学出版社地 址：上海市番禺路9 5 1号邮政编码：2 0 0 0 3 0 电 话：0 2 1 6 4 0 7 1 2 0 8印 制：江苏凤凰数码印务有限公司 经 销：全国新华书店开 本：7 1 0mm1 0 0 0mm 11 6 印 张：1 4.7 5字 数：2 5 4千字版 次：2 0 1 9年1 1月第1版 印 次：2 0 1 9年1 1月第1次印刷书 号：I SBN9 7 8 7 3 1 3 2 2 0 7 0 7定 价：5 8.0 0元版权所有 侵权必究告读者：如发现本书有印装质量问题请与印刷厂质量科联系联系电话：0 2 5 8 3 6 5 7 3 0 9前言|FOREWORD 聚类分析与离群检测是数据挖掘领域中非常热门的两个研究课题。聚类分析的主要目标是将数据对象按照相似度划分成不同的簇，使得在相同簇中的数据对象彼此相似，而不同簇中的数据对象彼此不同。离群检测是找出其行为很不同于预期对象的过程。聚类分析和离群检测可广泛地应用于模式识别、图像处理、人工智能、医学、基因科学、地质学和管理学等领域。本书对聚类分析和离群检测的基础理论和算法进行了分析，对包含复杂结构数据集的聚类问题和离群检测方法进行了研究，为解决现有聚类分析和离群检测存在的问题提供了新的思路。首先，本书针对现有聚类分析和离群检测存在的效率问题，提出基于自然邻居的局部核心点的概念和用准聚类中心及自然核心点进行解决的思路。当需要对大量数据进行聚类的时候，传统的聚类算法需要大量的时间。因此，我们考虑从数据集中选出代表点，然后将剩余的数据对象划分到其代表所属的簇中。局部核心点及准聚类中心都是通过邻域信息获得数据集中的代表点，剩余的数据对象划分到其代表所属的簇中，从而把原始数据集划分成多个子簇，这为解决复杂流形数据集的聚类分析问题提供了方便。这一内容在本书第3章进行了详细的介绍和讨论。其次，本书针对现有的聚类算法，包括基于中心的聚类算法、层次的聚类算法和最小生成树聚类算法等存在的问题，分别提出了新的基于中心的聚类算法DPLORE和QCC，新的层次聚类算法H i CLUBS、HCLORE和1HCBNR，以及新的最小生成树聚类算法LORE MST和NCP MST，用于解决现有的聚类算法中存在的效率问题、噪声点问题和无法适用于复杂流形结构数据集等问题。第46章对这些内容进行了详细的分析和讨论。再次，本书针对现有聚类的内部度量指标存在的问题，提出了一种基于局部核心点的聚类度量指标LCCV。针对现有的内部度量指标无法评估复杂流形簇的问题，本书提出使用最短路径度量局部核心点之间的不相似度，然后评估每个局部核心点的紧凑度和分离度，从而确定其聚类质量，最后将每个局部核心点的平均聚类质量作为LCCV指标。由于使用最短路径度量局部核心点之间的不相似度，LCCV能够有效地评估复杂流形簇。第7章对该内容进行了详细分析和讨论。最后，本书针对现有离群检测算法存在的问题，提出了新的基于自然邻居的离群检测算法。将自然邻居的概念引入离群点检测中，利用自然邻居的无参特性提出了无须参数k值的离群点检测算法，解决了现有离群点检测算法需要参数k并对k值敏感的问题。另外，本书还基于互为邻域图提出了专门用于离群簇检测的粗糙聚类算法，从而解决了用于离群簇检测的聚类算法参数多的问题。第8章对该内容进行了详细的分析和讨论。本书在撰写过程中，参考了大量国内外文献资料，对聚类分析和离群检测的相关知识进行了介绍和分析。本书是笔者多年在聚类分析和离群检测分析领域从事科研方面工作的系统总结，可供对聚类分析和离群检测感兴趣的读者学习和参考。由于笔者能力有限，本书难免存在不足之处，望广大读者不吝赐教。程东东、黄金龙 长江师范学院朱庆生 教授 重庆大学2 0 1 9年4月2基于自然邻居的聚类分析和离群检测算法研究目录|CONTENTS第1章 绪论1 1.1 数据挖掘的研究背景和意义1 1.2 聚类分析和离群检测的研究现状51.2.1 聚类分析研究现状51.2.2 离群检测研究现状9 1.3 本章小结1 2第2章 聚类分析和离群检测1 3 2.1 聚类分析1 32.1.1 聚类分析概述1 32.1.2 聚类算法概述1 52.1.3 聚类结果评估2 5 2.2 离群检测3 02.2.1 离群的定义3 02.2.2 离群检测算法概述3 12.2.3 离群检测评价3 5 2.3 本章小结3 6第3章 基于自然邻居的局部核心点和准聚类中心3 7 3.1 自然邻居3 7 3.2 基于自然邻居的局部核心点4 1 3.3 准聚类中心及自然核心点4 513.3.1 准聚类中心4 63.3.2 自然核心点5 1 3.4 本章小结5 3第4章 基于中心的聚类算法5 4 4.1 现有的基于中心的聚类算法存在的问题5 4 4.2 基于局部核心点的DP算法DPLORE5 64.2.1 基于局部核心点的DP算法基本思想5 64.2.2 实验结果及分析5 9 4.3 基于准聚类中心的聚类算法QCC7 14.3.1 QCC算法的基本思想7 14.3.2 QCC算法实验及分析7 4 4.4 本章小结8 9第5章 层次聚类算法9 1 5.1 现有的层次聚类算法存在的不足9 1 5.2 基于自然邻居的层次聚类算法H iCLUBS9 25.2.1 H iCLUBS算法基本思想9 25.2.2 实验及分析9 7 5.3 基于局部核心点的层次聚类算法HCLORE1 0 15.3.1 HCLORE算法基本思想1 0 15.3.2 实验及分析1 0 6 5.4 基于噪声去除的层次聚类算法HCBNR1 2 25.4.1 HCBNR算法的基本思想1 2 25.4.2 实验及分析1 2 3 5.5 本章小结1 2 6第6章 最小生成树聚类算法1 2 7 6.1 基于最小生成树的聚类算法存在的问题1 2 7 6.2 基于局部核心点的最小生成树算法LORE MST1 2 96.2.1 LORE MST算法基本思想1 2 92基于自然邻居的聚类分析和离群检测算法研究6.2.2 实验及分析1 3 3 6.3 基于自然核心点的最小生成树聚类分析算法NCP MST1 4 56.3.1 NCP MST算法过程1 4 66.3.2 实验分析1 5 0 6.4 本章小结1 5 8第7章 聚类结果内部评估方法1 6 0 7.1 现有的聚类结果内部评估方法存在的不足1 6 0 7.2 基于局部核心点的聚类结果评估方法1 6 17.2.1 局部核心点之间基于图的距离1 6 27.2.2 LCCV指标1 6 27.2.3 LCCV指标分析1 6 37.2.4 基于LCCV指标的层次聚类算法1 6 5 7.3 实验结果及分析1 6 67.3.1 人工数据集上的实验结果1 6 67.3.2 真实数据集上的实验结果1 7 47.3.3 LCCV指标与其他聚类算法结合的实验结果1 7 6 7.4 讨论1 7 97.4.1 局部核心点的合理性1 7 97.4.2 噪声点的影响1 8 0 7.5 本章小结1 8 2第8章 离群检测1 8 3 8.1 现有离群检测算法分析1 8 3 8.2 基于自然邻居的无参离群检测算法NOF1 8 68.2.1 NOF算法及相关定义1 8 68.2.2 实验结果及分析1 8 9 8.3 基于互为邻域图的离群簇检测算法ROCF1 9 78.3.1 ROCF算法及相关定义1 9 78.3.2 实验结果及分析2 0 3 8.4 本章小结2 1 03目 录第9章 总结和展望2 1 1 9.1 总结2 1 1 9.2 展望2 1 3参考文献2 1 5索引2 2 54基于自然邻居的聚类分析和离群检测算法研究书 书 书第1章绪 论 数据挖掘是现在大数据时代下对大量数据进行分析的重要途径和手段，可以得到大数据中包含的有价值的知识。聚类分析和离群检测是数据挖掘中非常重要的两个研究方向。本章主要分析了数据挖掘的研究背景和意义，以及现有聚类分析和离群检测算法及其面临的问题。1.1 数据挖掘的研究背景和意义随着计算机技术、互联网的发展和普及，各行各业都积累了大量的数据。利用大数据发现其蕴含的有价值的信息是大数据技术的目标。但是如何从大量的数据中发现新颖的、潜在的、有用的知识，是人们迫切需要解决的问题。在这种背景下，数据挖掘技术应运而生。但是现实生活中产生和存储的数据量以指数级别的速率在不断增长，数据的快速增长使得数据挖掘变得更具有挑战性，越来越多的研究者参与其中，经过不断研究和发展，数据挖掘技术得以不断完善。其研究成果不仅在人工智能、机器学习、模式识别、图像处理等计算机领域得到广泛应用，而且在农业、医学、航空航天等更多的社会领域也得到普遍应用。因此，对数据挖掘技术的研究具有重要的意义。数据挖掘1也称为知识发现（k n ow l e d g ed i s c o v e r yf r omd a t a，KDD），是利用相关的数据挖掘算法对大量的数据进行分析，从而发现其中一些新的、隐藏的、有价值的知识的过程。数据挖掘的主要过程如图1 1所示，包括数据准备、数据挖掘和评估结果。数据准备是从数据源获得原始数据，利用数据清理、数据集成、数据选择和数据变化等技术对原始数据进行预处理，从而得到数据挖掘适用的数据集。1数据挖掘是利用相关的数据挖掘算法，对预处理得到的数据进行分析，从而得到数据集中有用的信息。评估结果是根据不同的度量指标，对数据挖掘得到的结果，利用可视化和知识表示技术，向用户提供可理解的知识。图1 1 数据挖掘过程数据挖掘需要处理的数据多种多样，包括关系数据库、数据仓库、事物数据，还有其他类型的数据，如时间序列数据，文本、图像、视频、音频等多媒体数据，以及图、网状数据和万维网数据等。随着数据结构越来越复杂，数据挖掘所面临的挑战也越来越多。数据挖掘的任务主要包括频繁模式挖掘、关联规则分析、分类、预测、聚类分析和离群检测等。研究者针对不同的任务提出了不同的方法。频繁模式挖掘是从事务数据集中找出多次反复出现的联系。关联规则分析是从反复出现的联系中分析事物之间存在的必然联系，从而获得具有价值的信息。分类是在有监督的条件下，将一些已知的样本作为训练样本，经过算法的训练得到有用的模型或提取出数据中蕴含的特征，即分类器，然后利用该分类器对未知样本进行分类。聚类分析是在无监督的条件下，根据某种数据对象之间的相似度量或不相似度量，将一个数据集划分成多个子簇的过程，使得在同一个簇中的数据对象彼此相似而在不同簇中的数据对象彼此不同。离群检测是从大量的数据集中识别出不同于正常数据分布或预期对象的异常对象的过程。聚类分析和离群检测作为数据挖掘中非常重要的两个基本研究方向，其在现实中的应用也相当广泛。因此，聚类分析和离群检测已成为现今数据挖掘中非常热门的研究课题2。“物以类