互联网数据分析（4）

Posted on | Edited on | In , | Comments: | Views:

第四章：聚类分析

1. 概述

聚类分析的定义

  • 聚类分析(Cluster Analysis)是一个讲数据集中的所有数据，按照相似性划分为多个类别（Cluster，簇）的过程
    • 簇是相思数据的集合
  • 聚类分析是一种无监督分类方法：无训练集和预定义的类别标号
  • 要求：聚类之后，应保证高内聚、低耦合即同类之间相似性低，不同类之间相似度低

聚类分析的作用

  • 作为一个对的工具来获得数据集中数据的分布情况
    • 首先对数据集执行聚类，获得所有簇
    • 然后根据每个簇的样本数目获得每类数据的大体分布情况
  • 作为其他数据挖掘算法的预处理步骤

聚类分析的应用

  • 谁经常光顾商店,谁买什么东西,买多少
  • 识别顾客购买模式(如喜欢一大早来买酸奶 和鲜肉、习惯周末时一次性大采购)
  • 按会员卡记录的购买次数、购买时间、性 别、性别、年龄、购物种类、金额等变量 分类
  • 刻画不同用户群的特征 聚类中异常点的分析:欺诈
  • 通过对现有用户分群，以期对不同类别的用户采用不同的营销方式，如交叉营销(cross-sell)、向上营销(up-sell)等，并对可能流失的用户提前预警并采取相应措
    施。

常用聚类分析方法：

划分法

以距离作为数据集中不同数据间的相似性度量，将数据集划分成多个簇

方法：k-means、k-medoids

层次法

对给定的数据集进行层次分解，形成一个树形的聚类结果

方法：自顶向下法、自底向上法

2. 相似性计算

在聚类分析中，样本之间的相似性通常采用样本之间的距离来表示。

样本之间的经历实在样本的描述属性（特征）上进行计算的

样本的描述属性类型可能不同，相对应的计算方法也不同

连续性属性

重量、高度、年龄等

X~i~ =()

二值离散属性

多值离散属性

转换为二值属性进行计算

混合类型属性

划分聚类法：k-means

优点：

可扩展性比较好，算法复杂度为O(nkt)（n为样本数量，k是簇的个数，t是迭代次数）

缺点：

簇数k需要事先给定

初始点的选择影响算法迭代次数和聚类结果

对噪声和离群点数据敏感

其他缺陷：只能处理连续、二值、定序的数据类型，不能处理离散分类变量

节点编辑

更改容忍度：

集合编码值：避免二值属性数值高于连续属性的情况

轮廓系数（Silhouette系数）：

  • a~i~表示样本i到同簇其他样本的平均距离
  • b~i~表示样本i到其他簇的最小平均距离
  • 单个样本的轮廓系数s(i)为：$s(i)=(b(i)-a(i))/max{a(i),b(i)} $
  • 总体轮廓系数可取单个样本轮廓系数的平均值，轮廓系数大小在-1（极差）到1（极好）之间。

新生成的字段kMD-K-Means 到聚类中心点的距离

案例：

汽车数据表

在进行聚类之前可以按照意义生成一些新变量，这些新变量可能会对聚类结果有不同的影响

卖家表

  1. 数据清洗，剔除全部缺失的行、将信用等级转换为数值型变量（最初一对一转换效果不好，改成二对一转换，即两个相邻档次对应一个数值
  2. 年龄按固定宽度分级，10岁为一级
  3. 使用年龄、信用等级、性别三项数据进行聚类，聚类k值设为6时，轮廓系数最优
  4. 结果解读：年龄大多在20~30之间，信用为3~4之间，性别全部分开
  5. 拓展：处理省份按发达程度分类后加入聚类

使用自动聚类节点比较不同的聚类算法的结果，在放弃选项栏下选择筛选条件

两步聚类

预聚类阶段(pre-clustering)

采用了BIRCH算法中CF树生长的思想,逐个读取数据集中数据点,在生成CF树的同时,预先聚类密集区域的数据点,形成诸多的小的子簇(sub-cluster)。

聚类阶段(clustering)

以预聚类阶段的结果——子簇为对象,采用分层聚类方法递归逐个地合并子簇,直到期望的簇数量。

BIRCH算法

  • BIRCH算法的核心是利用树结构来快速的聚类,一般将它称之为聚类特征树(Clustering Feature Tree,简称CFTree)。
  • 这颗树的每一个节点是由若干个聚类特征 (Clustering Feature,简称CF)组成。每 个节点包括叶子节点都有若干个CF,而内 部节点的CF有指向子节点的指针,所有的 叶子节点用一个双向链表链接起来。

一个聚类特征CF的定义:
每一个CF是一个三元组,可以用(N, LS,SS)表示。其中N代表了这个CF中 拥有的样本点的数量;LS代表了这个CF 中拥有的样本点各特征维度的和向量, SS代表了这个CF中拥有的样本点各特征 维度的平方和。

CF树的性质
  • CF满足线性关系,即:
    CF1+CF2=(N1+N2,LS1+LS2,SS1+SS2)。
  • 在CF Tree中,对于每个父节点中的CF 节点,它的(N,LS,SS)三元组的值等于 这个CF节点所指向的所有子节点的三元组之和。
CF树的属性
  • B是每个内部节点的最大CF数,L是每个叶子节点的最大CF 数,对于上图中的CF Tree,限定了B=7, L=5, 也就是 说内部节点最多有7个CF,而叶子节点最多有5个CF。
  • 叶节点每个CF的最大样本半径阈值T,也就是说,在这个 CF中的所有样本点一定要在半径小于T的一个超球体内。
CF树的生成
  1. 从根节点向下寻找和新样本距离最近的叶子节点和叶子 节点里最近的CF节点。
    1. 如果新样本加入后,这个CF节点对应的超球体半径仍然 满足小于阈值T,则更新路径上所有的CF三元组,插入结束 。否则转入3.
    2. 如果当前叶子节点的CF节点个数小于阈值L,则创建一个 新的CF节点,放入新样本,将新的CF节点放入这个叶子节点 ,更新路径上所有的CF三元组,插入结束。否则转入4。
    3. 将当前叶子节点划分为两个新叶子节点,选择旧叶子节 点中所有CF元组里超球体距离最远的两个CF元组,分别作为 两个新叶子节点的第一个CF节点。将其他元组和新样本元组 按照距离远近原则放入对应的叶子节点。依次向上检查父节 点是否也要分裂,如果需要按和叶子节点分裂方式相同。
生成CF树之后

BIRCH算法的主要过程,就是建立CF Tree 的过程,此外还包括对CF Tree的优化。 如:

  • 去除一些异常CF节点,这些节点一般里面的 样本点很少。对于一些超球体距离非常近的 元组进行合并。
  • 利用其它的一些聚类算法比如K-Means对所有 的CF元组进行聚类,主要目的是消除由于样 本读入顺序导致的不合理的树结构,以及一 些由于节点CF个数限制导致的树结构分裂。

Tag Cloud