第7讲 常用聚类方法.ppt

第7讲 常用聚类方法 要点： c-均值算法 谱系聚类算法 其它聚类算法 课堂练习，课后练习 c-均值算法(k-均值算法) c-均值算法的基本思想 c-均值算法的计算过程及举例 c-均值算法的两种类型 c-均值算法的优缺点及其改进 返回 c-均值算法的基本思想 首先取定类别个数c和选取c个初始聚类中心 ，然后按最小距离原则将各样本Xi分配到c类中的某一类，接着通过不断地计算类心 和调整各样本的类别 ，最终使各样本到其所属类别中心的距离平方之和准则函数 大到极小： 返回 c-均值算法的计算过程 1.类别个数及初始聚类中心的选择 2.按照最小距离原则对样本归类 3.计算重新分类后的聚类中心 4.判断停止条件 返回 类别个数及初始聚类中心的选择 将待分类的样本记为{X1, X 2,…, XN}，选定类别个数为c。 令k=0，任选c个样本（或向量）作为初始聚类中心： 其中 是 类的中心。 返回 按照最小距离原则对样本归类 将待分类的样本Xi 逐个按最小距离原则归类: 如果 ，则判 。 其中 是 类 的中心。 返回 计算重新分类后的聚类中心 计算 类的聚类中心 如下： 其中 是 类的样本数。 返回 判断停止条件 如果 ，则停止； 否则，k=k+1，转至第2步。 返回 c-均值算法举例 已知样本集为： 如果聚成两类且 ，那么聚类结果是什么？求解过程。 如果 ，想一想聚类结果？ 返回 求解过程 对样本归类： 计算各类中心： 重新归类后计算中心得 ，聚类结果为： 返回 c-均值算法的两种类型 批修改法：将所有待分类样本按最小距离原则归类之后，再计算各类的中心。 逐个修改法：每向算法输入一个样本后就将它进行分类，并计算它所进入类的类心。 这两种算法的收敛性都得到了严格证明。 返回 c-均值算法的优缺点 c-均值算法的方法简单，结果尚令人满意，故应用较多。如果样本分布呈现类内团聚状，该算法是能达到很好聚类结果的。 c-均值算法的分类结果受到取定的类别数目及聚类中心的初始位置的影响，所以结果一般只是局部最优的。 c-均值算法在实际应用中需要试探不同的c值和选择不同的聚类中心初始值，以进一步达到更大范围的最优结果。 返回 c-均值算法的改进 c值的调整 初始聚类中心的选取 用类核代替类心 返回 c值的调整 J-c曲线法：可让类别数c从较小值逐步增加，并对每个选定的c值分别使用该算法，易知准则函数J随着c的增加而单调减少，因此在J-c曲线上曲率变化最大的点对应的类数是比较接近从样本几何分布上看最优的类数。 先验知识法：利用问题的先验知识分析选取合理的聚类数。 返回 J-c曲线示意图 返回 初始聚类中心的选取 经验法：凭经验选择初始类心。 随机法：将样本随机地分成c类，计算每类中心，以其作为初始类心。 密度法：求以每个样本为球心、某一正数d0为半径的球形域中的样本数，即密度。选取密度最大的样本作为第一个初始类心，然后在某个距离d的之外选取另一个具有最大密度的样本作为第二个初始类心，….. 最后共选取c个初始聚类中心。 最远距离法：用相距最远的c个样本作为初始聚类中心。 返回 用类核代替类心 c-均值算法的一个特点是只用一个中心代表一个类，而一个点往往不能充分地反映该类的样本分布结构，它对椭圆分布样本效果不佳。 如果已知各类样本分布的某些知识，则可以定义一个类核函数Kj =K(X,Vj)表示类?j的样本分布情况，其中Vj是关于类?j的一个参数集，X是n维样本，Kj可以是一个函数、一个点或其它适当的模型。为了度量样本X和?j类的接近程度，还应规定一个距离 。返回 椭圆分布样本示意图 返回 谱系聚类(Hierarchical Clustering)算法 谱系聚类算法的基本思想 谱系聚类算法的计算过程 谱系聚类算法的辅助说明 谱系聚类算法的基本特点 谱系聚类算法举例1和举例2 返回 谱系聚类算法的基本思想 首先视N个样本各自归为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别划分下各类之间的距离，再将距离最近的两个类合并，直至所有样