摘 要

CURE是一种针对大型数据库的高效的聚类算法。该算法选择了基于质心和代表对象方法之间的中间策略。它不用单个质心或对象代表一个簇，而是选择数据空间中固定了数目的具有代表性的点。要得到一个簇的代表点，首先选择簇中的分散对象，然后根据特定的收缩因子向簇中心“收缩”它们。在算法进行时，有最近距离代表点的两个簇被合并。

CURE采用了一种新型的层次聚类算法，本文主要实现了基于CURE算法的木材缺陷识别，并在此基础上对其性能进行了进一步的研究，取得了良好的效果。

关键词：聚类分析、CURE算法、木材缺陷识别

ABSTRACT

Cure algorithm is a large database of efficient clustering algorithm. This algorithm based on centroid and representatives choose between the object's methods among strategy. It does not have a single centroid or object represents a cluster, but the choice data space fixed number of representative points. To get a cluster of representatives point, first choose dispersing object, then clusters according to specific shrinkage factors to cluster center "shrink" them. In the algorithm, a recent distance representing point two clusters are incorporated.

Keywords: Clustering analysis, CURE,Wood defect recognition.

目 录

第一章 绪 论 1

1.1 聚类 1

1.1.1 聚类算法理论基础 1

1.1.2 聚类算法特点 2

1.1.3 研究现状 3

1.1.4 聚类算法应用 3

1.2 本课题的研究内容 4

1.2.1 选题的意义 4

1.2.2 研究的目的和研究内容 5

1.3 本论文结构安排 5

第二章 算法分析与设计 6

2.1 算法开发工具 6

2.2 算法编程语言 6

2.3 层次聚类 7

2.4 算法评价标准 8

第三章 CURE 算法 9

3.1 CURE 算法概述 9

3.1.1 CURE 算法特点 9

3.1.2 CURE 算法思想 10

3.1.3 CURE 算法聚类步骤 10

3.2 CURE 算法实现 11

第四章 基于CURE算法的木材缺陷识别 13

4.1图像数据预处理 13

4.1.1数据格式 13

4.1.2 图像数据集合 13

4.2 木材缺陷识别 14

4.2.1 木材缺陷识别现状 14

4.2.2木材缺陷识别 15

总 结 17

致 谢 18

参考文献 19

第一章 绪 论

1.1 聚类

聚类是数据挖掘、模式识别等领域最为常用的技术之一。通过一定的准则将已有数据对象分入不同的集合，我们把它们称为簇，簇内的对象彼此相似，簇间的对象尽可能相异。聚类分析也是一种分类技术。在许多应用中，我们可以将一个簇中的数据对象作为一个整体来对待。传统聚类过程通常没有先前的经验作为指导，属于无监督的分类过程，算法在对样本集进行聚类时并未考虑先前知识。

迄今为止，聚类还没有一个学术界公认的定义。本文在这里引用Everitt在1974年关于聚类的定义^[1]：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。事实上，聚类是一个无监督的分类，它没有任何先前知识可用。

聚类分析的理论在发展过程中得到不断的丰富，从最初的硬聚类算法的研究发展到模糊聚类算法和可能性聚类算法的研究，聚类分析的研究方向也在发展过程中得到不断的拓展。聚类算法也分很多种，如层次聚类算法、划分式聚类算法、基于网格和密度的聚类算法等^[2]。

1.1.1 聚类算法理论基础

聚类算法根据特征向量间的“相似”程度来完成对n维特征向量分组。根据已知数据，计算个体或变量之间亲疏关系的统计量，如距离或相关系数。依据某种衡量准则，如：最短距离法、最长距离法等方法，使同一类内的差别较小，而类与类之间的差别较大，最终将个体集或变量集分为若干类。

特征选择（feature selection）^[3]。必须选择合适的特征，并保存在向量中，该特征尽可能多的包含任务关心的信息，在特征选择中，如何减少信息冗余以及信息最小化是主要目标。在某些必要情况下，有必要事先进行特征的预处理。

近邻测度（proximity measure）。用于定量的测定两个特征向量之间的“相似”程度。有很多种近邻测度准则，合适的近邻测度准则的选取在聚类过程中非常必要。

聚类准则（clustering criterion）。聚类准则以蕴含在数据集中类的类型为基础，在选取上很大程度上依赖于专家判断。不同类型的类的准则判断有所不同，通常聚类准则可以用试探方式、代价函数或其它规则表示。

聚类算法（clustering algorithm）。该过程涉及到具体算法的选择，用于揭示数据集的聚类结构。

结果验证（validation of the results）。我们对数据进行聚类时，首先判断数据集是否有特定的分类结构，如果有，应用聚类算法进行聚类，并判断所得到的聚类结果是否有效，通常使用逼近检验验证其正确性。

结果判定（interpretation of the results）。通常，应用领域的专家必须用其他实验证据和分析判定聚类结果，最后得出正确的结论。

1.1.2 聚类算法特点

聚类分析是数据挖掘技术中重要的组成部分，它能够在潜在的数据中发现令人感兴趣的数据分布模式。聚类是一个富有挑战性的研究领域,它的潜在应用提出了各自特殊的要求。在数据挖掘领域中对聚类算法的典型要求主要有以下几个方面^[4]：

lt;1gt;可伸缩性。聚类算法对小数据集和大规模数据有同样的效果。

lt;2gt;处理不同数据类型属性的能力。实际应用要求算法能够处理不同类型的数据。