Clustering聚类分析

clustering聚类分析 聚类 分类相似的归为一类不相似的归入不同类未知类仅依靠对象的相似度 应用 生物学经济学 应用 文档分类文档 向量1 分量表示第i个词条的频率2 分量为0或1 表示是否引用第i篇文档 应用 社交网络 对象间的比较 相似度例 距离 不相似度 例 欧几里得距离 距离函数的选择 根据数据的情况选择例 将图中的点按连边情况分类点表示成邻接矩阵的行a 0 1 0 1 0 1 b 0 1 1 0 1 0 研究顾客的行为 d种商品n个顾客k种顾客类型 k n每种类型的顾客购买物品的情况满足一种概率分布 研究顾客的行为 顾客1 2种蔬菜 3种水果 1种海鲜 0种零食 顾客2 1种蔬菜 3种水果 1种海鲜 1种零食顾客3 4种蔬菜 0种水果 3种海鲜 2种零食顾客4 0种蔬菜 0种水果 0种海鲜 4种零食顾客5 3种蔬菜 1种水果 5种海鲜 1种零食可能的结果 1 2 3 5 4 顾客1 2 3 1 0 蔬菜水果海鲜零食 判断标准 每个类中 所有对象间的距离之和每个类中 所有对象到 中心 的距离之和k mediancriterion每个类中 所有对象到 中心 的距离平方之和k meanscriterion通过最小化这些值得到最优的划分 判断标准的选择 根据分类的目标 依靠经验例 距离的平方和1 异常点的误差被放大 得到更多关注2 数学计算上的优势 最优化判断标准 通常是np hard多项式算法并非精确的最优解 而是相对优的解或者局部的最优解 算法一 判断标准 k centercriterion最小化任意点到所分的类中心的最大距离基本思想 存在k个半径为r的球体覆盖所有点 存在最大距离为r的划分 算法一 步骤每次选取一个未被覆盖的数据点作为一个类的中心 作半径为r的球体 覆盖某些点 重复k次得到k个类 算法一 不靠谱 有点 但是 若存在最大距离为r 2的划分 这个算法一定能找到最大距离不超过r的划分 证明 反证法假设无法找到最大距离为r的划分 至少一个点不在k个半径为r的球体中 存在k 1个点两两的距离大于r k个半径为r 2的球体无法覆盖这k 1个点 不存在最大距离为r 2的划分 矛盾 类中心 要求类中心必须是数据点类的划分有限 可穷举类中心可以是空间中的任意点 使距离函数最小的点 结果精确某些判断标准下 类中心具有特殊性质 算法二 判断标准 k meanscriterion将d维的点集划分到k个聚类中 最小化所有点到所分的类中心 c 的距离平方之和 minimize 算法二 最好的中心是类中所有点的重心证明 设x为一个类的中心 类中有m个点 则距离的平方和可以表示为 定值 0 x c时最小 算法二 初始情况 选取k个点作为k个类的中心操作一 将每个数据点归入最近的中心所在类操作二 对每个类 将类的中心更新为类中所有数据点的重心终止条件 重复两个操作直到距离的平方和逼近局部最优 算法二 例子 n 9 k 3 算法二 例子 n 9 k 3 算法二 例子 n 9 k 3 算法二 终止条件算法一定会向局部最优解收敛 因为重复的两个操作都在不断优化距离平方和操作一 操作二 设置误差标准以逼近局部最优解 算法二 初始情况初始时对于k个点的选法不同 也会使收敛的结果不同 因此无法得到全局最优解 但近似的最优解也能成为理想的划分 参考材料