Clustering聚类分析

1、clustering 聚类分析聚类分析 聚类聚类 分类分类 相似的归为一类相似的归为一类 不相似的归入不同类不相似的归入不同类 未知类未知类 仅依靠对象的相似度仅依靠对象的相似度 应用应用 生物学生物学 经济学经济学 应用应用 文档分类文档分类 文档文档向量向量 1、分量、分量 表示第表示第i个词条的频率个词条的频率 2、分量、分量 为为0或或1，表示是否引用第，表示是否引用第i篇文档篇文档 ,., 21n aaaa i a i a 应用应用 社交网络社交网络 对象间的比较对象间的比较 相似度相似度 例：例： 距离（不相似度）距离（不相似度） 例：例： 欧几里得距离欧几里得距离 ),cos(b

2、a ),cos(1ba 距离函数的选择距离函数的选择 根据数据的情况选择根据数据的情况选择 例：将图中的点按连边情况分类例：将图中的点按连边情况分类 点表示成邻接矩阵的行点表示成邻接矩阵的行 a=(0,1,0,1,0,1) b=(0,1,1,0,1,0) 1 4| 2 ba ba 研究顾客的行为研究顾客的行为 d种商品种商品 n个顾客个顾客 k种顾客类型，种顾客类型，kn 每种类型的顾客购买物品的情况满每种类型的顾客购买物品的情况满 足一种概率分布足一种概率分布 研究顾客的行为研究顾客的行为 顾客顾客1：2种蔬菜，种蔬菜，3种水果，种水果，1种海鲜，种海鲜，0种零食，种零食， 顾客顾客2：1种

3、蔬菜，种蔬菜，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

4、-median criterion 每个类中，所有对象到每个类中，所有对象到“中心中心”的距离平方之的距离平方之 和和 k-means criterion 通过最小化这些值得到最优的划分通过最小化这些值得到最优的划分 判断标准的选择判断标准的选择 根据分类的目标，依靠经验根据分类的目标，依靠经验 例：距离的平方和例：距离的平方和 1、异常点的误差被放大，得到更多关注、异常点的误差被放大，得到更多关注 2、数学计算上的优势、数学计算上的优势 最优化判断标准最优化判断标准 通常是通常是np-hard 多项式算法多项式算法 并非精确的最优解，而是相对优的解或者局并非精确的最优解，而是相对优的解或者局

5、 部的最优解部的最优解 算法一算法一 判断标准：判断标准：k-center criterion 最小化任意点到所分的类中心的最大距离最小化任意点到所分的类中心的最大距离 基本思想：基本思想： 存在存在k个半径为个半径为r的球体覆盖所有点的球体覆盖所有点 存在最大距离为存在最大距离为r的划分的划分 算法一算法一 步骤步骤 每次选取一个未被覆盖的每次选取一个未被覆盖的数据数据点作为一个类点作为一个类 的中心，作半径为的中心，作半径为r的球体，覆盖某些点。重复的球体，覆盖某些点。重复k 次得到次得到k个类。个类。 算法一算法一 不靠谱？有点不靠谱？有点 但是：但是： 若存在最大距离为若存在最大距离为

6、r/2的划分，这个算法一定的划分，这个算法一定 能找到最大距离不超过能找到最大距离不超过r的划分。的划分。 证明：反证法证明：反证法 假设无法找到最大距离为假设无法找到最大距离为r的划分的划分 至少一个点不在至少一个点不在k个半径为个半径为r的球体中的球体中 存在存在k+1个点两两的距离大于个点两两的距离大于r k个半径为个半径为r/2的球体无法覆盖这的球体无法覆盖这k+1个点个点 不存在最大距离为不存在最大距离为r/2的划分（矛盾）的划分（矛盾） 类中心类中心 要求类中心必须是数据点要求类中心必须是数据点 类的划分有限，可穷举类的划分有限，可穷举 类中心可以是空间中的任意点（使距离函类中心可

7、以是空间中的任意点（使距离函 数最小的点）数最小的点） 结果精确结果精确 某些判断标准下，类中心具有特殊性质某些判断标准下，类中心具有特殊性质 算法二算法二 判断标准：判断标准：k-means criterion 将将d维的点集维的点集 划分到划分到k个聚类个聚类 中，最小化所有点到所分的类中心（中，最小化所有点到所分的类中心（c）的）的 距离平方之和。距离平方之和。 minimize ,., 21n aaaa k jsa ij ji ac 1 2 )( k sss,., 21 算法二算法二 最好的中心是类中所有点的重心最好的中心是类中所有点的重心 证明：证明： 设设x为一个类的中心，类中有为

8、一个类的中心，类中有 m个点。个点。 则距离的平方和可以表示为则距离的平方和可以表示为 m aaa,., 21 i i xa 2 i i xcca 2 22 )()(2xcmcaxcca i i i i 定值定值0 x=c时最小时最小 算法二算法二 初始情况：选取初始情况：选取k个点作为个点作为k个类的中心个类的中心 操作一：将每个数据点归入最近的中心所在类操作一：将每个数据点归入最近的中心所在类 操作二：对每个类，将类的中心更新为类中所操作二：对每个类，将类的中心更新为类中所 有数据点的重心有数据点的重心 终止条件：重复两个操作直到距离的平方和逼终止条件：重复两个操作直到距离的平方和逼 近局部最优近局部最优 算法二算法二 例子： n=9,k=3 算法二算法二 例子： n=9,k=3 算法二算法二 例子： n=9,k=3 算法二算法二 终止条件终止条件 算法一定会向局部最优解收敛，因为重复的两个算法一定会向局部最优解收敛，因为重复的两个 操作都在不断优化距离平方和操作都在不断优化距离平方和 操作一操作一 操作二操作二 设置误差标准以逼近局部最优解设置误差标准以逼近局部最优解 算法二算法二 初始情况初始情况 初始时对于初始时对于k个点的选法不同，也会使收敛的结果个点的选法不同，也会使收敛的结果 不同，因此无法得到全局最优解。不同，因此无