文档介绍：浅谈聚类算法
第一页，共16页
数据挖掘：指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。它是人工智能和数据库发展相结合的产物，是国际上数据库和信息决策系统最前沿的研究方向之一。数据挖掘主要的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神经网络算法等等。
聚类是数据挖掘中的一个非常重要的研究课题，广泛应用于各个领域，它对未知数能达到合理的效果。研究和运用聚类是完成数据挖掘任务的重要手段，因此对聚类的研究具有重要的理论价值和现实意义。
第二页，共16页
俗话说：“人以群分，物以类聚”。聚类就是利用计算机技术来实现这一目的的一种技术。聚类是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。
聚类与分类不同：分类问题中我们知道数据集的分类属性。而聚类问题则需要我们从数据集中找这个分类属性。
迄今为止, 年关于聚类所下的定义:一个类簇内的实体是相似的,不同类簇的实体是不相似的;一个类簇是测试空间中点的会聚,同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离;类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域,它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离.。
聚类的标准是使簇内相似度尽可能大，簇间相似度尽可能小。
第三页，共16页
伸缩性：聚类算法对小数据集和大规模数据集要同样有效。
处理不同类型属性的能力：实际应用要求算法能够处理不同类型的数据。
能发现任意形状的聚类：聚类特征的未知性决定聚类算法要能发现球形的、嵌套的、中空的等任意复杂形状和结构的聚类。
使决定输入参数的领域知识最小化：聚类算法要尽可能地减少用户估计参数的最佳取值所需要的领域知识。
能够有效地处理噪声数据：聚类算法要能处理现实世界的数据库中普遍包含的孤立点，空缺或者错误的数据。
第四页，共16页
对于输入纪录的顺序不敏感：聚类算法对不同的次序的记录输入应具有相同的聚类结果。
高维性：聚类算法不仅要擅长处理低维的数据集，而且要能处理高维、数据可能非常稀疏且高度偏斜的数据集。
基于约束的聚类：聚类结果既要满足特定的约束。又要具有良好聚类特性。
可解释性和可用性：聚类结果应该是可解释的、可理解的和可用的。
第五页，共16页
没有任何一种聚类技术(聚类算法),,这里将聚类算法大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法.
第六页，共16页
划分式聚类算法
划分聚类算法把数据点集分为k个划分，每个划分作为一个聚类。它一般从一个初始划分开始，然后通过重复的控制策略，使某个准则函数最优化，而每个聚类由其质心来代表(K-MEANS算法)，或者由该聚类中最靠近中心的一个对象来代表(K-MEDOIDS算法)。划分聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k可以合理地估计，并且初始中心的选择和噪声会对聚类结果产生很大影响。
划分式聚类算法需要预先指定聚类数目或聚类中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。
第七页，共16页
K均值聚类
1967 年,MacQueen 首次提出了K均值聚类算法(K-means 算法).迄今为止,很多聚类任务都选择该经典算该算法的核心思想是找出K 个聚类中心C1,C2,…,Ck,使得每一个数据点xi 和与其最近的聚类中心Cv的平方距离和被最小化(该平方距离和被称为偏差D).
K 均值(K-means)聚类算法(对n 个样本进行聚类)
1[初始化]. 随机指定K 个聚类中心(C1,C2,…,Ck);
2[分配xi]. 对每一个样本xi,找到离它最近的聚类中心Cv,并将其分配到Cv所标明类;
3[修正Cw]. 将每一个Cw移动到其标明的类的中心;
4[计算偏差].
5[D 收敛?]. 如果D 值收敛,则return(C1,C2,…,Ck)并终止本算法;否则,返回步骤K2.
第八页，共16页
K-means 算法的优点与不足。优点：能对大型数据集进行高效分类，其计算复杂性为 O(tkmn)，其中，t 为迭代次数，K 为聚类数，m 为特征属性数，n 为待分类的对象数，通常K、m、t<<n。在对大型数据集聚类时，K-means