文档介绍：聚类方法第十一章
现在学习的是第1页，共38页
划分聚类
一、按最邻近规则的简单试探法
给N个待分类的模式样本 ，要求按距离阈值T分类到聚类中心
算法过程：
S-1
-1
-3
3
2
2
0
2
1
-1
-2
-1
-3
-5
现在学习的是第15页，共38页
∴目标函数
∴
解：第一次分类时计算所有样本，分别划到 时的E值，找出最大E值对应的样本。
1、开始时，
现在学习的是第16页，共38页
2、分别计算当 划入
时的E值
把 划入
时有
现在学习的是第17页，共38页
然后再计算把 划入 时对应的E值，找出一个最大的E值。
一直计算下去…
把 划为 的E值最大。
∴
E(1)=
再继续进行第二，第三次迭代…
计算出 E(2) , E(3) , …
现在学习的是第18页，共38页
次数 E值
1
2
3
4
5
6
7
8
9
10
11
现在学习的是第19页，共38页
第10次迭代 划入 时，E最大。于是分成以下两类：
∴
每次分类后要重新计算 的值。可用以下递推公式：
现在学习的是第20页，共38页
现在学习的是第21页，共38页
动态聚类-K-means
一、动态聚类的方法概要
① 先选定某种距离作为样本间的相似性的度量;
② 确定评价聚类结果的准则函数;
③ 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。
现在学习的是第22页，共38页
选代表点
初始分类
分类合理否
最终分类
修改分类
Y
N
动态聚类框图
现在学习的是第23页，共38页
二、代表点（种子点）的选取方法：
代表点就是初始分类的k个聚类中心
① 凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的k个代表点;
② 将全部样本随机分成k类，计算每类重心，把这些重心作为每类的代表点;
③ 用前k个样本点作为代表点。
现在学习的是第24页，共38页
④ 按密度大小选代表点：
以每个样本作为球心，以d为半径做球形；落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太