我们思考这样一个问题:在餐饮行业中,
餐饮企业遇到的这些问题,可以通过聚类分析解决。
聚类分析是一种无监督学习,而我们前面介绍的Logistic回归和决策树算法这两种分类算法则属于有监督学习。这两者的区别是什么呢?
回答这个问题其实很简单,就看输入数据是否有标签(label)。输入数据有标签,则为有监督学习,没标签则为无监督学习。
今天我们介绍以下几个问题:
** 1. 聚类分析思想**
2. 主要聚类方法
3. 类间、类内距离的度量
4. 层次聚类(谱系聚类)
5. 划分聚类法(快速聚类法)
6. 其他问题
7. 用python具体实现
那么,什么是类内对象相似性、类间对象相似性呢?又该如何度量它们呢?这个我们放在第三部分讨论,这里我们先来看看主要的聚类方法。
聚类的方法有:
划分的方法
层次的方法
基于密度的方法
基于网格的方法
基于模型的方法
刚才我们说到,聚类分析的目标是:类内对象相似性尽量大,类间对象相似性尽量小。
那么,什么是类内对象相似性、类间对象相似性呢?又该如何度量它们呢? 首先我们介绍:
若类$G_p$中有对象$x_1, x_2, ...,x_n$,则其均值$$\bar{x}_p=\frac{1}{n_p}\sum_{i=1}^{n_p}x_i$$称为类$G_p$的质心(或重心)。
类的形式和形状多种多样,所以类与类之间的距离有多种定义与计算方法。如果我们定义类$G_p$和$G_q$之间的距离为$D_{pq}$
$$D_{pq}=\min\limits_{i\in{G_F},j\in{G_q}}d_{ij}$$
其中,$\bar{x}_p$和$\bar{x}_q$分别是两个类的重心,即计算两个中心之间的距离
$$D_{1+2}=\sum_{k\in{G_F}\bigcup{G_q}}(x_k-\bar{x})'(x_k-\bar{x})\Rightarrow{D_{pq}=D_{1+2}-D_1-D_2}$$离差平方和距离:计算每个类的离差平方和,将两个类看做一个类计算离差平方和,再计算二者之间的差额。
假定观测样品之间的距离皆采用欧式平方距离,即$$d_{ij}=d^2(x_i,x_j)^{T}(x_i,x_j)=\parallel{x_i-x_j}\parallel^2$$则类间距离递推公式有统一的形式:$$D_{kr}^2=\alpha_pD_{kp}^2+\alpha_qD_{kq}+\beta{D_{pq}^2}+\gamma\mid{D_{kp}^2-D_{kq}^2}\mid$$
我们用类内平方和来定义类内距离。
设某层次水平上类的个数是G。类$G_{k}(k=1..G)$的类内离差平方和记为:$S_{k}=\sum_{i\in{G_k}}(x_i-\bar{x}_k)^T(x_i-\bar{x}_k)=\sum_{i\in{G_k}}\parallel{x_i-x_k}\parallel^2$
其中$\bar{x}_k$是类$G_k$的重心。$S_{k}$越小,说明$G_k$中各样品越相似。
令$$P_{G}=\sum_{K=1}^{G}S_k$$
以T记所有样品的总离差平方和,$$T=\sum_{i=1}^{n}(x_i-\bar{x})^T(x_i-\bar{x})=\sum_{i=1}^{n}\parallel{x_i-\bar{x}}\parallel^2$$其中$$\bar{x}=\frac{1}{n}\sum_{i=1}^{n}x_i$$类间离差平方和=$T-P_G$
层次聚类又分为两种,分别为:
比如,这张图从左到右就是凝聚方法,从右到左就是分裂方法。
下面我们介绍凝聚式层次聚类的步骤: - n个样品开始时作为n个类,计算两两之间的距 离,构成一个对称距离矩阵 - 选择$G_{(0)}$中的非对角线上的最小元素,设这个最小元素是$G_{pq}$。 这时$G_{p}=\{x_p\},G_{q}=\{x_q\}$。将$G_{p}$$G_{q}$合并成一个新类$G_{r}$。在$G_{(0)}$中消去$G_{p}$$G_{q}$所对应的行与列,并加入由新类$G_{r}=\{G_p,G_q\}$与剩下的其他未聚合的类间的距离组成的一行和一列,得到一个新的距离矩阵$G_{(1)}$,它是n-1阶方阵。 - 从$G_{(1)}$出发重复步骤2的作法得$G_{(2)}$。再由$G_{(2)}$出发重复上述步骤,直到n个样品聚为1个大类为止。在合并过程中要记下合并样品的编号及两类合并时的距离,并绘制聚类层次图。
某年5省城镇居民月均消费(单位:元/人)
- 分别用1,2,3,4,5表示辽宁、浙江、河南、甘肃、青海5个省。将距离矩阵记为 $G_{(0)}$ 。 - 我们的聚类过程如下: 这就得到了我们的分类结果。可是,我们应该如何度量结果呢?比如,用$R^2$统计量来度量时, $$R^2=1-\frac{P_G}{T}$$
快速聚类法先将样品粗糙地分一下类,然后再按照某种原则进行修正,直至分类比较合理为止。
其步骤如下图所示:
# K-Means算法 其算法步骤如下: - 选择K个对象作为每个类的初始质心,然后计算其它每个对象与每个质心的距离,与距离最小的质心归为一类。 - 指派到一个质心的对象集合为一个类,更新每个类的质心。 - 重复上述指派和更新质心的步骤,直至类不发生变化为止。然后按相同的原则选取xi4 ,依次下去,直至选定k个聚点
例如:一维数据集X: 1, 2, 3, 8, 9, 10, 25. 令K等于2,可能划分结果为{1, 2, 3, 8},{9, 10, 25}。其均值分别为3.5和14.67
对任何数据集是否一定可以得到聚类结果? 答案是否定的。如下图这种情况就不能得到很好的聚类结果。
我们可以利用**霍普斯金统计量H**判断数据集的聚类趋势: - 均匀的从数据集D中抽取n个点,对每个点Pi,计算其与D中最近邻的距离xi$$x_i=\min\limits{v\in{D}}\{dist(p_i,v)\}$$ - 再次均匀的从数据集D中抽取n个点,对每个点qi,计算其与D中除抽出对象外的最近邻的距离yi $$y_i=\min\limits{v\in{D}}\{dist(q_i,v)\}$$如果H近似0.5 则D不具有显著的聚类趋势
影响聚类结果的因素
聚类结果如何评价?
外在评价方法
内在评价方法
令a(o)表示任一对象o与同簇内其它对象的平均距离;
b(o)表示对象o与其它簇内对象的最小平均距离;
轮廓系数:
$$s(o)=\frac{b(o)-a(o)}{max\{a(o),b(o)\}}$$
$$-1<s(o)<1$$
取所有对象轮廓系数的平均值 ,接近1则结果佳。
我们对引子中的问题进行解决,使用K-Means算法进行聚类分析
#使用K-Means算法聚类消费行为特征数据
import pandas as pd
#参数初始化
inputfile = 'data/consumption_data.xls' #销量及其他属性数据
data = pd.read_excel(inputfile, index_col = 'Id') #读取数据
data.head()
R | F | M | |
---|---|---|---|
Id | |||
1 | 27 | 6 | 232.61 |
2 | 3 | 5 | 1507.11 |
3 | 4 | 16 | 817.62 |
4 | 3 | 11 | 232.81 |
5 | 14 | 7 | 1913.05 |
其中R表示最近一次的消费时间间隔,F表示消费频率,M表示消费总金额
首先对数据进行标准化处理
data_zs = 1.0*(data - data.mean())/data.std() #数据标准化
from sklearn.cluster import KMeans
k = 3 #聚类的类别
iteration = 500 #聚类最大循环次数
model = KMeans(n_clusters = k, n_jobs = 4, max_iter = iteration) #分为k类,并发数4
model.fit(data_zs) #开始聚类
KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=500, n_clusters=3, n_init=10, n_jobs=4, precompute_distances='auto', random_state=None, tol=0.0001, verbose=0)
# 简单输出结果
r1 = pd.Series(model.labels_).value_counts() #统计各个类别的数目
r2 = pd.DataFrame(model.cluster_centers_) #找出聚类中心
r = pd.concat([r2, r1], axis = 1) #横向连接(0是纵向),得到聚类中心对应的类别下的数目
r.columns = list(data.columns) + [u'类别数目'] #重命名表头
print(r)
R F M 类别数目 0 -0.149353 -0.658893 -0.271780 559 1 -0.160451 1.114802 0.392844 341 2 3.455055 -0.295654 0.449123 40
#详细输出原始数据及其类别
r = pd.concat([data, pd.Series(model.labels_, index = data.index)], axis = 1)
#详细输出每个样本对应的类别
r.columns = list(data.columns) + [u'聚类类别'] #重命名表头
r.head()
R | F | M | 聚类类别 | |
---|---|---|---|---|
Id | ||||
1 | 27 | 6 | 232.61 | 0 |
2 | 3 | 5 | 1507.11 | 0 |
3 | 4 | 16 | 817.62 | 1 |
4 | 3 | 11 | 232.81 | 0 |
5 | 14 | 7 | 1913.05 | 0 |