0引言
我做过一段时间车联网大数据分析，当然实际上是跟着一位大姐打杂学习。感觉最有意思的一部分内容是基于车主用户的轨迹数据、使用聚类的方法得到用户的常用路径，进而知道用户经常往返的地点，然后就可以推测用户的住址和公司地址了。如果再做下去，就可以做一些广告推荐之类的东西——然而没有然后，公司黄了。
不过聚类算法的奇妙一直印在我的脑子里：不需要标签就能把样本分成若干有内在关联的小组。
正是因为聚类算法的这种特点，它可以解决很多看起来无从下手的任务，比如图像分割、用户画像、异常检测、GPS轨迹数据模式抽取等等；另外，当我们对数据了解比较少的时候，可以先基于一些特征进行聚类，看看各个小组的数据内容有什么特点，也许会有发现。
常见的聚类算法有kmeans，meanshift, DBSCAN,HMM,LDA（Latent Dirichlet Allocation），等等等(HMM的无监督模式，和LDA都可以看做聚类算法)。本文将介绍最简单的kmeans聚类算法。
1分类与聚类的关系
分类和聚类是两种认识和管理事物的方法，我们人类一直在使用。
1.1分类
我们在生活和生产中，经常会搞“分类”——选择一些关键特征，基于这些特征的取值，将事物分门别类，进而将事物管理起来。我们常听到的“管理”，一个基本的目的是降低被管理的事物的复杂度。“分类”就是我们降低世界的复杂程度的一种有效手段：我主要记住一类事物的重要特征，而不需要记住这类事物的每一个个体的特征，就可以从大脑里快速获取关于这些个体的重要信息，然后快速地做出决策。
人可以分类，为啥我们要搞分类算法呢？我们常说的基于机器学习方法的分类算法，指的是这样以为算法，它们可以自动的从有标签数据中，学习特征到类别的映射规则（或函数）。这也是“人工智能”的“智能”的一种来源。“自动”，狭义地讲就是机器可以完成；再狭义一点，就是计算机可以完成。
举个人类在生活中分类的例子。假设我在野外玩耍时，遇到一个长着獠牙的大型动物，长得像二师兄。我判断这是一头大野猪，赶紧匿了。基于外形特征判断动物的类别，这就是一次分类行为。
问题来了，存储在我的大脑里的“分类器”是怎么来的呢？我的分类器实际上是基于从《动物世界》里提取的有标签数据训练出来的。电视节目比较详细地展示了野猪的特征，比如脸长、有灰褐色的毛发、尾巴较短等等(当然主要是图像特征，文字描述在脑海里主要负责辅助记忆和思维过程)。特征取值水平符合记忆里的模式的，我都判定为野猪。由于训练数据的限制，要是问我“这个是不是疣猪”，答案是“不知道”。
还有一个问题，“野猪”这个概念是怎么出现的呢？
1.2聚类
地球上存在的生物种类非常非常多，生物学家为了了解它们是如何出现的，经常要为某一种生物“找祖宗”或者“找亲戚”，也就是确定进化路径。经常有这样的情况，即专家会把一种以前认为是某种类别的动物，重新划分到另一种类别。比如河马，有一段时间，大家认为它猪是近亲，因为二者共同点很多，最突出的是都有偶数个脚趾。再后来，一些科学家用分子生物学的方式，也就是比较DNA序列的相似度，比较河马和其他动物的相似程度，发现河马和鲸鱼的关系最近，在进化史上是”表兄弟”，它们有共同祖先。就这样，科学家基于河马和鲸的相似度，把二者归到了同一个组。
这是一个聚类的操作，科学家基于某些特征和相似度度量方法，把相似的事物划分到同一个组。 人们使用的聚类方法有很多，这里就不列了。
总的来说，聚类是一种挺消耗脑力的动作，因此人们也追求将聚类自动化、提出了很多聚类算法，其中最具代表性的是kmeans。
1.3聚类算法的应用场景
教材里对聚类的介绍比较抽象，我看当时看不明白，不知道为什么这些学者要设计这种算法。后来在工作接触了一些相关场景，才发现聚类方法和思想可以用来解决很多问题。
两种情况下我们可以考虑聚类算法：（1）当我对研究对象所知甚少的时候，可以先聚类一把，看看样本里有没有“群体”，甚至是有意义的群体；（2）当我们对研究对象所知甚少，但是又必须对它们进行分组(分类，聚合等称呼都可以)时，可以用聚类算法来做。有一次，一位创业的师兄接了一个项目，内容是关于李宇春的一次舆情事件分析。任务里包含对微博评论列表内容的分析，由于评论数据量好几万，业务人员分析不过来。师兄说，你来做聚类吧。我和一个师弟就基于词向量特征做了一个聚类，先按照内容对这些评论分组(聚类结果一般是若干组样本，一个组通常成为“簇”)；然后交给业务人员，他们从聚出来的簇中寻找有意义的，然后概括了一下，就成了评论分析结果报告。
2kmeans聚类算法
2.1kmeans的假设
Kmeans做了几个假设，让任务更简单一点：
（1） 具体事物之间是有区别的，“区别”的大小可以用某种指标来度量。
（2） 距离较小的事物，在某些方面上比较相似，我们可以把他们归为一类。
这两个假设就是kmeans聚类算法的核心。
2.2kmeans聚类算法的重要组件
Kmeans聚类算法的重要组件包括:(1)类的个数;(2)距离的计算方式。
Kmeans要求我们规定一个参数，就是研究对象需要分成的组的个数。当然，这有一点不科学：我对研究对象还没有太多了解呢，我怎么知道需要分成几组？不用担心，我们可以试一下大于1的若干整数。有一些策略可以帮助我们确定分成几组合适。
Kmeans需要一个度量样本之间距离的指标。欧氏距离、余弦距离、海明距离、杰卡德距离等等，根据需求选择。一般来说，场景会提供决策依据。
2.3kmeans聚类算法的工作过程
如表2-1，是赵本山、我、孙悟空、盼盼和舒克的身高体重数据。现在我们需要基于身高和体重，对这些研究对象进行聚类。
表1-1 研究对象体测数据
我们在二维坐标系中画出这5个点，如图2-1。
我们开始聚类，首先尝试k=2。
首先从5个点中随机挑选两个，作为初始簇中心。当然也可以从平面上任选两点。如图2-1，C和E被选为初始簇中心，标记为红色。
接下来，我们计算其余点与两个簇中心的距离，并将其余节点划分到距离较近的簇中心一组。如图2-3，A、B和D被划分到E这一组； E这一组只有E一个。
完成了第一次分组，我们需要为各个簇找到簇中心，也就是常说的“质心”。最简单的就是簇内各点坐标取均值,如图2-4。
接下来，我们再一次计算每一个点到簇中心的距离，然后选择它们归属的簇中心，如图2-5。这一次，E点由于距离1号簇中心更近，归属到了1号簇中心。新的划分结果是，C和E分到1号簇，A、B、D划分到一个簇。
再一次计算各个簇的中心，如图2-6。后面就是一直迭代寻找归属簇中心和更新簇中心的过程，直到簇的内容不再变化，也就是收敛，如图2-7和图2-8。
我们发现，我和赵本山一组，孙悟空、盼盼和舒克一组。经过专家查询资料和分析，我们发现前面一组是人类，后面一组是动物——这个划分有实际含义，好，就是这样了。我们从这份数据中找到了两个群体，一个是人类，另一个是动物。
2.4如何度量聚类的效果
专家觉得前面得到的聚类结果是有意义的，效果还不错。不过我们搞科研或者工程，得尽量用数字来度量“效果”，以便做各种比较。我们经常用轮廓系数来度量聚类的效果。
聚类嘛，我们希望一个簇内的样本距离越近越好，不同簇的样本越远越好。有人按照这个思路提出了轮廓系数。
轮廓稀系数首先是用来评价一个样本的归属划分效果的。假设点i归属于m号簇，而距离点i最近的其他簇是n号簇计算方式为：
基于各个样本的轮廓稀疏，我们可以计算整个聚类结果的轮廓系数：
一般来说，我们会选择轮廓系数最高的k值，作为聚类结果。
2.5KNN分类器
是的，kmeans的结果可以用来构建一个knn分类器。详情可以参考关于knn分类器的各种文章。
3kmeans的python实现
import numpy as np
#一个最简单的KNN
class KNN():
def __init__(self):
self.model = {}#存储各个类别的训练样本的特征，key为类别标签，value是一个list，元素为样本的特征向量
self.training_sample_num = {}#存储训练数据中，各个类别的数量
#训练模型，输入是标签列表，和对应的输入数据列表
def fit(self, X, Y):
for i in range(len(Y)):
#将训练数据按照类别分组
if Y[i] in self.model:
self.model[Y[i]].append(X[i])
else:
self.model[Y[i]] = [X[i]]
#各个类别的样本总数
self.training_sample_num[Y[i]] = self.training_sample_num.get(Y[i], 0) + 1
#预测/判断一个样本的类别。这里模仿sklearn的风格，允许输入单个样本，也允许输入多个样本
def predict(self, X):
result = None
if type(X[0])==list:
for x in X:
result.append(self.predict_one(x))
else:
result = self.predict_one(X)
return result
#判断单个样本的类别
def predict_one(self, x):
label = None#类别标签
min_d = None#目前为止，待分类样本与各类代表性样本的最小平均距离
for class_label in self.model:#遍历每个类别的代表性样本
sum_d = 0#待分类样本与本类别的代表性样本的距离之和
for sample in self.model[class_label]:#遍历这个类别下所有的代表性样本
sum_d += self.distance(x, sample)#累计
mean_d = sum_d/self.training_sample_num[class_label]#待分类样本与本类别的代表性样本的平均距离
if min_d==None or mean_d<=min_d:#如果遍历到第一个类别，或者待分类样本与当前类别的平均距离比之前的更低，更新类标签与最小距离
label = class_label
min_d = mean_d
return label
#计算两个样本之间的距离
def distance(self, x1, x2, type="eu"):
d= None
if type=="eu": d = np.sum((x1-x2)**2)#欧氏距离
return d
#评估模型效果
def eveluate(self, X, Y):
pass
#制造训练数据
def generate_training_data(self):
data_str = """类别 样本唯一标识 身高(cm) 体重(kg) 尾巴长度(cm)
A 高秀敏 160 60 0
A 赵本山 170 70 0
A 范伟 170 70 0
A 宋丹丹 160 60 0
B 金丝猴孙悟空 120 40 100
B 大熊猫盼盼 100 100 10
B 大象hadoop 300 3000 50
B 老鼠舒克 10 0.1 10"""
print(data_str)
data_list = data_str.split('\n')
X = []
Y = []
for line in data_list[1:]:
data = line.split(" ")
Y.append(data[0])
X.append(list(map(lambda x: float(x), data[2:])))
return X, Y
if __name__ == '__main__':
M = KNN()
train_X, train_Y = M.generate_training_data()
print(train_X)
M.fit(train_X, train_Y)
xiao_li_zi = np.array([175,75,0])
res = M.predict(xiao_li_zi)
print(res)4结束语
kmeans聚类算法是我们学习过程中最早遇到的无监督机器学习算法，它的想法和KNN比较接近，可以对照着来看。
当然了，kmeans也可能是最弱的聚类算法之一，我们还需要了解一下别的聚类算法，然后根据场景要求选择。
注意：本文为李鹏宇(知乎个人主页
https://www.zhihu.com/people/py-li-34)原创作品，受到著作权相关法规的保护。如需引用、转载，请注明来源信息：（1）作者名，即“李鹏宇”；（2）原始网页链接，即
https://zhuanlan.zhihu.com/p/76631018址。如有疑问，可发邮件至我的邮箱:lipengyuer@126.com。
