人工智能论文

人工智能论文

课程名称：《人工智能》

论文题目：对聚类算法的研究学习班级：12计算机4班

学号：********

*名：***

提交日期：2015/6/15

当今社会经济和科技都处于迅猛发展中，使得各行各业有大量的数据需要进行合理高效的处理，聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大，它对未知数据的划分和分析起着非常重要的作用：通过聚类，能够找出这些数据的分布特点以及他们之间的关系。

但是对于聚类算法是有一些要求的，主要有可伸缩性，处理不同类型属性的能力，发现任意形状的聚类，用于决定输入参数的领域知识最小化，处理“噪声”数据的能力，处理“噪声”数据的能力，高维度，基于约束的聚类，可解释性和可用性。基于以上要求人们从不同角度提出了许多效率高、通用性强的聚类方法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。

1.划分法

给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K

K-MEDOIDS算法、CLARANS算法。

划分法的优点是收敛速度快，在对中小规模的数据库中发现球状簇很适用。缺点是它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k可以合理地估计，且初始中心的选择和噪声会对聚类结果产生很大影响，还要求用户预先指定聚类个数。

2. 层次法

这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。代表算法有：BIRCH算法、CURE 算法、CHAMELEON算法等；

自顶向下的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用这种方法，因为在较高的层很难进行正确的拆分。

3.基于密度的方法

这种方法说的是，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE 算法等；

基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

4.基于网格的方法

这种方法首先将数据空间划分成为有限个单元（cell）所有的处理都是以单个的单元为对象的。代表算法有：STING算法、WA VE-CLUSTER算法；

网格聚类法处理速度快，处理时间与数据对象的数目无关，一般由网格单元的数目决定。缺点是只能发现边界是水平或垂直的聚类，不能检测到斜边界。该类算法也不适用于高维情况，因为网格单元的数目随着维数的增加而呈指数增长。另外还有下列问题：一是如何选择合适的单元大小和数目，二是怎样对每个单元中对象的进行汇总，三是存在量化尺度的问题。

5.基于模型的方法

基于模型的方法给每一个聚类假定一个模型，然后去寻找能个很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神经网络的方案。

COBWEB优点为：可以自动修正划分中类的数目；不需要用户提供输入参数。缺点为：基于这样一个假设：在每个属性上的概率分布是彼此独立的。但这个假设并不总是成立。且对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化，不适用于聚类大型数据库的数据。

这些聚类算法都有各自的优缺点，但每种方法都只能适合于解决某一类问题这是由实际问题的复杂性和数据的多样性决定的。因此，用户应该结合实际根据自己的需要选择最恰当的算法。近年来，随着数据挖掘、机器学习和人工智能等领域中传统方法的不断发展以及各种新方法和新技术的涌现，聚类算法得到了长足的发展。不难发现其新趋势：传统聚类方法的融合发展。聚类算法综合了数据挖掘、模式识别、数学等众多领域的研究成果。目前这些领域中相关理论迅速发展、完善、相互渗透，相信会使得聚类分析将得到更快更好的发展。

聚类算法的应用

聚类主要应用于模式识别中的语音识别、字符识别等,机器学习中的聚类算法应用于图像分割和机器视觉,图像处理中聚类用于数据压缩和信息检索.聚类的另一个主要应用是数据挖掘(多关系数据挖掘)、时空数据库应用(GIS等)、序列和异类数据分析等，聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都有重要作用。

典型的聚类过程主要包括数据(或称之为样本或模式)准备、特征选择和特征提取、接近度计算、聚类(或分组)、对聚类结果进行有效性评估等步骤。

聚类过程:

1) 数据准备:包括特征标准化和降维.

2) 特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中.

3) 特征提取:通过对所选择的特征进行转换形成新的突出特征.

4) 聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量; 而后执行聚类或分组。

5) 聚类结果评估:是指对聚类结果进行评估.评估主要有 3 种:外部有效性评估、内部有效性评估和相关性测试评估。