第7章-非监督分类.pptxVIP

非监督分类; 相似性度量 均值聚类 向量量化 最大流/最小割 其它分类方法;分类 基本的精神活动——发现样本之间的联系，相似性，差异性;非监督聚类： 根据相似性，对样本空间进行划分。 硬聚类 模糊聚类 谱系聚类;分类 分类的多样性。;距离测度 定义在特征空间×特征空间到实数的函数：;常用距离测度： 范数距离：任意范数可以定义距离。 其他距离测度：;常用距离测度： Hamming距离：。 ;编辑距离（Levenshtein/EDIT 距离）： 将序列A变为序列B的所有可能方法中，代价最小的一个。;寻找最短编辑距离 遍历法;寻找最短编辑距离 图的最短路径问题 动态规划法： 阶段：步数 状态：已处理节点集一步可达的新节点。 代价：1;栅格图： 横轴为目标字符串，纵轴为起始字符串。 节点标注了所有可能状态 状态为：节点横轴取值（包含）合并纵轴取值（不包含）（注意前后顺序） 水平、垂直边权重为1； 某节点水平与垂直对应符号相同其左下对角边权重为0，否则为1； 对角边权重为0的两个状态相同；;;编辑距离的性质： 三角不等性： ED(x,y) ≤ ED(x,z) + ED(z,y)。 分裂不等性： ED(x,y) ≤ ED(x[1..i],y[1..j])+ED(x[i+1..n],y[j+1..m]) ED(x,y) ≤ m（目标与源字符串长度大的一个） ED(x,y) ≥ m-n ED(x,y)=0 iff x=y 如果两字符串等长， ED(x,y) ≤ HD(x,y)（海明距离）;Damerau–Levenshtein距离 除了替换、插入、删除外，允许交换相邻两个字符的位置。 /wiki/Damerau%E2%80%93Levenshtein_distance;相似性测度 ;常用相似测度： 内积： Tanimoto测度：;点到集合的距离： 最大距离： 最小距离： 平均距离：;点到平面的距离（支持向量机） 点到二次曲面的距离： 二次曲面： 代数距离：;垂直距离： 求解z得到： ;径向距离（椭圆集特有）： ;归一化径向距离（椭圆集特有）： 通过线性变换，将椭圆变成正圆， 计算正圆距离为： 归一化径向距离： 归一化距离与径向距离关系。 ;集合到集合的距离： 最大距离： 最小距离： 平均距离： 重心距离：; 相似性度量 均值聚类 向量量化 最大流/最小割 其它分类方法;回顾KNN分类器： 已知类中心聚类（监??分类），x属于到各类重心最近的类。;问题： 非监督聚类还需要得到类中心。 K/c均值聚类： 目标： 取定c类，选取c个初始聚类中心，即代表点。按最小距离原则将各样本分配到离代表点最近的一类中，不断重新计算类中心，调整各样本类别，最终使聚类准则函数Je最小。;C/K均值聚类： C（K）均值：对类中心进行动态调整。 1. 选择任意数据作为初始类中心， 2. 最小距离分类 3. 更新类中心为各类中心 4. 迭代，直到类中心不发生变化。;C/K均值聚类： 特点：N个样本聚类成c类时，所产生的总距离最小。 收敛性：k均值不能保证收敛到全局最优解。 优点：算法简单，实际中表现出色，是一种主要聚类方法。 过程：初始参数-分类-更新参数-分类，过程与EM算法类似，属于一类迭代算法。;特征空间变换： 如果数据分布不具有各项同性，分类前需要对数据进行变换。 等价于变换距离测度： 马氏距离：;逐个样本进入聚类器，每个类竞争该样本，得到该样本的类更新参数。 参数更新公式： 竞争胜出者： 竞争失败者： 竞争学习是一种更新策略，相对于K均值分类的“批量模式”，竞争学习为“在线模式”，可用于各种具体方法。 ;K均值聚类的竞争学习： 参数c为类中心，如果希望在竞争到新样本后类中心为包含该样本的类中心，则迭代公式为： 竞争胜出者： 竞争失败者： ;一般地，η应满足： ;竞争学习; 相似性度量 均值聚类 向量量化 最大流/最小割 其它分类方法;向量量化;向量量化;向量量化; 相似性度量 均值聚类 向量量化 最大流/最小割 其它分类方法