文档介绍：浅谈聚类算法
第1页，共16页，编辑于2022年，星期四
数据挖掘：指从大型数据库或数据仓库中提取隐含的、先前未知的、对决策有潜在价值的知识和规则。它是人工智能和数据库发展相结合的产物，是国际上数据库和信息决策系统最且高度偏斜的数据集。
基于约束的聚类：聚类结果既要满足特定的约束。又要具有良好聚类特性。
可解释性和可用性：聚类结果应该是可解释的、可理解的和可用的。
第5页，共16页，编辑于2022年，星期四
没有任何一种聚类技术(聚类算法),,这里将聚类算法大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法.
第6页，共16页，编辑于2022年，星期四
划分式聚类算法
划分聚类算法把数据点集分为k个划分，每个划分作为一个聚类。它一般从一个初始划分开始，然后通过重复的控制策略，使某个准则函数最优化，而每个聚类由其质心来代表(K-MEANS算法)，或者由该聚类中最靠近中心的一个对象来代表(K-MEDOIDS算法)。划分聚类算法收敛速度快，缺点在于它倾向于识别凸形分布大小相近、密度相近的聚类，不能发现分布形状比较复杂的聚类，它要求类别数目k可以合理地估计，并且初始中心的选择和噪声会对聚类结果产生很大影响。
划分式聚类算法需要预先指定聚类数目或聚类中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。
第7页，共16页，编辑于2022年，星期四
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.
第8页，共16页，编辑于2022年，星期四
K-means 算法的优点与不足。优点：能对大型数据集进行高效分类，其计算复杂性为 O(tkmn)，其中，t 为迭代次数，K 为聚类数，m 为特征属性数，n 为待分类的对象数，通常K、m、t<<n。在对大型数据集聚类时，K-means 算法比层次聚类算法快得多。不足：通常会在获得一个局部最优值时终止；仅适合对数值型数据聚类。
第9页，共16页，编辑于2022年，星期四
层次化聚类算法
分层聚类算法把数据对象分组而形成一个聚类树。分层聚类算法分为两大类：聚结型和分裂型。聚结型算法采用自底向上的策略，首先把每个对象单独作为一个聚类，然后根据一定的规则合并成为越来越大的聚类，直到最后所有的对象都归入到一个聚类中。大多数分层聚类算法都属于聚结型算法，它们之间的区别在于类间相似度的定义不同。与聚结型算法相反，分裂型算法采用自顶向下的方法。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。纯粹的分层聚类算法的缺点在于一旦进行合并或分裂之后，就无法再进行调整。现在的一些研究侧重于分层聚类算法与循环的重新分配方法的结合。适合于小型数据集的分类。
第10页，共16页，编辑于2022年，星期四
层次聚结算法
该算法由树状结构的底部开始逐层向上进行聚合,假定样本集 S={o1,o2,…,on}共有 n 个样本.
1[初始化]. 置每个样本 oi 为一个类;
/*共形成 n 个类:o1,o2,…,on*/
2[找最近的两个类],distance(or,ok)=min[distance(ou,ov)],其中ou,ov属于S，但不相等.
/*从现有的所有类中找出距离最近(相似度最大)的两个类 or 和 ok*/ 3[合并 or 和 ok]. 将类 or 和 ok 合并成一个新类 ork;
/*现有的类数将减 1*/ 4若所有的样本都属于同一个类,则终止本算法;否则,返回步骤 HA2.
第11页，共16页，编辑于2022年，星期四
基于网格和密度的聚类算法
基于网格和密度的聚类方法是一类重要的聚类方法,它们在以空间信息处理为代表的众多领域有着广泛应用.