1、本科毕业论文(科研训练、毕业设计)题 目：基于孤立因子的层次聚类算法与应用BIRCH 算法与 CLOF 算法姓 名：学 院：软件学院系：专 业：软件工程年 级：学 号：指导教师（校内）： 职称： 指导教师（校内）： 职称： 年 月 日基于孤立因子的层次聚类算法与应用2基于孤立因子的层次聚类算法与应用摘要 在分析 BIRCH 算法与 CLAP 算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法。该算法首先采用随机抽样，通过初步聚类的结果定义子聚类和数据项的孤立因子，并采用全局因子和局部因子定义相结合，改进了孤立点的去除和吸收算法，提高了聚类的质量，降低了对数据输入顺序的
2、敏感性，增强了对噪声数据处理的稳健性，并在大型数据库聚类、图像压缩和图像分割等方面进一步得到验证。关键词 聚类 BIRCH 算法 CLAP 算法 孤立因子 CLOF 算法基于孤立因子的层次聚类算法与应用3A Clustering Algorithm Based on Outlier-handling Factor and its ApplicationsAbstract In this paper, we propose a new hierarchical clustering algorithm to improve the performance of the BIRCH algorit
3、hm and CLAP algorithm. 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 order through the global OF and loca
4、l OF. In final, we investigate applications of the algorithm proposed for dealing with large database, pixel classification and image compression.Keyword Clustering BIRCH CLAP Outlier-handling Factor CLOF目录第一章 引言 .6第二章 CLOF 算法系统设计需求分析 .82.1 引言 .82.1.1. 编写目的 .82.1.2. 项目背景 .82.1.3. 名词解释 .92.2 任务概述 .92
5、.2.1 目标 .92.3 数据描述 .92.3.1 静态数据 .102.3.2 动态数据 .102.4 功能需求 .102.4.1 流程图 .102.4.2 功能描述 .102.5 性能需求 .112.5.1 时间要求 .122.5.2 适应性 .122.6 运行环境描述 .122.6.1 硬件设备 .122.6.2 支持软件 .12第三章 算法与实现 .131 CF 类 .131.1 CF 树的定义 .131.2 CF 类属性 .131.3 CF 类成员函数 .132 主函数 .142.1 函数原型 .142.2 参数说明 .142.3 功能说明 .142.4 CLOF 算法描述 .143
6、 输入接口 .153.1 功能说明 .153.2 Input 类成员变量 .153.3 Input 类成员函数 .154 输出接口 .154.1 功能说明 .164.2 Output 类成员变量 .16基于孤立因子的层次聚类算法与应用54.3 Output 类成员函数 .165 软件界面 .16第四章 实验结果 .17比较性实验一: .17比较性实验二: .17应用性实验之一: .18第五章 结论 .19致谢语 .19参考文献 .20基于孤立因子的层次聚类算法与应用6第一章引言本文在分析 BIRCH1算法与 CLAP4算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法
7、，并且用 Visual C+实现了 CLOF 算法系统。系统包含了输入/输出、数据预处理、CLOF 算法核心和图像还原预处理四个模块。数据挖掘（Data Mining，DM ）就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的，人们事先不知道的、但又是潜在的有用信息和知识的过程。由于数据挖掘是一门受到来自各种不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。其中，最常用的术语是“知识发现”和“数据挖掘” 。相对来讲，数据挖掘主要流行于统计界（最早出现于统计文献中） 、数据分析、数据库和管理信息系统界；而知识发现则主要流行于人工智能和机器学习界。数据挖掘可粗略
8、地理解为三部曲：数据准备（Data Preparation） 、数据挖掘，以及结果的解释评估（Interpretation and Evaluation） 。根据数据挖掘的任务分类有如下几种：分类或预测模型数据挖掘、数据总结、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等。根据数据挖掘的对象分类有如下若干种数据源：关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据、异质数据库、遗产（Legacy）数据库，以及 Web 数据源。根据数据挖掘的方法分类可粗分为：统计方法、机器学习方法、神经网络方法和数据库方法。统计方法中，可细分为：回归分析
9、（多元回归、自回归等） 、判别分析（贝叶斯判别、费歇尔判别、非参数判别等） 、聚类分析（系统聚类、动态聚类等） 、探索性分析（主元分析法、相关分析法等） 、以及模糊集、粗糙集、支持向量机等。机器学习中，可细分为：归纳学习方法（决策树、规则归纳等） 、基于范例的推理 CBR、遗传算法、贝叶斯信念网络等。神经网络方法，可细分为：前向神经网络（BP 算法等） 、自组织神经网络（自组织特征映射、竞争学习等）等。数据库方法主要是基于可视化的多维数据分析或 OLAP 方法，另外还有面向属性的归纳方法。聚类（Clustering ）就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类分析源
10、于许多研究领域，包括数据挖掘，统计学，生物学，以及机器学习。聚类分析是以相似性为基础，把一组个体划分成若干个具有一定意义的子类,即“物以类聚” ，其目的是使得属于同一类别的个体之间尽可能相同，而不同类别上的个体间尽可能相异。聚类分析也称群分析，簇群分析等，是数值分类学的一个分支，并在数据挖掘、图像分割、模式分类及决策制定等众多领域中广泛应用，同时由于不需要任何应用领域知识，因而受到广大数据挖掘研究人员的广泛重视。其中在面向大型数据库方面，目前流行的主要算法有BIRCH1、CURE 6等。BIRCH 算法通过采用多阶段聚类技术，利用计算机有限的主存和辅存资源，尽可能多地去除孤立点，实现对大规模数
11、据库的聚类分析，它具有良好的伸缩性和处理噪音能力，许多数据挖掘研究人员在 BIRCH 算法的基础上提出了改进算法，提高了运行速度和改进了聚类质量，CLAP 4算法就是其中代表之一。数据挖掘的大多数算法主要研究的问题是发现“大模式” ，即输入数据的主要特征；另一方面是研究“小模式”问题即孤立点挖掘，孤立点探测和分析有非常广泛的应用，如欺诈监测、定制市场、医疗分析等领域。 10基于孤立因子的层次聚类算法与应用7在 BIRCH 算法中，孤立点是指在那些密度较低或数量相对少得多的子聚类，它们对整体的聚类模型影响很小，因而在重建 CF 树时，把它们当成孤立点从内存写入硬盘，留出更多的内存空间吸收余下的数
12、据项；而在孤立点挖掘中，孤立点的定义是指那些没有“足够多”邻居的对象，它代表一些特别的意义。 其实两者定义是一致的，都是指在它的某个领域中只有相对少的邻居，另外 BIRCH 算法检测孤立点是为了去除它，而孤立点挖掘则是为了寻找一些有特别意义的数据对象。我们考虑把对孤立点的检测与对孤立点的去除结合在一起，在 BIRCH 算法和 CLAP 算法基础上，提出一个基于孤立因子的层次聚类算法 CLOF（Clustering aLgorithm based on Outlier-handling Factor and random-sampling） 。基于孤立因子的层次聚类算法与应用8第二章 CLOF 算法系统设计需求分析2.1 引言本项目分为三个部分：K-Means 算法实现、CLOF 算法实现及数据库输入输出和图像的处理，由三个人共同完成，其中 CLOF 算法是由本人实现。2.1.1. 编写目的1. 明确程序的编写目的及在整个项目过程中的作用。2. 作为以后工作的重要参考。2.1.2. 项目背景在分析 BIRCH 算法与 CLAP 算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法（CLOF） 。BIRCH（Balance Iterative Reduci
