数据挖掘（6）聚类分析

一、什么是聚类分析

1.1概述

1. 无指导的，数据集中类别未知
2. 类的特征：
   • 类不是事先给定的，而是根据数据的相似性、距离划分的
   • 聚类的数目和结构都没有事先假定。
3. 挖掘有价值的客户:
   • 找到客户的黄金客户
   • ATM的安装位置

1.2区别·

二、距离和相似系数

2.1概述

1. 原则: 组内数据有较高相似度、不同组数据不相似
2. 相似性的度量(统计学角度):
   1. Q型聚类:对样本聚类(行聚类)
   2. R型聚类:对变量聚类(列聚类)
   3. 

2.2Q型聚类(样本聚类、行聚类)

1.样本资料矩阵: 

2.定义距离的准则:

3.变量的类型

1. 间隔尺度变量(数值型变量):可加可比
2. 有序尺度变量(叙述型变量):不可加可比
3. 名义尺度变量(名义型变量):不可加不可比

4.间隔尺度变量(数值型变量)

1. 缺点:数据集中存在变量取值范围相差十分悬殊，会造成大数吃小数现象。

2. 数值与指标量纲有关

度量值的标准化:

• 将初始测量值转换为无单位变量。
• 常用零均值规范化

特例:比例数值变量

 5.有序尺度变量

1. 只可以不可加:比如各种排名、等级
2. 步骤

6.名义尺度变量(符号变量)

1. 两种类型

   1. 二元变量:
      • 只有两个取值变量:如男女、开关、01
   2. 名义变量:
      • 二元变量推广:如颜色变量(R,G,B)

2. 二元变量计算:

   1. 差异矩阵法:

   2. 恒定的相似度

      1. 对称的二元变量：取值01内容同等价值、相同权值
         • 如:男女
      2. 简单匹配系数
         • 
         • 取值不一样(01或10)的个数在所有变量的比重

   3. 非恒定的相似度

      1. 非对称二元变量:取值01内容重要程度不同
         • 如:病毒阴阳性
      2. Jaccard相关系数
         • 
         • 取值不一样(01或10)的个数在所有变量(除去取值为00)的比重
   4. 相似度系数例子(小题计算):
   5. 名义变量计算(最常用):

7.混合数据类型

1. 现实数据库中包含多类型的数据
2. 如何计算？
   1. 将变量按类型分组，对每种类型的变量单独聚类分析，但实际中，往往不可行。
   2. 将所有的变量一起处理，只进行一次聚类分析。
3. 相似度计算

 2.3R型聚类(变量聚类、列聚类)

1. 相似系数:

   • 夹角余弦
   • 相关系数

2. 夹角余弦

   • 值越大越好
   • 

3. 变量间相似系数

4. 相似系数

5. 相似矩阵

三、 类的定义和类间距离

3.1类的定义

1. 定义1:任意元素，间距离满足:
   1. 适合:团簇状
   2. 
2. 定义2:任意元素,间距离满足(类内平均距离)
   1. 适合:团簇状
3. 定义3:对于任意元素,存在使得其满足(不要求任意两个元素)
   1. 适合:长条状
   2. 

3.2类间距离

1. 最近距离

   1. 与最近距离为

   2. 是和，合并得到的

   3. 实际中不多见，避免极大值影响

   4. 例子

      1. 计算类间距离，然后将最小的两个进行合并

      2. " role="presentation" style="position: relative;">$$

2. 最远距离 
   1. 与最远距离为
   2. 是和，合并得到的

   3. 可能被极大值扭曲，删除后再聚类

   4. 例题:与上面的类似，每次选取距离最小的，合并的时候取的是max

3. 平均距离

   1. 

4. 中间距离 
   1. 
5. 重心距离

   1. 一个类空间的位置用重心表示，两个类重心之间距离为二者的距离

   2. 对异常值不敏感，结果能稳定

四、基于划分的聚类方法

4.1划分方法

1. 将n个对象划分成k类，且满足:
   • 每个聚类内至少包含一个对象
   • 每个对象必须属于一个类(模糊划分计划可以放宽要求)
2. 划分方法:
   1. k-均值:每个聚类用该聚类中对象的平均值表示
   2. k-中心点:每个聚类用接近聚类重心的一个对象(真实存在的点)表示

4.2k-均值聚类算法

1. 用类均值表示

2. 不适合处理离散型属性，适合处理连续型属性

3. 算法流程:

   1. 选取聚类中心:随机从n个数据选择k个对象作为初始聚类中心
   2. 对剩余的每个对象，根据各个聚类中心的距离，将其赋给最近的聚类。
   3. 重新计算每个聚类的平均值(中心)
   4. 不断重复，直到准则函数收敛(减小)
4. 收敛准则函数:误差平方和最小

5. 缺点:

   1. 局部最优，不是全局最优

   2. 结果与k的取值有关

   3. 不适合发现大小很不相同的簇、凹状的簇
      *

   4. 只有在簇的平均值被定义的情况下才能使用，不适合有类属性的数据。

   5. 对噪声、异常点敏感。

6. 示意图例子：

7. 

4.3k-中心点聚类算法

1. k-中心点与k-均值算法区别

   簇中心	评价准则
   k-均值	簇中对象均值(可以是虚点)	误差平方和
   k-中心点	接近簇中心的一个对象表示(实际存在的点)	绝对误差

2. 基本策略
   1. 随意选择一个代表对象作为中心点，将剩余对象按最小距离划分进簇中。
   2. 重复利用非中心对象代替中心对象，若改善聚类的整体距离，则进行替代。
   3. 用代价函数进行估算质量:
3. 替代的四种情况

• 如何判断非代表对象是否能替代当前代表对象,需要对每个非中心点P考虑
• 替换的总代价:
• 若总代价为负，则可以替代

 4.算法步骤

1. 选取聚类中心:随机从n个数据对象选择k个
2. 循环3-5，知道聚类不发生变化
3. 对剩余的每个对象，根据各个聚类中心的距离，将其划分给最近的聚类。
4. 选择任意非中心对象计算与中心对象交换的成本S。
5. 若成本S为负，则交换中心对象。

五、基于层次的聚类方法

5.1 总述

1. 给定的数据对象集合进行层次分解，根据层次分解的方式，层次的方法被分为凝聚、分裂。
2. 凝聚层次法(agnes算法)
   • 自底向上
   • 一开始将每个对象作为单独的一组，然后合并相近的组，直到合为一组或到达终止条件
3. 分裂层次法(dinan算法)
   • 自底向下
   • 所有对象置于一个簇，在迭代的每一步，一个簇被分裂为更下的簇，直到每个对象单独为一个簇或到达某个终止条件
4. 计算距离方法

5.2agnes算法

1. 步骤:
   1. 每个对象当做一个初始簇
   2. repeant 3-4
   3. 根据两个簇中最近数据点找到最近的两个簇
   4. 合并两个簇，生成新的簇集合
   5. until 达到定义的簇的数目
2. 例子
3. 特点:
   • 算法简单，合并会出现问题：一旦合并就不能撤销，可能会对后续操作产生影响。
   • 复杂度比较大O(n^2)

5.3diana算法

1. 簇的直径:一个簇中的任意两个数据点的距离中的最大值
2. 平均相异度(平均距离):
3. 算法步骤

   将所有对象当做一个初始簇
   for(int i = 1; i <= k; i++){
       在所以簇中挑选出最大直径的簇C
       找出C中与其他点平近距离最大的一个点p放入splinter group,剩余点放入old party
       Repeat
           在old party中找出到splinter group比到old party更近的点，加入splinter group
       Until 没有新的点被分到splinter group
       splinter group 与 old party 就被分解为两个新的簇
   }
   

4. 例题

 六、 基于密度的聚类方法

6.1概述

1. 基于密度聚类方法
   • 只要一个区域中点的密度(对象、数据点的数目)超过阈值，就将其加到与之相近的聚类中
2. 可以过滤噪声、孤立点、发现任意形状的簇
3. 代表算法:Dbscan、Optics、Denclue