1、 本科毕业论文 (科研训练、毕业设计 ) 题 目： 基于孤立因子的层次聚类算法与应用 K-means 算法与有效性指标研究 姓 名： 学 院：软件学院 系： 专 业：软件工程 年 级： 学 号： 指导教师（校内）： 职称： 教 授 指导教师（校内）： 职称： 工程师 年 月 日 基于孤立因子的层次聚类算法与应用 第 2 页 基于孤立因子的层次聚类算法与应用 A Clustering Algorithm Based on Outlier-handling Factor and its Applications 摘要 数据挖掘是数据库系统和新的数据库应用的一个有希望的、欣欣向荣的学科前沿。作为一个
2、数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为其它算法的预处理步骤，这些算法再在生成的簇上进行处理。由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 本文在分析 BIRCH1算法与 CLAP4算法的优缺点基础上，结合孤 立点挖掘算法，提出一种基于孤立点预测的层次聚类算法，并且用 Visual C+实现了 CLOF 算法系统。系统包含了输入 /输出、数据预处理、 CLOF 算法核心和图像还原预处理四个模块。 CLOF 算法首先采用随机抽样，通过初步聚类的结果定义子
3、聚类和数据项的孤立因子，并采用全局因子和局部因子定义相结合，改进了孤立点的去除和吸收算法，提高了聚类的质量，降低了对数据输入顺序的敏感性，增强了对噪声数据处理的稳健性，并在大型数据库聚类、图像压缩和图像分割等方面进一步得到验证。 关键词 聚类 BIRCH 算法 CLAP 算 法 K-means 算法 基于孤立因子的层次聚类算法与应用 第 3 页 A Clustering Algorithm Based on Outlier-handling Factor and its Applications Abstract： Data mining is a promising and flourish
4、ing frontier in database systems and new database applications. As a data mining function, cluster analysis can be used as a stand-alone tool to gain insight into the distribution of data, to observe the characteristics of each cluster, and to focus on a particular set of clusters for further analys
5、is. Alternatively, it may serve as a preprocessing step for other algorithms, such as characterization and classification, which would then operate on the detected clusters. Owing to the huge amounts of data collected in databases, cluster analysis has recently become a highly active topic in data m
6、ining research. In this paper, we propose a new hierarchical clustering algorithm to improve the performance of the BIRCH algorithm and CLAP algorithm; furthermore, we achieve the system of CLOF algorithm using Visual C+. The system contains four modules: input/output, data preprocess, the kernel of
7、 CLOF algorithm, the preprocess of image revivification. Based on preprocessing the random samples, we define an outlier-handling factor (OF) relative to cluster feature entry as well as data item. This new algorithm can be used to improve clustering quality and eliminate the sensitivity of input or
8、der through the global OF and local OF. Finally, we investigate applications of the algorithm proposed for dealing with large database, pixel classification and image compression. Keyword： Clustering BIRCH CLAP K-means 基于孤立因子的层次聚类算法与应用 第 4 页 目 录 第一章 引言 6 1.1 什么是数据挖掘 6 1.2 什么是聚类分析 6 1.3 什么是 CLOF 算法 7
9、 第二章 CLOF 算法系统设计需求分析 8 2.1 引言 8 2.1.1 编写目的 8 2.1.2 项目背景 8 2.1.3 名词解释 9 2.2 任务概述 9 2.2.1 目标 9 2.3 数据描述 9 2.3.1 静态数据 10 2.3.2 动态数据 10 2.4 功能需求 10 2.4.1 流程图 10 2.4.2 功能描述 10 2.4.3 数据与功能的对应关系 11 2.5 性能需求 12 2.5.1 时间要求 12 2.5.2 适应性 12 2.5.3 可用性 12 2.6 运行环境描述 12 2.6.1 硬件设备 12 2.6.2 支持软件 12 第三章 CLOF 算法系统模块
10、设计 13 3.1 CLOF 算法的数据预 处理 13 3.1.1 数据挖掘过程中数据预处理的原因与意义 13 3.1.2 数据预处理的基本功能 13 3.1.3 数据预处理的主要方法 13 3.2 CLOF 算法的数据预处理中的数据采样 14 3.2.1 数据挖掘过程中数据的采样 14 3.2.2 数据挖掘不同领域中的采样 14 3.2.3 数据挖掘中的采样方法 15 3.3 数据挖掘的聚类算法 15 3.3.1 CLOF 算法数据预处理中采用的 K-means 算法 16 3.4 数据预处理模块设计中定义的主要方法 18 3.5 CLOF 算法的图像还原预处理 19 3.6 CLOF 算法
11、系统界面 20 基于孤立因子的层次聚类算法与应用 第 5 页 第四章 CLOF 算法系统测试结果 21 结论 23 致谢语 23 参考文献 24 基于孤立因子的层次聚类算法与应用 第 6 页 第一章 引言 本文在分析 BIRCH1算法与 CLAP4算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法，并且用 Visual C+实现了 CLOF 算法系统。系统包含了输入 /输出、数据预处理、 CLOF 算法核心和图像还原预处理四个模块。本人负责数据预处理模块和图像还原预处理模块，输入 /输出模块由张涛同学负责， CLOF 算法核心模块则由吴楠楠同学负责。 本项目的知识背景
12、主要是基于数据挖掘和聚类分析 两个概念。 1.1 什么是数据挖掘 数据挖掘（ Data Mining， DM） 就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的，人们事先不知道的、但又是潜在的有用信息和知识的过程。 数据挖掘，又称为数据库中知识发现（ Knowledge Discovery from Database,简称 KDD） ,它是一个从大量的数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。整个知识挖掘 (KDD)过程是由若干挖掘步骤组成，而数据挖掘仅是其中的一个主要步骤。整个知识挖掘的步骤有： 1. 数据清洗 (Data Cleaning),其作用
13、就是清除数据噪声和与挖掘主题明显无关的数据； 2. 数据集成 (Data Integration),其作用就是将来自多数据源中的相关数据组合到一起； 3. 数据转化 (Data Transformation)，其作用就是将数据转化成易于进行数据挖掘的数据存储形式； 4. 数据挖掘 (Data Mining)，它是知识挖掘的一个基本步骤，其作用就是利用智能方法挖掘数据模式或规律知识； 5. 模式评估 (Pattern Evaluation)，其作用就是根 据一定评估标准 (Interesting Measures)从挖掘结果筛选出有意义的模式知识； 6. 知识表示（ Knowledge Pres
14、entation） ，其作用就是利用可视化和知识表达技术，向用户展示所挖掘出的相关知识。 尽管数据挖掘仅仅是整个知识挖掘过程中的一个重要步骤，但由于目前工业界、媒体、数据库研究领域中，“数据挖掘”一词已被广泛使用并被普遍接受，因此也广义地使用“数据挖掘”一词来表示整个知识挖掘过程，即数据挖掘就是一个从数据库、数据仓库、或其它信息资源库的大量数据中发掘出有趣的知识。 1.2 什么是聚类分析 聚类（ Clustering） 就是将物理或抽象对象的集 合分组成为由类似的对象组成的多个类的过程，并使得同一个类内的数据对象具有较高的相似度 ,而不同类中的数据对象是不相似的。 聚类分析源于许多研究领域，包
15、括数据挖掘，统计学，生物学，以及机器学习。聚类分析是以相似性为基础，把一组个体划分成若干个具有一定意义的子类 ,即“物以类聚”，其目的是使得属于同一类别的个体之间尽可能相同，而不同类别上的个体间尽可能相异。聚类分析也称群分析，簇群分析等，是数值分类学的一个分支，并在数据挖掘、图像分割、模式分类及决策制定等众多领域中广泛应用，同时由于不需要任何应用领域知识，因而受到 广大数据挖掘研究人员的广泛重视。其中在面向大型数据库方面，目前流行的主要算法有 BIRCH1、基于孤立因子的层次聚类算法与应用 第 7 页 CURE6等。 BIRCH 算法通过采用多阶段聚类技术，利用计算机有限的主存和辅存资源，尽可
16、能多地去除孤立点，实现对大规模数据库的聚类分析，它具有良好的伸缩性和处理噪音能力，许多数据挖掘研究人员在 BIRCH 算法的基础上提出了改进算法，提高了运行速度和改进了聚类质量， CLAP4算法就是其中代表之一。 数据挖掘的大多数算法主要研究的问题是发现“大模式”，即输入数据的主要特征；另一方面是研究“小模式”问题即孤立点 挖掘，孤立点探测和分析有非常广泛的应用，如欺诈监测、定制市场、医疗分析等领域。 在 BIRCH 算法中，孤立点是指在那些密度较低或数量相对少得多的子聚类，它们对整体的聚类模型影响很小，因而在重建 CF(Cluster Feature)树时，把它们当成孤立点从内存写入硬盘，留
17、出更多的内存空间吸收余下的数据项；而在孤立点挖掘中，孤立点的定义是指那些没有“足够多”邻居的对象，它代表一些特别的意义。 其实两者定义是一致的，都是指在它的某个领域中只有相对少的邻居，另外 BIRCH 算法检测孤立点是为了去除它，而孤立点挖掘则是为 了寻找一些有特别意义的数据对象。 我们考虑把对孤立点的检测与对孤立点的去除结合在一起，在 BIRCH 算法和 CLAP 算法基础上，提出一个基于孤立因子的层次聚类算法 CLOF（ Clustering algorithm based on Outlier-handling Factor and random-sampling）。 1.3 什么是 C
18、LOF 算法 CLOF 是对 BIRCH 算法的改进，主要体现在 CF 树重建时对孤立点的处理算法上，因此主要给出改进的 CF 树重建算法 : 1. 随机抽样 N 个数据，用全局聚类算法进行预处理，获得聚类数 、聚类中心、半径、直径等初步聚类结果； 2. 不断地把数据项插入 CF 树，直到 CF 树重建，如果数据已全部插入 ,则转 8； 3. 计算每个子聚类 CFi的全局孤立因子 i ，然后检查输入的数据量是否超过全局因子 Gi ，若不超过则转 5； 4. 对 CF 树所有子聚类的数据进行聚类，求局部孤立因子 i ,然后 修正 CFi的全局孤立因子 i ； 5. 计算满足两个条件的子聚类所含的
19、数据个数：子聚类所含数据相对少得多（低于平均值）、孤 立因子 i 0 ； 6. 如果去除的孤立点个数太少（低于 5%） ，则降低 0 ，转 5；如果去除的孤立点个数太多（高于 50%），则提高 0 ,转 5； 7. 把去除的孤立点在硬盘中按其孤立因子的大小分别放入相应的回收站 ,如果磁盘空间没有溢出则转 2，继续插入剩下的数据。 8. 按孤立因子从小到大次序依次吸收回收站的孤立点，直至 CF 树饱和为止； 9. 转入 BIRCH 算法的阶段二（ 即有选择地压缩）； 基于孤立因子的层次聚类算法与应用 第 8 页 第二章 CLOF 算法系统设计需求分析 2.1 引言 我们通过本节内容来说明关于整个
20、需求分析说明书的综述，包括本文的编写目的、项目背景、名词解释等。 2.1.1 编写目的 1. 明确程序的编写目的及在整个项目过程中的作用。 2. 提高开发效率。 3. 作为以后工作的重要参考。 2.1.2 项目背景 在分析 BIRCH 算法与 CLAP 算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法 (CLOF)。 BIRCH（ Balance Iterative Reducing and Clustering using Hierarchies） 算法由四阶段组成： (1)装载； (2)有选择地压缩； (3)全局聚类； (4)有选择地提炼。阶段 1 的主要任务是
21、利用计算机可用的主存和辅存空间，通过一次扫描数据库的所有数据，建立起初始的驻留内存的 CF 树；阶段 2 是可选的阶段，决定于阶段 3 采取的全局算法；阶段 3 的主要任务是采用一个全局或局部的聚类算法对 CF 树的子聚类进行聚类。阶段 4 也是可选的，通过数据库的再次扫描，进一步去除孤立点，提高聚类精度。可见 BIRCH 算法是通过采用多阶段聚类技术，利用计算机有限的主存和辅存资源，实现对大规模数据库的聚 类分析。 在数据量高速增长的今天，大数据集的数据挖掘面临着： (1)解决可用内存量是有限的而数据集是任意大的问题，由于内存增长的速度远小于数据量的增长速度，大部分数据挖掘面临的问题是内存数
22、据集之比非常小。 (2)降低 I/O 成本，一方面要解决同样的容量存放更多的内容，另一方面程序执行过程中尽量减少访问次数。 BIRCH 算法很好地解决数据挖掘所面临的问题。 BIRCH 特别适合大数据集，它将数据集首先以一种很紧凑的压缩格式存放，直接在压缩的数据集上进行聚类而不是在原始的数据集上聚类，它的 I/O 成本与数据集的大小呈线性关系，单遍 扫描数据集就可生成较好的聚类，可选的另一遍或多遍扫描用于进一步地改进聚类质量。 BIRCH 试图利用可用的资源来生成最好的聚类结果。给定有限的主存，一个重要的考虑是最小的 I/O 时间。 BIRCH 采用了一种多阶段聚类技术：数据集合的单遍扫描产生
23、了一个基本的聚类，一或多遍的额外扫描可以进一步地改进聚类质量。这个算法的计算复杂性是 O(n),这里的 n是对象的数目。 BIRCH 算法具有对象数目的线性伸缩性，及较好的聚类质量。但是，既然 CF 树的每个节点由于大小限制只能包含有限数目的条目，一个 CF 树节点并不总是对于用户所认为 的一个自然聚类。而且，如果簇不是球形的， BIRCH 不能很好地工作，因为它用了半径或直径的概念来控制聚类的边界。 BIRCH 算法具有良好的算法伸缩性和处理噪声的能力，但也有下述 3 个缺点： 1. BIRCH 算法有一个聚类的预处理过程，需要扫描所有数据来产生一个初始聚类结果。基于孤立因子的层次聚类算法与
24、应用 第 9 页 然后，需要再次扫描所有数据，进一步优化初始的聚类结果。对于大规模数据库，两次扫描所有的数据大大降低了算法效率。 2. 簇直径只是定义了一簇点之间的聚类距离，并没有定义叶节点的直径大小。所以，只要叶节点还有空位，就可以容纳新的点，既使新的点会使叶节点直径变 得很大，降低了叶节点的紧密度。这样的结果会降低搜索的精度，影响聚类质量。 3. BIRCH 算法采用自顶向下的搜索策略，是一种局部搜索算法，它找到的叶节点不一定是最好的。这会导致在数据项输入顺序不好时，产生错误的聚类。 CLAP（ Clustering Algorithm Based on Random-sampling a
25、nd Cluster-feature） 算法的描述： 由 Zhou Bing 等 4提出的 CLAP 算法即基于随机抽样和聚类特征的聚类算法从 BIRCH算法出发，针对其局限性，主要在三个方面进行改进 :采用高效的随机取样算法 8 ，从数据库中抽取一部分数据进行聚类预处理，避免了预处理时对数据库的全面扫描，节省了运行时间； 设立了分叶直径 和簇直径 一起控制 CF 树的构造，要求插入新的叶节点后分叶的簇直径不超过 ，否则要求产生新的叶节点来容纳新的数据项 ,增加了叶节点的紧密度，提高了搜索效率，改进了聚类质量； 在寻找最“亲”的叶子结点方面，通过设立全局因子 ，采取全局搜索策略和局部搜索策略相
26、结合，从而降低了数据输入顺序对聚类质量的影响。 实验测试结果表明，该算法在聚类速度和聚类质量方面均优于 BIRCH 算法。 CLAP 算法的核心是通过定义分叶直径加强同一个叶子结点的子聚类之间的紧密度，从而提高了聚类质量，但在对孤立点（ Outlier） 的处理上没有作进一步的阐述。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。然而，在一些应用中（如欺骗检测），罕见的事件可能比正常出现的那些更有趣。因此孤立点挖掘则是为了寻找一些有特别意义的数据对象。 基于以上分析，我们在 BIRCH 算法与 CLAP 算法的基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法 (CLOF)。 2
27、.1.3 名词解释 BIRCH 算法： Balanced Iterative Reducing and Clustering using Hierarchies CLAP 算法： Clustering Algorithm Based on Random-sampling and Cluster-feature CLOF 算法： Clustering Algorithm Based on Outlier-handling Factor and Random-sampling 2.2 任务概述 我们通过本节内容来说明本项软件项目开发的意图以及所要达到的目标。 2.2.1 目标 利用大型数据库聚类、
28、 图像压缩和图像分割等方法，在分析 BIRCH 算法与 CLAP 算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法。，改进孤立点的去除和吸收算法，提高了聚类的质量，降低了对数据输入顺序的敏感性，增强了对噪声数据处理的稳健性。 2.3 数据描述 数据分为 静态数据和动态数据。所谓静态数据，指在运行过程中主要作为参考的数据，它们在很长一段时间内不会变化，一般也不会随着运行而改变；所谓动态数据，包括所有在基于孤立因子的层次聚类算法与应用 第 10 页 运行中要发生变化的数据，以及在运行中要输入、输出的数据。 2.3.1 静态数据 1. 公共的图像文件 Mandrill.b
29、mp(512*512 像素 ) 2. 公共的图像文件 Perpers.bmp(512*512 像素 ) 图 1 Mandrill.bmp 图 2 Perpers.bmp 3 美国家庭情况网络调查 Internet 数据库，共 33832 条记录，每条记录有 29个属性。 2.3.2 动态数据 1. 聚类结果文档 (*.txt)：包含聚类数量，输出维数，中心点。 2. 初步聚类结果 k 类。 3. 产生 Internet 数据库聚类结果。 4. 经过算法处理后得到经过聚类处理的图像。 2.4 功能需求 本节是我们需求分析的重点章节，包括流程图、功能描述、数据与功能的对应关系等。 2.4.1 流程图 图 3 CLOF 系统流程图 2.4.2 功能描述 对最底层的功能所要完成的功能进行详细描述，填入下表中： 数据输入(Access 数据库数据或图像 ) K-means算法预处理 CLOF算法核心处理 数据输出(Access数据库数据或图像 ) K-means算法聚类处理
