title: 模式识别 第八章 数据聚类 非监督学习方法
date: 2017-03-26 18:47:53
categories: ML/卢晓春 模式识别引论
mathjax: true
tags: [Machine Learning]
第八章 数据聚类 非监督学习方法
相似性测度
欧式
马氏
明氏
相似性函数
数据标准化
不是所有情况下标准化处理都是合理的。在使用标准化技术时，要注意应用的环境是否恰当。可能导致数据标准化后交叉了不易划分。
聚类的准则函数：计算完相似性后，根据准则函数来划分
- 误差平方和准则：一个好的聚类方法应能使集合中的所有向量与这个均值向量的误差的长度平方和最小。
- 散布准则：不但反映同类样本的聚集程度，而且反映不同类之间的分离程度。
- 子类散布矩阵
- 类内散布矩阵
- 类间散布矩阵
- 总散布矩阵
- 迹准则
- 行列式准则
- 基于模式与类核间距离的准则函数
上面两种方法都是用均值向量来表示一类的位置并代替该类，损失了各类在空间中的分布情况。
为了细致的表征一类，可以定义一个核来表示其模式分布结构。核可以是一个函数，一个属于同一类的模式集合或其它模型；还需要定义一个距离（即测度）以及由此构成的准则函数。
分类聚类算法 即 层次聚类算法
见 网络数据挖掘笔记
- 聚合法：
- 聚合算法步骤如下，其中c是事先指定的聚类数，当c达到后，迭代停止；如果c=1，则得到整个分类树。
- 设c*=n，Di={xi}，i=1,2,…,n
- 若c*<=c，则停止
- 找最近的两个类Di和Dj【近点距离、远点距离、平均距离】
- 将Di和Dj合并，删去Di， c*减1
- 转向步骤2
- 分解法：从整体开始分
动态聚类法
动态聚类方法是一种普遍采用的聚类方法，主要具有以下3个要点
选定某种距离度量作为样本间的相似性度量
确定某个评价聚类结果质量的准则函数
给定某个初始分类，然后用迭代算法找出使准则函数取极值的最好聚类结果
-
初始聚类中心的选择方法
- 任取前c个样本点作为初始聚类中心
- 凭经验选择
- 将全部数据随机分为c类，计算各类重心，将重心作为聚类中心
- 密度法选择代表点（具有统计特性）
- 从c-1类划分中产生c类划分问题的初始聚类中心
-
初始聚类中心确定后，有不同的分类方法来确定初始划分，包括如何修正聚类中心
- 对选定的中心按距离最近原则将样本划归到各聚类中心代表的类别，然后调整聚类中心（批量修正法）
- 取一样本，将其归入与其距离最近的那一类，并计算该类的样本均值，以此样本均值代替原来的聚类中心作为新的聚类中心，然后再取下一个样本，如此操作，直到所有样本都归属到相应的类别中为止（单步样本修正法）
一般来说，不同的初始划分往往会得到不同的解。
-
K均值算法
- 给定允许误差ℇ，令t=1
- 初始化聚类中心wi(t)，i=1,2,…,c
- 修正dij，
- 修正聚类中心wi(t+1)
- 计算误差E或者Je
- 如果E< ℇ ，则算法结束；否则t=t+1，转步骤3
- 上述K均值算法每次把全部样本都调整完毕后才重新计算一次各类的聚类中心，属于批处理算法；也可以采用逐个样本修正法，每调整一个样本的类别就重新计算一次各类的聚类中心。
- 这个算法是在类别数c给定的情况下进行的。当类别数未知时，可以假设类别是在不断增加的，准则函数是随c的增加而单调减小的。可以通过Je-c的关系曲线来确定合适的聚类类别数。
-
ISODATA算法
- 合并发生在某一类样本个数太少，或者两类聚类中心之间距离太小的情况
- 分裂发生在某一类别的某分量出现类内方差过大的现象
- 设置若干控制参数
- K均值算法的迭代次数
- 控制合并与分裂的参数
- 最多合并次数
- 聚类中最少样本数
- 控制分裂参数
- 最小类间距离
- 合并与分裂次数
- 算法步骤
- 选择参数
- 确定初始聚类中心
- 用K均值算法进行迭代。
- 合并/分裂
- 计算各类的新的聚类中心
- 判断是否满足结束条件，否则转3
