基于孤立因子的层次聚类算法与应用 ——随机抽样与图像压缩-毕业论文

基于孤立因子的层次聚类算法与应用随机抽样与图像压缩本科毕业论文(科研训练、毕业设计)题 目：基于孤立因子的层次聚类算法与应用随机抽样与图像压缩姓 名：学 院：软件学院系：专 业：软件工程年 级：学 号：指导教师（校内）： 职称： 指导教师（校内）： 职称： 年 月 日基于孤立因子的层次聚类算法与应用A Clustering Algorithm Based on Outlier-handling Factor and its Applications摘要 数据挖掘是数据库系统和新的数据库应用的一个有希望的、欣欣向荣的学科前沿。作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为其他算法的预处理步骤，这些算法再在生成的簇上进行处理。由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。本文在分析BIRCH算法与CLAP算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法，并且用Visual C+实现了CLOF算法系统。系统包含了输入/输出、数据预处理、CLOF算法核心和图像还原预处理四个模块。CLOF算法首先采用随机抽样，通过初步聚类的结果定义子聚类和数据项的孤立因子，并采用全局因子和局部因子定义相结合，改进了孤立点的去除和吸收算法，提高了聚类的质量，降低了对数据输入顺序的敏感性，增强了对噪声数据处理的稳健性，并在大型数据库聚类、图像压缩和图像分割等方面进一步得到验证。关键词 聚类 BIRCH算法 CLAP算法 图像压缩第 22 页 共 25 页A Clustering Algorithm Based on Outlier-handling Factor and its ApplicationsAbstract：Data mining is a promising and flourishing 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 analysis. 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 mining 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 CLOF algorithm, the preprocess of image revivification. Keyword： ClusteringBIRCHCLAP K-means目 录第一章 引言5第二章 CLOF算法系统设计需求分析72.1引言72.1.1编写目的72.1.2项目背景72.2任务概述92.2.1目标92.3数据描述92.3.1静态数据92.3.2动态数据102.4功能需求102.4.1流程图102.4.3数据与功能的对应关系112.5性能需求112.5.1时间要求112.5.2适应性122.6运行环境描述122.6.1硬件设备122.6.2支持软件12第三章随机抽样与图像压缩133.1数据库的输入输出143.1.1 目的143.1.3处理流程163.2 图像处理163.2.1目的163.2.2图片背景知识163.2.2.1BMP文件组成163.2.3图片处理类183.2.4重构图片方法思想183.2.5处理图像实例193.2.6程序输入输出接口与实例20第四章CLOF算法系统测试结果21第五章 结论23致谢语23参考文献25第一章 引言本文在分析BIRCH1算法与CLAP4算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法，并且用Visual C+实现了CLOF算法系统。系统包含了输入/输出、数据预处理、CLOF算法核心和图像还原预处理四个模块。数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的，人们事先不知道的、但又是潜在的有用信息和知识的过程。它是一门涉及面很广的交叉学科，包括机器学习、数理统计、神经网络、数据库、模式识别、粗糙集、模糊数学等相关技术。由于数据挖掘是一门受到来自各种不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。其中，最常用的术语是知识发现和数据挖掘。相对来讲，数据挖掘主要流行于统计界（最早出现于统计文献中）、数据分析、数据库和管理信息系统界；而知识发现则主要流行于人工智能和机器学习界。数据挖掘可粗略地理解为三部曲：数据准备（Data Preparation）、数据挖掘，以及结果的解释评估（Interpretation and Evaluation）。 根据数据挖掘的任务分类有如下几种：分类或预测模型数据挖掘、数据总结、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等。根据数据挖掘的对象分类有如下若干种数据源：关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据、异质数据库、遗产（Legacy）数据库，以及Web数据源。根据数据挖掘的方法可粗分为：统计方法、机器学习方法、神经网络方法和数据库方法。统计方法中，可细分为：回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、费歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探索性分析（主元分析法、相关分析法等）、以及模糊集、粗糙集、支持向量机等。机器学习中，可细分为：归纳学习方法（决策树、规则归纳等）、基于范例的推理CBR、遗传算法、贝叶斯信念网络等。神经网络方法，可细分为：前向神经网络（BP算法等）、自组织神经网络（自组织特征映射、竞争学习等）等。数据库方法主要是基于可视化的多维数据分析或OLAP方法，另外还有面向属性的归纳方法。聚类（Clustering）就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类分析源于许多研究领域，包括数据挖掘统计学、生物学、以及机器学习。聚类分析是以相似性为基础，把一组个体划分成若干个具有一定意义的子类,即“物以类聚”，其目的是使得属于同一类别的个体之间尽可能相同，而不同类别上的个体间尽可能相异。聚类分析也称群分析，簇群分析等，是数值分类学的一个分支，并在数据挖掘、图像分割、模式分类及决策制定等众多领域中广泛应用，同时由于不需要任何应用领域知识，因而受到广大数据挖掘研究人员的广泛重视。其中在面向大型数据库方面，目前流行的主要算法有BIRCH1、CURE6等。BIRCH算法通过采用多阶段聚类技术，利用计算机有限的主存和辅存资源，尽可能多地去除孤立点，实现对大规模数据库的聚类分析，它具有良好的伸缩性和处理噪音能力，许多数据挖掘研究人员在BIRCH算法的基础上提出了改进算法，提高了运行速度和改进了聚类质量，CLAP4算法就是其中代表之一。数据挖掘的大多数算法主要研究的问题是发现“大模式”，即输入数据的主要特征；另一方面是研究“小模式”问题即孤立点挖掘，孤立点探测和分析有非常广泛的应用，如欺诈监测、定制市场、医疗分析等领域。10在BIRCH算法中，孤立点是指在那些密度较低或数量相对少得多的子聚类，它们对整体的聚类模型影响很小，因而在重建CF树时，把它们当成孤立点从内存写入硬盘，留出更多的内存空间吸收余下的数据项；而在孤立点挖掘中，孤立点的定义是指那些没有“足够多”邻居的对象，它代表一些特别的意义。 其实两者定义是一致的，都是指在它的某个领域中只有相对少的邻居，另外BIRCH算法检测孤立点是为了去除它，而孤立点挖掘则是为了寻找一些有特别意义的数据对象。我们考虑把对孤立点的检测与对孤立点的去除结合在一起，在BIRCH算法和CLAP算法基础上，提出一个基于孤立因子的层次聚类算法CLOF（Clustering aLgorithm based on Outlier-handling Factor and random-sampling）。第二章 CLOF算法系统设计需求分析2.1引言我们通过本节内容来说明关于整个需求规格说明书的综述，包括本文的编写目的、范围、名词和术语、参考资料等。2.1.1编写目的1. 明确程序的编写目的及在整个项目过程中的作用。2. 提高开发效率。3. 作为以后工作的重要参考。2.1.2项目背景在分析BIRCH算法与CLAP算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法（CLOF）。BIRCH（Balance Iterative Reducing and Clustering using Hierarchies）算法由四阶段组成：（）装载；（）有选择地压缩；（）全局聚类；（）有选择地提炼。阶段的主要任务是利用计算机可用的主存和辅存空间，通过一次扫描数据库的所有数据，建立起初始的驻留内存的CF树；阶段是可选的阶段，决定于阶段3采取的全局算法；阶段的主要任务是采用一个全局或局部的聚类算法对CF树的子聚类进行聚类。阶段4也是可选的，通过数据库的再次扫描，进一步去除孤立点，提高聚类精度。可见BIRCH算法是通过采用多阶段聚类技术，利用计算机有限的主存和辅存资源，实现对大规模数据库的聚类分析。在数据量高速增长的今天，大数据集的数据挖掘面临着：解决可用内存量是有限的而数据集是任意大的问题，由于内存增长的速度远小于数据量的增长速度，大部分数据挖掘面临的问题是内存数据集之比非常小。降低I/O成本，一方面要解决同样的容量存放更多的内容，另一方面程序执行过程中尽量减少访问次数。BIRCH算法很好地解决数据挖掘所面临的问题。BIRCH特别适合大数据集，它将数据集首先以一种很紧凑的压缩格式存放，直接在压缩的数据集上进行聚类而不是在原始的数据集上聚类，它的I/O成本与数据集的大小呈线性关系，单遍扫描数据集就可生成较好的聚类，可选的另一遍或多遍扫描用于进一步地改进聚类质量。BIRCH试图利用可用的资源来生成最好的聚类结果。给定有限的主存，一个重要的考虑是最小的I/O时间。BIRCH采用了一种多阶段聚类技术：数据集合的单遍扫描产生了一个基本的聚类，一或多遍的额外扫描可以进一步地改进聚类质量。这个算法的计算复杂性是O(n),这里的n是对象的数目。BIRCH算法具有对象数目的线性伸缩性，及较好的聚类质量。但是，既然CF树的每个节点由于大小限制只能包含有限数目的条目，一个CF树节点并不总是对于用户所认为的一个自然聚类。而且，如果簇不是球形的，BIRCH不能很好地工作，因为它用了半径或直径的概念来控制聚类的边界。BIRCH算法具有良好的算法伸缩性和处理噪声的能力，但也有下述3个缺点：1. BIRCH算法有一个聚类的预处理过程，需要扫描所有数据来产生一个初始聚类结果。然后，需要再次扫描所有数据，进一步优化初始的聚类结果。对于大规模数据库，两次扫描所有的数据大大降低了算法效率。2. 簇直径只是定义了一簇点之间的聚类距离，并没有定义叶节点的直径大小。所以，只要叶节点还有空位，就可以容纳新的点，既使新的点会使叶节点直径变得很大，降低了叶节点的紧密度。这样的结果会降低搜索的精度，影响聚类质量。3. BIRCH算法采用自顶向下的搜索策略，是一种局部搜索算法，它找到的叶节点不一定是最好的。这会导致在数据项输入顺序不好时，产生错误的聚类。CLAP（Clustering Algorithm Based on Random-sampling and Cluster-feature）算法的描述：CLAP算法即基于随机抽样和聚类特征的聚类算法从BIRCH算法出发，针对其局限性，主要在三个方面进行改进：采用高效的随机取样算法8，从数据库中抽取一部分数据进行聚类预处理，避免了预处理时对数据库的全面扫描，节省了运行时间；设立了分叶直径和簇直径一起控制CF树的构造，要求插入新的叶节点后分叶的簇直径不超过，否则要求产生新的叶节点来容纳新的数据项,增加了叶节点的紧密度，提高了搜索效率，改进了聚类质量；在寻找最“亲”的叶子结点方面，通过设立全局因子，采取全局搜索策略和局部搜索策略相结合，从而降低了数据输入顺序对聚类质量的影响。实验测试结果表明，该算法在聚类速度和聚类质量方面均优于BIRCH算法。CLAP算法的核心是通过定义分叶直径加强同一个叶子结点的子聚类之间的紧密度，从而提高了聚类质量，但在对孤立点（Outlier）的处理上没有作进一步的阐述。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。然而，在一些应用中（如欺骗检测），罕见的事件可能比正常出现的那些更有趣。因此孤立点挖掘则是为了寻找一些有特别意义的数据对象。基于以上分析，我们在BIRCH算法与CLAP算法的基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法（CLOF）。2.1.3名词解释BIRCH算法： Balanced Iterative Reducing and Clustering using HierarchiesCLAP算法： Clustering Algorithm Based on Random-sampling and Cluster-featureCLOF算法： Clustering Algorithm Based on Outlier-handling Factor and Random-samplingCF树： Clustering Feature Tree2.2任务概述在分析BIRCH算法与CLAP算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法。该算法首先采用随机抽样，通过初步聚类的结果定义子聚类和数据项的孤立因子，并采用全局因子和局部因子定义相结合，改进了孤立点的去除和吸收算法，提高了聚类的质量，降低了对数据输入顺序的敏感性，增强了对噪声数据处理的稳健性，并在大型数据库聚类、图像压缩和图像分割等方面进一步得到验证2.2.1目标利用大型数据库聚类、图像压缩和图像分割等方法，在分析BIRCH算法与CLAP算法的优缺点基础上，结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法。，改进孤立点的去除和吸收算法，提高了聚类的质量，降低了对数据输入顺序的敏感性，增强了对噪声数据处理的稳健性。2.3数据描述数据分为静态数据和动态数据。所谓静态数据，指在运行过程中主要作为参考的数据，它们在很长一段时间内不会变化，一般也不会随着运行而改变。所谓动态数据，包括所有在运行中要发生变化的数据，以及在运行中要输入、输出的数据。2.3.1静态数据美国家庭情况网络调查Internet数据库，共有33832条记录，每条记录有29个属性。公共图像文件Mandrill.bmp (512*512像素)，分割成1*2图块，生成2维向量近13万条作为原始数据。图1：Mandrill.bmp(512*512像素) 图2：Perpers(512*512像素）2.3.2动态数据 聚类结果文档（*.txt）：包含聚类数量，输出维数，中心点。例：428.1805668016194311.5535762483131162.843.160.993243243243216.84290540540543.84455958549223123.020725388601 K类，K个中心点，最小半径，最小直径，平均半径，平均直径。 产生Internet数据库聚类结果。 经过算法处理后得到经过聚类处理的图像。2.4功能需求2.4.1流程图K-MEAN算法预处理数据输出ACCESS数据库数据或图像K-MEAN算法聚类处理CLOF算法处理生成聚类结果数据输入（ACCESS数据库数据或图像） 这五大部分将进一步分成三大块由项目小组三个人负责完成。第一块为数据的输入和输出及图像处理由本人负责；第二块为K-MEAN算法预处理和聚类处理由刘裴寰负责；第三块为CLOF算法处理生成聚类结果由吴楠楠负责。2.4.2功能描述对最底层的功能所要完成的功能进行详细描述，填入下表中：功能名称功能标识符功能详细描述数据输入01用DAO方法访问ACCESS数据库读入美国家庭情况网络调查internet数据库构建CDIB类读入mandrill.bmp作为数据处理对象K-MEAN算法预处理02通过预处理获得初步聚类结果k类、k个聚类中心、平均半径R、平均直径D、最小半径R、最小直径D，提供给CLOF算法核心模块使用最为重要的k个输入变量(kn),CLOF算法03CLOF算法通过采用多阶段聚类技术，利用计算机有限的主存和辅存资源，尽可能多地去除孤立点，实现对大规模数据库的聚类分析CLOF算法由四阶段组成：（）装载；（）有选择地压缩；（）全局聚类；（）有选择地提炼K-MEAN算法聚类04通过处理获得数据集Xi（i=1，,N；N是随机选取的数据总量）和聚类结果K类，提供给图象还原模块使用数据输出05用DAO方法访问ACCESS数据库读出经过聚类后得美国家庭情况网络调查internet数据库构建CDIB类读出经过处理后得mandrill.bmp2.4.3数据与功能的对应关系用一张矩阵图说明功能描述中的各个功能与数据描述中的静态数据、动态数据之间的对应关系，例如：功能标识符输入输出01internet数据库mandrill.bmp待处理数据对象02待处理数据对象K类，k个中心点，最小半径，最小直径，平均半径，平均直径03待处理数据对象分类后的数据对象04分类后的数据对象类的中心值05待处理数据对象新的数据库文件和处理后得mandrill.bmp2.5性能需求2.5.1时间要求时间要求相对较低。本程序的主要目的在于用于验证及改进算法，因此对于时间运行不做太高要求。2.5.2适应性处理数据产生异常时能正常退出数据库。2.6运行环境描述本程序的运行环境分为硬件环境和软件环境2.6.1硬件设备处理器为Intel Pentium 4,内存512M，硬盘为60G。2.6.2支持软件 Windows2000操作系统 Microsoft ACCESSVisual C+ 6.0. PhotoShop 6.0第三章随机抽样与图像压缩前言本程序的核心是建立聚类特征树并通过聚类特征树处理相关数据，聚类特征树是一个高度平衡树(Cluster Feature Tree) ,它存储了层次聚类的聚类特征。树中的非叶子结点有后代或“孩子”，它们存储了其孩子的CF(Cluster Feature)的总和；叶子结点储存了所有的子聚类；它有两个参数：分支因子B(或L)和阈值T。其中分支因子表示每个非叶子节点孩子的最大数目；分支因子表示每个叶子节点最多有个CF项；阈值表示存储在树的叶子结点中的子聚类的最大直径CLAP算法的核心是通过定义分叶直径加强同一个叶子结点的子聚类之间的紧密度，从而提高了聚类质量，但在对孤立点的处理上没有作进一步的阐述。目前基于孤立点挖掘研究主要集中在三个方面：基于统计的孤立点检测、基于距离的孤立点检测、基于偏离的孤立点检测，相应地定义了许多算法。我们的研究是基于孤立因子预测和随机抽样的层次聚类算法CLOFCLOF主要体现在CF树重建时对孤立点的处理算法上，因此主要给出改进的CF树重建算法（如图1）1. 随机抽样N个数据，用全局聚类算法进行预处理，获得聚类数、聚类中心、半径、直径等初步聚类结果；2. 不断地把数据项插入CF树，具体插入算法见3，4，直到CF树重建，如果数据已全部插入,则转8；3. 根据3.1描述的算法，计算每个子聚类CFi的全局孤立因子，然后检查输入的数据量是否超过全局因子Gi ，若不超过则转5；4. 对CF树所有子聚类的数据进行聚类，求局部孤立因子,然后根据3.1描述修正CFi的全局孤立因子；5. 计算满足两个条件的子聚类所含的数据个数：子聚类所含数据相对少得多（低于平均值）、孤立因子；6. 如果去除的孤立点个数太少（低于5%），则降低，转5；如果去除的孤立点个数太多（高于50%），则提高,转5；7. 把去除的孤立点在硬盘中按其孤立因子的大小分别放入相应的回收站,如果磁盘空间没有溢出则转2，继续插入剩下的数据。8. 按孤立因子从小到大次序依次吸收回收站的孤立点，直至CF树饱和为止；9. 转入BIRCH算法的阶段二；CLOF算法的预处理同样要调用其它的聚类算法。在本算法中采取K-Mean算法10，其基本步骤如下，详细算法见10：1. 给定划分数K，迭代终止条件，初始划分,目标函数,i=0；2. 根据最近原则，对所有的数据重新进行划分，得到新的划分和；3. 如果,则停止，否则i=i+1，转2；为了确定最佳聚类数，选用Sun.H-S.Wang-Q.Jiang有效性指标（2003）9，在判定时具有优良的稳定性和准确性,而且可以准确地处理类间有交叠或有多孤立点的情况。 (4)其中表示类内紧凑度，表示类间分离度本程序的流程为初始化一个空的CF树，调用预处理模块K-menas算法以估计全局的特征、以使聚类过程有一定的全局的方向性而且结果更为精确，然后逐个读取数据并且插入到CF树中，必要时（如内存不足）进行重建、回收孤立点，在插入数据达到一定数量时（程序中设定为所有数据的50%、70%、90%）再度调用K-means算法修正前次估计的参数，最后通过链表输出最终数据到新文件中。程序分成三大块，第一块为数据的输入和输出及图像处理由本人负责；第二块为K-MEAN算法预处理和聚类处理由刘裴寰负责；第三块为CLOF算法处理生成聚类结果由吴楠楠负责。本部分的工作是将来自数据库和图像的数据以nn维的形式传入CF树，作为CF树的数据来源。经过算法分析计算后将原数据库和图像的数据按照聚类后的结果形成新的数据最后将之写入数据库或重新形成图像，通过图像等的前后变化对比就可以比较算法的优劣。从而达到验证算法的目的。下面将分数据库和图像处理两部分来介绍数据的输入和输出过程。3.1数据库的输入输出3.1.1 目的 通过大型数据库聚类前后对比来比较分析BIRCH算法与CLAP算法的优缺点并结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法。通过前后对比就可以论证算法的优劣3.1.2 数据库输入输出方法的实现采用DAO访问数据库，DAO是Microsoft Jet数据库引擎中内置的编程接口。DAO用Microsoft Jet数据库引擎提供的整套的数据访问对象，其中封装了各种常用的数据库对象，如表，查询，和Recordsets。DAO通常用来访问本地桌面数据资源如Microsoft Access，Microsoft FoxPro等也可以用来访问远程数据资源。 Visual C提供了对DAO的封装，MFC DAO封装了DAO的大部分功能，从而Visual C程序就可以使用Visual C提供的DAO类方便的访问Microsoft Jet数据库，编写简洁的数据库应用程序。CDaoWorkspace：CDaoWorkspace对象可以让一个用户从登陆到离开期间对指定的密码保护的数据库会话进行全过程管理CDaoDatabase代表远程数据资源或桌面数据库的连接CDaoRecordSet封装了从某个数据库表中选择的记录集CDaoTableDef表示基本表或附加表的定义。每个DAO数据库对象包括一个称为TableDef的集合，包含所有存储的DAO表定义对象，CDaoTableDef对象可以用来控制表定义本算法用到的类方法如下：CDaoDatabase属性GetName 返回当前使用的数据库名称操作Close关闭数据库连接Create创建DAO数据库对象，初始化CDaoDatabase对象DeleteTableDef 删除数据库中表的定义。getTableDefCount 返回数据库中定义的表的数目open向某个数据库建立一个连接CDaoRecordSet构造器CDaoRecordSet构造CDaoRecordSet对象 Close关闭记录集Open动态或快照方式创建某个表的新记录集 操作AddNew准备增加新记录，调用Update方法结束Delete从记录集中删除当前记录Update完成AddNew操作，向数据源保存新的的数据Move把当前记录从移动指定的记录数MoveNext在记录集中把下一条记录作为当前记录GetFieldCount返回一个值，代表记录集中的字段数GetFieldValue返回记录集中字段的值 构造器Append向数据库中新增一个表CDaoTableDef构造一个CDaoTableDef对象Close关闭打开的TableDef对象Create创建一个表Open打开数据库TableDef集合中已有的TableDef对象GetFielCount返回表中字段数GetRecordCount返回表中记录数SetName设置表名 操作DreateField创建表中的字段DeleteField删除表中的字段输入每次将一行数据读入数组并用GetFielCount方法得到的数字作为维数传入算法程序。3.1.3处理流程数据输出ACCESS数据库数据或图像K-MEAN算法聚类处理CLOF算法处理生成聚类结果K-MEAN算法预处理数据输入（ACCESS数据库数据或图像）3.2 图像处理3.2.1目的通过图像压缩和分割前后对比来比较分析BIRCH算法与CLAP算法的优缺点并结合孤立点挖掘算法，提出一种基于孤立点预测的层次聚类算法。前期工作读入一个bmp格式的图片将每一个像素值或该对应像素的颜色表的索引值作为输入数据交给程序，最后再将处理后的象素值作为新的值恢复成图像。通过前后对比就可以论证算法的优劣。3.2.2图片背景知识3.2.2.1BMP文件组成BMP文件由文件头、位图信息头、颜色信息和图形数据四部分组成。文件头主要包含文件的大小、文件类型、图像数据偏离文件头的长度等信息；位图信息头包含图象的尺寸信息、图像用几个比特数值来表示一个像素、图像是否压缩、图像所用的颜色数等信息。颜色信息包含图像所用到的颜色表，显示图像时需用到这个颜色表来生成调色板，但如果图像为真彩色，既图像的每个像素用24个比特来表示，文件中就没有这一块信息，也就不需要操作调色板。文件中的数据块表示图像的相应的像素值，图像的像素值在文件中的存放顺序为从左到右，从下到上，也就是说，在BMP文件中首先存放的是图像的最后一行像素，最后才存储图像的第一行像素，但对与同一行的像素，则是按照先左边后右边的顺序存储的；另外一个需要读者朋友关注的细节是：文件存储图像的每一行像素值时，如果存储该行像素值所占的字节数为4的倍数，则正常存储，否则，需要在后端补0，凑足4的倍数。3.2.2.2 BMP文件头typedef struct tagBITMAPFILEHEADERWORD bfType; / 位图文件的类型，必须为“BM”DWORD bfSize; / 位图文件的大小，以字节为单位WORD bfReserved1; / 位图文件保留字，必须为0WORD bfReserved2; / 位图文件保留字，必须为0DWORD bfOffBits; / 位图数据的起始位置，以相对于位图文件头的偏移量表示，以字节为单位 BITMAPFILEHEADER；该结构占据14个字节3.2.2.3位图信息头BMP位图信息头数据用于说明位图的尺寸等信息。其结构如下：typedef struct tagBITMAPINFOHEADERDWORD biSize; / 本结构所占用字节数LONG biWidth; / 位图的宽度，以像素为单位LONG biHeight; / 位图的高度，以像素为单位WORD biPlanes; / 目标设备的平面数不清，必须为1WORD biBitCount/ 每个像素所需的位数，必须是1(双色), 4(16色)，8(256色)或24(真彩色)之一DWORD biCompression; / 位图压缩类型，必须是 0(不压缩),1(BI_RLE8压缩类型)或2(BI_RLE4压缩类型)之一DWORD biSizeImage; / 位图的大小，以字节为单位 DWORD biClrUsed;/ 位图实际使用的颜色表中的颜色数DWORD biClrImportant;/ 位图显示过程中重要的颜色数 BITMAPINFOHEADER；该结构占据40个字节。3.2.2.4位图数据位图的一个像素值所占的字节数：当biBitCount=1时，8个像素占1个字节当biBitCount=4时，2个像素占1个字节；当biBitCount=8时，1个像素占1个字节；当biBitCount=24时,1个像素占3个字节，此时图像为真彩色图像。当图像不是为真彩色时，图像文件中包含颜色表，位图的数据表示对应像素点在颜色表中相应的索引值，当为真彩色时，每一个像素用三个字节表示图像相应像素点彩色值，每个字节分别对应R、G、B分量的值，这时候图像文件中没有颜色表。上面我已经讲过了，Windows规定图像文件中一个扫描行所占的字节数必须是4的倍数(即以字为单位),不足的以0填充3.2.3图片处理类 class CDibRGBQUAD * m_pRGB; 颜色信息首地址BYTE* m_pData;数据信息首地址UINT m_numberOfColors;颜色位数BITMAPFILEHEADER bitmapFileHeader;位图文件头BITMAPINFOHEADER* m_pBitmapInfoHeader;位图信息头地址BITMAPINFO* m_pBitmapInfo；位图信息地址BYTE* pDib;图片首地址DWORD size;图片大小CDib()；构造函数CDib();析构函数char m_fileName256;存储文件名bool isValid();打开正确判断函数char* getFileName();获得文件名DWORD getSize();获得图像大小UINT getWidth();获得图像宽度UINT getHeight();获得图像高度UINT getNumberOfColors();获得颜色数RGBQUAD * getRGB();获得颜色信息首地址BYTE* getData();获得数据信息首地址 WORD DIBNumberColors(LPBYTE lpDIB);获得位图颜色void saveFile(const CString filename);保存图像void loadFile(const char* dibFilename);载入图像3.2.4重构图片方法思想3.2.4.1读入文本文档数据将保存有类数cluster，维数dim和各个中心点数值的文本文档读入获得处理图像所需的数据。3.2.4.2读入图像用CDIB类的loadFile（）方法读入图像并获得数据首地址，图像高度，图像宽度等信息依次用p，h，w存储3.2.4.3处理图像将整个图像数据看成一个方阵，要处理的维数大小为一个小方块，每次处理一个方块，大方阵为小方块的整数倍。方阵为highwidth大小，小方块的大小为h_dimw_dim大小。用bmptemp数组存储整个图像的数据用dimtemp数组存储小方块的数据。因为数据是从左到右自下向上存储的所以要从最后一层开始读入数据。按照左到右自下向上的顺序将图片数据读入bmptemp数组。将每个小方块看成一个点将真个图像从左至右从上至下依次处理每次将一小方块的数据读入dimtemp数组处理，每次获得的dimtemp数组用change()函数处理，change()函数的作用是计算每个方块和读入的哪一类的中心点的距离最近，就将距离最近的类的值赋给dimtemp数组。距离的计算方法为按照顺序计算小方块中数值和一个类中心点的平方和。dimtemp数组获得新值后再传递给bmptemp数组中相应的位置，这样依次处理下来后bmptemp数组就是得到的新图像的像素值。最后将bmptemp数组的值再按照左到右自下向上的顺序赋给图像的数据值。3.2.4.4保存图像 调用CDIB类的saveFile（）方法将得到的新图像保存为新bmp文件3.2.5处理图像实例原始图像 聚类结果K=2时图像分割结果 K=3时 图像分割结果图3 Perpers.bmp图像处理3.2.6程序输入输出接口与实例图 4 CLOF算法系统Access数据库界面图 5 CLOF算法系统bmp图像界面第四章CLOF算法系统测试结果CLOF算法实现的软件环境：Windows2000操作系统，Microsoft Visual C+6.0，Microsoft ACCESS数据库；算法实现的硬件环境：处理器为Intel Pentium 4,内存512M，硬盘为60G。对算法的参数设置如下：全局因子G取50, 70,90 ，阈值=1，预处理抽样率为10%；全局聚类算法采用K-Mean算法10，初始化方法采用Greedy算法10，由有效性指标9来确定最佳聚类数。试验在经典大型数据库测试、图像分割和图像压缩三方面进行，并分为两大类：一类为比较性实验，一类为应用性实验。比较性实验一：数据集为公共图像文件Mandrill (512*512像素，见图4)，分割成1*2图块，生成2维向量近13万条作为原始数据，并生成XY散点分布图(图4)。实验结果如下:K2345678改进前Vwsj0.15660.04190.04110.02740.02060.98900.9189CLOF算法Vwsj0.16150.03760.02220.01770.03560.66820.7619表1 比较性实验一有效性指标对照表从上表中可以看出改进前最佳聚类为6，CLOF算法最佳聚类为5；图6 CLAP算法改进前后分布图左边图中为改进前CF树最终包含数据的XY散点分布图，右边为CLOF算法的XY散点分布图,其分布明显比左边密集。显然从图和表直观表明CLOF算法对孤立点具有较强的处理能力。比较性实验二：数据为家庭网络使用情况调查数据库Internet，由厦门大学数据挖掘实验室提供，共有33832条记录，每条记录有29个属性。实验结果如下(表2),改进前、后的最佳聚类数都为4，但比较其有效性指标，前者优于后者，改进前Vwsj=0.2739， 改进后CLOF算法Vwsj=0.1506。K2345678改进前Vwsj0.53570.33510.27390.90900.83550.98391.0533CLOF算法Vwsj0.49510.37560.15060.44930.48080.48891.1195表2 比较性实验二有效性指标对照表应用性实验之一：数据集为公共的图像文件Perpers （512*512像素），对图像像素进行分类，结果如下原始图像 聚类结果K=2时图像分割结果 K=3时 图像分割结果图7 Perpers.bmp图像处理其中最佳聚类数为K=3，图像像素分为蔬果的亮面，暗面和背景（含深色的蔬果）,当指定K=2时，图像像素分为蔬果亮面和暗面。数据集为公共的图像文件mandrill.bmp (512*512像素),并分割成4*4图像块，生成16维向量组生成原始聚类数据，进行图像压缩实验，分别指定最多颜色数为64、128，相应聚类数为K=4、K=8。原始图像 K= 4时压缩图像 K=8 压缩图像图8 Mandrill.bmp图像处理第五章 结论本次毕业设计实现了基于BIRCH算法和CLAP算法上改进的CLOF算法系统。整个系统包含了输入/输出、数据预处理、CLOF算法核心和图像还原预处理等四个模块。数据挖掘作为一个只有十几年研究历史的较新研究领域，一直吸引了无数数据挖掘人员的注意力，尤其在大型数据库的数据挖掘方面显得更具有挑战性。CLOF算法系统实现并测试了针对孤立点的处理方法上基于孤立因子的聚类算法CLOF。测试表明，该算法在对孤立点的处理上具有更强的稳健性和具有更高的聚类质量，只是尽管算法中采取了局部因子和全局因子相结合动态修正孤立因子，但初始抽样和初始聚类的随机性仍对最终聚类结果有一定的影响，因此如何定义孤立因子，提高孤立因子预测的准确性尚需进一步研究。本次毕业设计是我本科期间的最后一项重要任务，我又一次亲手参与了一个软件项目的开发。对以培养软件工程实践人才为目标的软件学院来说，实践是相当重要的一个环节，因而本次毕业设计意义重大。软件工程作为一个实践性很强的工科专业，动手能力是必不可少的。在这次毕业设计中，我全新认识了软件项目开发小组的模式。在这一个多月的编程工作中，我既尝到了毫无思路的苦闷，也体验到灵感一闪的兴奋。一个多月的团队生活也使我领会了团队合作精神，没有整个团队的紧密配合是无法完成一个较大项目的，相反有了流畅的组合许多看似无法解决的问题也会迎刃而解。通过具体的实践，我也学到