聚类算法最佳实践(一)

理论篇

在学习聚类算法之前，我们首先要搞清什么是聚类？什么是分类?

分类:作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并且断言所有待分类项都有一个类别与之对应.
聚类:而聚类指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，这在机器学习中被称作 unsupervised learning （无监督学习）。

聚类模型的核心思想？

物以类聚，人以群分。或者用“近朱者赤,近墨者黑”来理解也可以。

理解聚类分析的关键是什么？

1.首先在建立模型之前，我们既不知道数据到底是来自几个类；也不知道每个数据到底是那一类；也不知道类和类的界限是什么。2.建立聚类模型后最终达到的目标是：组内数据样本之间的亲疏程度最近，组间的数据样本之间的亲疏程度最远。3.所谓亲疏程度就是两个数据（变量）综合考虑各指标后的接近程度，比如常用的欧式距离。

除了欧式距离还有哪些距离度量方式？

距离选择的原则？

1.要考虑所选择的距离公式在实际应用中有明确的意义。如欧氏距离就有非常明确的空间距离概念。马氏距离有消除量纲影响的作用。2.要综合考虑对样本观测数据的预处理和将要采用的聚类分析方法。如在进行聚类分析之前已经对变量作了标准化处理，则通常就可采用欧氏距离。3.考虑研究对象的特点和计算量的大小。实际中，聚类分析前不妨试探性地多选择几个距离公式分别进行聚类，然后对聚类分析的结果进行对比分析，以确定最合适的距离测度方法。

聚类就是k-means算法吗？

k-means只是聚类算法中最常见也是最容易理解和上手的一种，聚类算法不仅限于k-means一种，常用的还有AP聚类、均值漂移聚类、系统聚类（又称层次聚类）、k-medians（k中位数聚类）、DBSCAN（密度聚类）、Birch（又称TF-tree聚类），这些都需要我们学习了解，实际应用中使用哪一种聚类算法还需要我们结合业务经验给予判断。

合理运用聚类算法的关键因素

1.数据的采集、抽样以及初始中心点的选取，后面我们会讲到在sckit-learn中对此做的优化思想。2.聚类种类k值的选择。人工经验选择和机器选择两种，机器选择主要依靠手肘原则。3.距离度量的手段，大多数情况下使用的欧式距离。4.聚类算法的选取，理论上取决于聚类结果是否为非凸形状的簇、聚类结果之间大小差别是否较大、时间复杂度这三个方面。5.异常值处理，尤其是k-means算法对异常值非常敏感，所以在建模前对异常数据的预处理工作也很重要。6.空值/缺失值的处理，聚类算法本身不允许存在缺失值/空值，对于这部分我们如何填充也至关重要，比如数字0填充，数字-1填充、数字999填充，均值填充等。7.对于不同变量间的数据量纲必须统一，如果量纲不统一，可以对数据进行标准化，常用的标准化方法有：归一化、zscore得分等。

实战篇_k-means上手

一个k-means快速上手的示例

作为一个不折不扣的调包侠，百度一下sckit-learn中文文档，嗖嗖嗖，拿到下面这几行代码，咔咔咔，三下五除二就能轻轻松松实现一个k-means聚类模型，在python的各种机器学习包的便利之下，入门机器学习的门槛变的很低，但只会调包终究停留在小白的层面，很难根据实际场景举一反三。

>>> from sklearn.cluster import KMeans>>> import numpy as np>>> X = np.array([[1, 2], [1, 4], [1, 0],... [10, 2], [10, 4], [10, 0]])>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)>>> kmeans.labels_array([1, 1, 1, 0, 0, 0], dtype=int32)>>> kmeans.predict([[0, 0], [12, 3]])array([1, 0], dtype=int32)>>> kmeans.cluster_centers_array([[10., 2.], [ 1., 2.]])

实战篇_k-means进阶

k-means算法的一般流程

使用伪代码可以表示如下：

创建k个点作为起始质心(经常是随机选择) 当任意一个点的簇分配结果发生改变时 对数据集中的每个数据点 对每个质心  计算质心与数据点之间的距离 将数据点分配到距其最近的簇  对每一个簇，计算簇中所有点的均值并将均值作为质心

从0到1实现一个k-means雏形

从以上伪代码可知，k-means算法实现可分解为数据之间的距离计算（常用为欧式距离）、初始起始质心选取（常为随机选取）、质心迭代直到收敛。由此我们可以给出distEculd、randCent、kMeans这三个函数：

def distEclud(vecA, vecB): # 欧式距离计算 return sqrt(sum(power(vecA - vecB, 2)))

def randCent(dataSet, k): # 构建初始质心 n = shape(dataSet)[1]  centroids = mat(zeros( (k,n)))  for j in range (n) : minJ = min(dataSet[:,j]) rangeJ = float(max(dataSet[:,j]) - minJ) centroids[:,j] = minJ + rangeJ * random.rand(k,1) return centroids

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent): # 获取数据集的行数m m = shape(dataSet)[0] # 创建一个m*2的零矩阵，第一列用于存放分类结果， # 第二列用于存放数据点与聚类中心的方差即欧式距离的平方 clusterAssment = mat(zeros((m,2))) # 调用randCent方法构建初始聚类中心 centroids = createCent(dataSet, k) clusterChanged = True  while clusterChanged: clusterChanged = False  # 对每一条数据即一组m维的向量 for i in range(m): # 初始化最近距离为无穷大，分类结果为-1 minDist = inf;minlndex = -1 # 对随机给出的k的初始质心 for j in range(k): # 计算当前数据与k个质心的聚类，并寻找最近的质心 distJI = distMeas(centroids[j,:], dataSet[i,:]) if distJI < minDist: minDist = distJI; minlndex = j if clusterAssment[i,0] != minlndex: clusterChanged = True clusterAssment[i,:] = minlndex, minDist**2 print (centroids) for cent in range(k): # 所有行数据投票给最近的质心后，更新质心的位置继续下一次迭代，直到质心不再改变为止 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent) [0]] # 通过计算当前分组的均值更新质心 centroids[cent,:] = mean(ptsInClust, axis=0) return centroids, clusterAssment

其中distEculd、randCent都是函数kMeans的辅助函数，distEculd负责计算两个数据向量之间的欧式距离，randCent负责通过随机方式给出初始化质心。我们对数据集X按照我们实现的kMeans方法重新做一次预测，结果如下：

>>>X = np.array([[1, 2], [1, 4], [1, 0],... [10, 2], [10, 4], [10, 0]])>>>kMeans(X, 2)[[6.85601978 2.20940709] [3.35132326 2.1726808 ]][[10. 2.] [ 1. 2.]]Out[52]:(matrix([[10., 2.], [ 1., 2.]]), matrix([[1., 0.], [1., 4.], [1., 4.], [0., 0.], [0., 4.], [0., 4.]]))

从上述输出结果可以看到聚类收敛后最终的聚类中心为[[10. 2.],[ 1. 2.]],预测分类结果为[1,1,1,0,0,0],这与我们使用sckit-learn模块儿输出的结果一致。

sckilt-learn中KMeans参数刨析

回头审视一下我们实现的k-means雏形，在kMeans方法中，主要参数只有dataSet和k这两个，如果我们仔细阅读sckit-learn包中KMeans方法的能够让我们配置的参数多达11个。

class sckit-learn.cluster.KMeans(): def __init__(self, n_clusters=8, init='k-means++', n_init=10, max_iter=300, tol=1e-4, precompute_distances='auto', verbose=0, random_state=None, copy_x=True, n_jobs=None, algorithm='auto'):

•n_clusters:质心数量，也就是分类数，默认是8个。•init:初始化质心的选取方式，主要有下面三种参数可选，‘k-means++’、‘random’or ndarray, or a callable，默认是'k-means++'。因为初始质心是随机选取的，会造成局部最优解，所以sckilit-learm在这里对初始化方法做了优化，假设已经选取了n个初始聚类中心(0<n<K)，则在选取第n+1个聚类中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心，但在选取第一个聚类中心(n=1)时同样通过随机的方法，之所以这样做是因为聚类中心互相离得越远越好。这个方法在sklearn中通过给init参数传入“k-means++”即可。•n_init:随机初始化的次数，kmeans质心迭代的次数。•max_iter:最大迭代次数，默认是300。•tol:误差容忍度最小值,默认是0.0001。•precompute_distances:是否需要提前计算距离，auto,True,False三个参数值可选。默认值是auto，如果选择auto，当样本条数*分类数>1200万时（等同于100M的作业开销），就不会提前进行计算，如果小于则会与提前计算。提前计算距离会让聚类速度很快，但是也会消耗很多内存。
copy_x:主要起作用于提前计算距离的情况，默认值是True,如果是True,则表示在源数据的副本上提前计算距离时，不会修改源数据。•verbose:冗长模式，默认为0，不打印任何过程信息。修改为True后会打印相应过程信息。•random_state:int,默认为None,确定质心初始化的随机数生成。使用一个整数，使随机性确定性。•n_jobs：启用进程数。•algorithm：优化算法的选择，有auto、full和elkan三种选择。full就是一般意义上的K-Means算法，elkan是使用的elkan K-Means算法。默认的auto则会根据数据值是否是稀疏的(稀疏一般指是有大量缺失值)，来决定如何选择full和elkan。如果数据是稠密的，就选择elkan K-means，否则就使用普通的Kmeans算法。
以上11个参数中通常只有n_clusters和random_state这两个参数需要我们去手动指定，其他参数在大部分情况下使用默认值就可以，但想要用好k-means算法，尤其要清楚init、precompute_distances、algorithm这三个参数的含义以及为什么要这么做，在我看来k-means算法本身的优缺点都很明显，而sckit-learn所提供方法与我们第三部分实现的k-means雏形的区别就在于这三个参数分别对模型初始化方法、聚类效率、样本稀疏性这三方面做的改进。

未完待续！后续将在聚类算法最佳实践（二）中分享其他几类聚类算法的心得和实战经验。