用 sklearn 对 140W 个点进行 kmeans 基于密度聚类划分 - Python - 伯乐在线
& 用 sklearn 对 140W 个点进行 kmeans 基于密度聚类划分
任务需求：现有140w个某地区的ip和经纬度的对应表，根据每个ip的/24块进行初步划分，再在每个区域越100-200个点进行细致聚类划分由于k值未知，采用密度的Mean Shift聚类方式。
1#原理部分
关于kmeans纯代码实现可以移步之前的一篇
在文中已经对代码做了详细的注释。
K-means算法是是最经典的聚类算法之一，它的优美简单、快速高效被广泛使用。它是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
从N个点随机选取K个点作为质心
对剩余的每个点测量其到每个质心的距离，并把它归到最近的质心的类
重新计算已经得到的各个类的质心
迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束
k-平均算法是解决聚类问题的一种经典算法，算法简单、快速。
对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O（nkt），其中n是所有对象的数目，k是簇的数目，t是迭代的次数。通常k&&n。这个算法经常以局部最优结束。
算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。
K 是事先给定的，这个 K 值的选定是非常难以估计的；
对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。一旦初始值选择的不好，可能无法得到有效的聚类结果；
该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
不适合于发现非凸面形状的簇，或者大小差别很大的簇；
对于”噪声”和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。
关于K值的确定主要在于判定聚合程度：提供几篇论文注意，这些论文仅仅是提供思路，不要去自己写出来，内容有点扯
2#框架资源
本次基于密度的kmeans算法使用的是 scikit-learn 框架。
官网：http://scikit-learn.org/stable/index.html
聚类算法汇总：http://scikit-learn.org/stable/modules/clustering.html
KMeans算法 : http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_assumptions.html#sphx-glr-auto-examples-cluster-plot-kmeans-assumptions-py
MeanShift算法： http://scikit-learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html#sklearn.cluster.MeanShift
meanShift 测试demo：http://scikit-learn.org/stable/auto_examples/cluster/plot_mean_shift.html#sphx-glr-auto-examples-cluster-plot-mean-shift-py
安装框架环境：http://scikit-learn.org/stable/install.html
测试数据集合下载：
数据比较小，百来个经纬度的点
3#实践操作
3.1：运用 Kmeans
使用2-6作为k值评定聚类效果
。请先下载上文中的数据集合，和测试代码放在同一目录下，确保下列运作环境已经安装完成：
完整运行代码：请结合官方文档，可以理解运行的参数和返回值
from sklearn.cluster import KMeans
from sklearn.externals import joblib
import numpy
import matplotlib.pyplot as plt
from sklearn.cluster import KMeansfrom sklearn.externals import joblibimport numpyimport matplotlib.pyplot as plt
# -*- coding: utf-8 -*-
from sklearn.cluster import KMeans
from sklearn.externals import joblib
import numpy
import time
import matplotlib.pyplot as plt
if __name__ == '__main__':
## step 1: 加载数据
print "step 1: load data..."
dataSet = []
fileIn = open('./data.txt')
for line in fileIn.readlines():
lineArr = line.strip().split(' ')
dataSet.append([float(lineArr[0]), float(lineArr[1])])
#设定不同k值以运算
for k in range(2,10):
clf = KMeans(n_clusters=k) #设定k
！！！！！！！！！！这里就是调用KMeans算法
s = clf.fit(dataSet) #加载数据集合
numSamples=len(dataSet)
centroids = clf.labels_
print centroids,type(centroids) #显示中心点
print clf.inertia_
#显示聚类效果
mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '&r', 'pr']
#画出所有样例点 属于同一分类的绘制同样的颜色
for i in xrange(numSamples):
#markIndex = int(clusterAssment[i, 0])
plt.plot(dataSet[i][0], dataSet[i][1], mark[clf.labels_[i]]) #mark[markIndex])
mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '&b', 'pb']
# 画出质点，用特殊图型
centroids =
clf.cluster_centers_
for i in range(k):
plt.plot(centroids[i][0], centroids[i][1], mark[i], markersize = 12)
#print centroids[i, 0], centroids[i, 1]
plt.show()
123456789101112131415161718192021222324252627282930313233343536
# -*- coding: utf-8 -*-from sklearn.cluster import KMeansfrom sklearn.externals import joblibimport numpyimport timeimport matplotlib.pyplot as plt if __name__ == '__main__':
## step 1: 加载数据
print "step 1: load data..."
dataSet = []
fileIn = open('./data.txt')
for line in fileIn.readlines():
lineArr = line.strip().split(' ')
dataSet.append([float(lineArr[0]), float(lineArr[1])])
#设定不同k值以运算
for k in range(2,10):
clf = KMeans(n_clusters=k) #设定k
！！！！！！！！！！这里就是调用KMeans算法
s = clf.fit(dataSet) #加载数据集合
numSamples=len(dataSet)
centroids = clf.labels_
print centroids,type(centroids) #显示中心点
print clf.inertia_
#显示聚类效果
mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '&r', 'pr']
#画出所有样例点 属于同一分类的绘制同样的颜色
for i in xrange(numSamples):
#markIndex = int(clusterAssment[i, 0])
plt.plot(dataSet[i][0], dataSet[i][1], mark[clf.labels_[i]]) #mark[markIndex])
mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '&b', 'pb']
# 画出质点，用特殊图型
centroids =
clf.cluster_centers_
for i in range(k):
plt.plot(centroids[i][0], centroids[i][1], mark[i], markersize = 12)
#print centroids[i, 0], centroids[i, 1]
plt.show()
效果截图如下：
3.1：使用MeanShift自动生成k值删除游离点
注意此部分中数据集合需要转换为np.array类型。
# -*- coding: utf-8 -*-
from sklearn.cluster import KMeans
from sklearn.externals import joblib
import numpy ,time
import matplotlib.pyplot as plt
from sklearn.cluster import MeanShift, estimate_bandwidth
import numpy as np
if __name__ == '__main__':
## step 1: 加载数据
print "step 1: load data..."
dataSet = []
fileIn = open('./data.txt')
for line in fileIn.readlines():
lineArr = line.strip().split(' ')
dataSet.append([float(lineArr[0]), float(lineArr[1])])
numSamples = len(dataSet)
X = np.array(dataSet) #列表类型转换成array数组类型
bandwidth = estimate_bandwidth(X, quantile=0.2, n_samples=500)
clf = MeanShift(bandwidth=bandwidth, bin_seeding=True,cluster_all=True).fit(X)
centroids = clf.labels_
print centroids,type(centroids) #显示每一个点的聚类归属
# 计算其自动生成的k，并将聚类数量小于3的排除
arr_flag = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
for i in clf.labels_:
arr_flag[i]+=1
for i in arr_flag:
if(i & 3):
mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '&r', 'pr']
#画出所有样例点 属于同一分类的绘制同样的颜色
for i in xrange(numSamples):
plt.plot(dataSet[i][0], dataSet[i][1], mark[clf.labels_[i]]) #mark[markIndex])
mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '&b', 'pb']
# 画出质点，用特殊图型
centroids =
clf.cluster_centers_
for i in range(k):
plt.plot(centroids[i][0], centroids[i][1], mark[i], markersize = 12)
print centroids #显示中心点坐标
plt.show()
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
# -*- coding: utf-8 -*-from sklearn.cluster import KMeansfrom sklearn.externals import joblibimport numpy ,timeimport matplotlib.pyplot as pltfrom sklearn.cluster import MeanShift, estimate_bandwidthimport numpy as np if __name__ == '__main__':
## step 1: 加载数据
print "step 1: load data..."
dataSet = []
fileIn = open('./data.txt')
for line in fileIn.readlines():
lineArr = line.strip().split(' ')
dataSet.append([float(lineArr[0]), float(lineArr[1])])
numSamples = len(dataSet)
X = np.array(dataSet) #列表类型转换成array数组类型
bandwidth = estimate_bandwidth(X, quantile=0.2, n_samples=500)
clf = MeanShift(bandwidth=bandwidth, bin_seeding=True,cluster_all=True).fit(X)
centroids = clf.labels_
print centroids,type(centroids) #显示每一个点的聚类归属
# 计算其自动生成的k，并将聚类数量小于3的排除
arr_flag = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
for i in clf.labels_:
arr_flag[i]+=1
for i in arr_flag:
if(i & 3):
mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '&r', 'pr']
#画出所有样例点 属于同一分类的绘制同样的颜色
for i in xrange(numSamples):
plt.plot(dataSet[i][0], dataSet[i][1], mark[clf.labels_[i]]) #mark[markIndex])
mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '&b', 'pb']
# 画出质点，用特殊图型
centroids =
clf.cluster_centers_
for i in range(k):
plt.plot(centroids[i][0], centroids[i][1], mark[i], markersize = 12)
print centroids #显示中心点坐标
plt.show()
运行截图如下：
其中第一部分是每一个点在聚类之后所属的类的标识，可以看出最高有7,说明该集合最多聚集了8个类，显示的数值为5则是聚类中类数目大于3的有5个。
关于项目最后
140w个经纬数据，按照ip/24分类，分出19660个24块，对每一个24块聚类，将分类结果和游离点标记，重新写回数据库，项目完结。
总计运算时间约半小时。其实聚类耗时少，测试时时间主要消耗在绘图上。曾经直接将10000个点一起聚类，但是在大的距离尺度下，密度的衡量值就变化了，导致10000个点只分出10个类别，导致精度不和要求所以拆分块之后再聚类。
打赏支持我写出更多好文章，谢谢！
打赏支持我写出更多好文章，谢谢！
关于作者：
可能感兴趣的话题
请问您在文中最后说的24块是什么意思呢？Ip是什么意思呢？
按照您的说法，如果一共3万个经纬度数据似乎也是要分块的意思？不过不太明白是怎么分块的？
o 256 回复
关于 Python 频道
Python频道分享 Python 开发技术、相关的行业动态。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2017 伯乐在线K-Means聚类算法（一）：算法思路2 years ago很多人已经急着想试一下了，那么，在正式编程开始之前，我们不妨先使用Matlab提供的内置的K-Means感受一下（代码在GitHub上自己下载，你的Matlab要支持K-Means哦，我的版本是r2015a）实际编程的时候，我们会遇到如下问题：1，怎么初始化才能更快收敛不震荡？2，如果有一中心点初始化的时候离得远了，或者被其它中心点包围了，导致每个数据点都不肯找他怎么办？3，如何评价算法是否收敛？ 4，算法不收敛怎么办？5，能不能给每个点设置权重？……还有这些奇奇怪怪的优化问题：1，如何高效的使用Matlab计算欧氏距离？2，如何快速计算出每一个点属于哪一类？3，如何保存和输出结果？怎么设计数据结构？……这些在K-Means聚类算法的思路、实现、改进及原理（二）：算法的实现里详细讨论。138收藏分享举报文章被以下专栏收录做好玩的、大部分人都能读懂的数据科学笔记推荐阅读{&debug&:false,&apiRoot&:&&,&paySDK&:&https:\u002F\\u002Fapi\u002Fjs&,&wechatConfigAPI&:&\u002Fapi\u002Fwechat\u002Fjssdkconfig&,&name&:&production&,&instance&:&column&,&tokens&:{&X-XSRF-TOKEN&:null,&X-UDID&:null,&Authorization&:&oauth c3cef7c66aa9e6a1e3160e20&}}{&database&:{&Post&:{&&:{&isPending&:false,&contributes&:[{&sourceColumn&:{&lastUpdated&:,&description&:&做大部分人都能读懂的数据科学笔记&,&permission&:&COLUMN_PRIVATE&,&memberId&:3093253,&contributePermission&:&COLUMN_PUBLIC&,&translatedCommentPermission&:&all&,&canManage&:true,&intro&:&做好玩的、大部分人都能读懂的数据科学笔记&,&urlToken&:&TsingJyuData&,&id&:9658,&imagePath&:&ef4c0257bd5aebe17c7d.jpeg&,&slug&:&TsingJyuData&,&applyReason&:&&,&name&:&清雨的 Data Science 笔记&,&title&:&清雨的 Data Science 笔记&,&url&:&https:\u002F\\u002FTsingJyuData&,&commentPermission&:&COLUMN_ALL_CAN_COMMENT&,&canPost&:true,&created&:,&state&:&COLUMN_NORMAL&,&followers&:2485,&avatar&:{&id&:&ef4c0257bd5aebe17c7d&,&template&:&https:\u002F\\u002F{id}_{size}.jpeg&},&activateAuthorRequested&:false,&following&:false,&imageUrl&:&https:\u002F\\u002Fef4c0257bd5aebe17c7d_l.jpeg&,&articlesCount&:15},&state&:&accepted&,&targetPost&:{&titleImage&:&https:\u002F\\u002F62f5abead8240cfbee947c_r.png&,&lastUpdated&:,&imagePath&:&62f5abead8240cfbee947c.png&,&permission&:&ARTICLE_PUBLIC&,&topics&:[],&summary&:&专栏刚刚成立，就有五十多人关注，让我这个小屌丝诚惶诚恐，仔细思索该为诸位读者大大们奉上怎样的文章。一番思索、最后决定先从K-Means写起，原因是，这个算法的\u003Cb\u003E思路好懂\u003C\u002Fb\u003E，不需要知道背后的数学背景也能玩的起来，实现简单（哪怕只要是能#include&math.h&…&,&copyPermission&:&ARTICLE_COPYABLE&,&translatedCommentPermission&:&all&,&likes&:0,&origAuthorId&:3093253,&publishedTime&:&T17:55:27+08:00&,&sourceUrl&:&&,&urlToken&:,&id&:355492,&withContent&:false,&slug&:,&bigTitleImage&:false,&title&:&K-Means聚类算法（一）：算法思路&,&url&:&\u002Fp\u002F&,&commentPermission&:&ARTICLE_ALL_CAN_COMMENT&,&snapshotUrl&:&&,&created&:,&comments&:0,&columnId&:9658,&content&:&&,&parentId&:0,&state&:&ARTICLE_PUBLISHED&,&imageUrl&:&https:\u002F\\u002F62f5abead8240cfbee947c_r.png&,&author&:{&bio&:&Machine Learning in Factory&,&isFollowing&:false,&hash&:&fb8d6e26bced&,&uid&:12,&isOrg&:false,&slug&:&qing-yu-ying&,&isFollowed&:false,&description&:&求研究机构包养，会研究数据，会写程序，会卖萌，会讲笑话，喜欢喝咖啡。&,&name&:&清雨影&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Fqing-yu-ying&,&avatar&:{&id&:&4f1e1f3f31f82e106d373aeb&,&template&:&https:\u002F\\u002F50\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false},&memberId&:3093253,&excerptTitle&:&&,&voteType&:&ARTICLE_VOTE_CLEAR&},&id&:311895}],&title&:&K-Means聚类算法（一）：算法思路&,&author&:&qing-yu-ying&,&content&:&\u003Cp\u003E专栏刚刚成立，就有五十多人关注，让我这个小屌丝诚惶诚恐，仔细思索该为诸位读者大大们奉上怎样的文章。一番思索、最后决定先从K-Means写起，原因是，这个算法的\u003Cb\u003E思路好懂\u003C\u002Fb\u003E，不需要知道背后的数学背景也能玩的起来，实现简单（哪怕只要是能#include&math.h&的C语言都可以不是很复杂的构建起来），在工作中经常会用到（用来精简和压缩数据等等）。\u003C\u002Fp\u003E\u003Cp\u003E\u003Cbr\u003E最重要的一点是：\u003Cb\u003E经常有人用错地方，不能使用欧氏距离作为相似度指标的地方也敢用！然后效果怎样我就不说了！\u003C\u002Fb\u003E\u003C\u002Fp\u003E\u003Cp\u003E\u003Cbr\u003E如果您还不理解或者不知道K-Means：\u003Cbr\u003E我希望诸位读完（一）以后，我的文章能让诸位了解K-Means的原理，适用范围和参数整定方法，掌握Matlab的能使用Matlab的kmeans工具进行实验。\u003Cbr\u003E我希望（二）以后的时候每个掌握基础编程的人都有用自己熟悉的语言开发一个基础的K-Means的能力。\u003Cbr\u003E我希望在写到（三）的时候每个掌握其变形使用方法，能优化算法，并且添加自己的思路进去（比如数据权重）。\u003Cbr\u003E我希望写完（四）以后，大家会了解它的数学背景。\u003Cbr\u003E\u003Cbr\u003E\u003Cbr\u003EPS1：虽说是“做每个人都能懂的笔记”，但是让任何人都懂觉得还是难以做到，所以昨天在创建专栏的时候最后写成了“做大部分人都能读懂的数据科学笔记”\u003Cbr\u003E\u003Cbr\u003EPS2：如果有任何不明白的地方欢迎讨论，如果您具有相应的基础知识（见下），但是觉得\u003Cb\u003E我写的您看不懂，请一定告诉我！ \u003C\u002Fb\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cbr\u003EPS3：如果觉得不错，请点个\u003Cb\u003E赞\u003C\u002Fb\u003E，你们的\u003Cb\u003E赞\u003C\u002Fb\u003E是我写这些文章和代码的动力，我还有很多细心回答的答案，如果您觉得好也请点个\u003Cb\u003E赞\u003C\u002Fb\u003E。如果写的不好……不要走，我会改的，我真的会改的TAT\u003C\u002Fp\u003E\u003Cp\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&237\& data-rawwidth=\&445\& src=\&https:\u002F\\u002Fc3827c19cfbd7985465abe184b67a996_b.png\& class=\&origin_image zh-lightbox-thumb\& width=\&445\& data-original=\&https:\u002F\\u002Fc3827c19cfbd7985465abe184b67a996_r.png\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&237\& data-rawwidth=\&445\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='445'%20height='237'&&\u002Fsvg&\& class=\&origin_image zh-lightbox-thumb lazy\& width=\&445\& data-original=\&https:\u002F\\u002Fc3827c19cfbd7985465abe184b67a996_r.png\& data-actualsrc=\&https:\u002F\\u002Fc3827c19cfbd7985465abe184b67a996_b.png\&\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E正文开始：\u003C\u002Fb\u003E\u003Cbr\u003E\u003Cbr\u003E以下是读完这一文章需要的基础知识：\u003Cbr\u003En维欧氏空间\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BR%7D%5E%7Bn%7D\& alt=\&{R}^{n}\& eeimg=\&1\&\u003E，\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BL%7D%5E%7B2%7D\& alt=\&{L}^{2}\& eeimg=\&1\&\u003E距离，Matlab编程基础知识。\u003Cbr\u003E\u003Cbr\u003E我会遵循如下的顺序介绍K-Means：\u003Cbr\u003E\u003Cb\u003E1、算法概述概览（本文）；\u003C\u002Fb\u003E\u003Cbr\u003E2、是算法思路；\u003Cbr\u003E3、代码实现和改进；\u003Cbr\u003E4、数学原理。\u003Cbr\u003E\u003Cbr\u003E需要注意的是，数学原理并不是工作的过程或者算法的实现，这个实现起来很简单的算法有着不是那么单纯的背景，PRML一书中将其归类到“混合模型与EM”一章中去。而且，就算不知道原理我们也能把这个算法撸的很爽，所以在最后才会介绍。\u003Cbr\u003E\u003Cbr\u003E我会在（二）中提供我们自己实现的K-Means的算法的源代码，但是没有接触过这一类算法的筒子们最好自己动手试一下，这算法简单，可以不依赖一些矩阵计算数学库就较为轻松的实现，我这里采用Matlab，主要是因为画图演示方便，自己实现的时候可以使用C，Python，C++，Java，VB，C#等任何支持数组，且你熟悉的语言完成。\u003Cbr\u003E\u003Cbr\u003E所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，这个方法要保证同一类的数据有相似的特征，如下图所示：\u003Cbr\u003E\u003C\u002Fp\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&2513\& data-rawwidth=\&5937\& src=\&https:\u002F\\u002F6a4378159_b.jpg\& class=\&origin_image zh-lightbox-thumb\& width=\&5937\& data-original=\&https:\u002F\\u002F6a4378159_r.jpg\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&2513\& data-rawwidth=\&5937\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='5937'%20height='2513'&&\u002Fsvg&\& class=\&origin_image zh-lightbox-thumb lazy\& width=\&5937\& data-original=\&https:\u002F\\u002F6a4378159_r.jpg\& data-actualsrc=\&https:\u002F\\u002F6a4378159_b.jpg\&\u003E\u003Cbr\u003EK-Means算法的特点是\u003Cb\u003E类别的个数是人为给定的\u003C\u002Fb\u003E，如果让机器自己去找类别的个数，我们有AP聚类算法，先不说，说了就跑题了。\u003Cbr\u003EK-Means的一个重要的假设是：\u003Cb\u003E数据之间的相似度可以使用欧氏距离度量\u003C\u002Fb\u003E，如果不能使用欧氏距离度量，要先把数据转换到能用欧氏距离度量，\u003Cb\u003E这一点很重要\u003C\u002Fb\u003E。\u003Cbr\u003E（注：\u003Cb\u003E可以使用欧氏距离度量\u003C\u002Fb\u003E的意思就是欧氏距离越小，两个数据相似度越高）\u003Cbr\u003E\u003Cbr\u003E我们来看个反例：\u003Cbr\u003E\u003Cbr\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&2625\& data-rawwidth=\&3500\& src=\&https:\u002F\\u002Fc16e7cf2d475b29e6f4a_b.jpg\& class=\&origin_image zh-lightbox-thumb\& width=\&3500\& data-original=\&https:\u002F\\u002Fc16e7cf2d475b29e6f4a_r.jpg\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&2625\& data-rawwidth=\&3500\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='3500'%20height='2625'&&\u002Fsvg&\& class=\&origin_image zh-lightbox-thumb lazy\& width=\&3500\& data-original=\&https:\u002F\\u002Fc16e7cf2d475b29e6f4a_r.jpg\& data-actualsrc=\&https:\u002F\\u002Fc16e7cf2d475b29e6f4a_b.jpg\&\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cbr\u003E图中是一个瑞士卷形状的流形，这个时候我们表示相似度应该用测地距离。什么叫测地距离呢？就是\u003Cb\u003E在曲面上\u003C\u002Fb\u003E从A点走到B点（\u003Cb\u003E不允许离开曲面\u003C\u002Fb\u003E）的最短距离。\u003Cbr\u003E但是很明显：测地距离很远的两个点有的时候会分在同一类（图中同一种颜色），说明这个时候用欧氏距离就失效了。\u003Cbr\u003E这种情况怎么处理呢？以后在讲\u003Cb\u003EISOMAP和LLE\u003C\u002Fb\u003E的时候提到如何使用KNN和最短路径算法等工具实现非欧空间到欧氏空间转化，先不说，说了就跑题了。\u003Cbr\u003E\u003Cbr\u003EK-Means算法有个很著名的解释，就是牧师-村民模型（这个故事是谁和我说的我忘了，以下是我的复述，有知道原作者的提醒我一下）：\u003Cbr\u003E\u003Cblockquote\u003E有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的居民，于是每个居民到离自己家最近的布道点去听课。\u003Cbr\u003E听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的居民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。\u003Cbr\u003E牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个居民又去了离自己最近的布道点……\u003Cbr\u003E就这样，牧师每个礼拜更新自己的位置，居民根据自己的情况选择布道点，最终稳定了下来。\u003C\u002Fblockquote\u003E\u003Cbr\u003E以上就是K-Means算法的一个过程。\u003Cbr\u003E\u003Cbr\u003E我们考虑能用欧氏距离度量的情况：\u003Cbr\u003E那么这样一个在欧氏空间中用来聚类的算法是怎么工作的呢，那就具体说一下算法：\u003Cbr\u003E首先我们得到了\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BR%7D%5E%7Bn%7D\& alt=\&{R}^{n}\& eeimg=\&1\&\u003E空间中的一堆点，这里取2维空间（方便查看），可以是酱婶的：\u003Cbr\u003E\u003Cbr\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&2725\& data-rawwidth=\&3338\& src=\&https:\u002F\\u002F21d0ddb358a30bfb11b1471_b.jpg\& class=\&origin_image zh-lightbox-thumb\& width=\&3338\& data-original=\&https:\u002F\\u002F21d0ddb358a30bfb11b1471_r.jpg\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&2725\& data-rawwidth=\&3338\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='3338'%20height='2725'&&\u002Fsvg&\& class=\&origin_image zh-lightbox-thumb lazy\& width=\&3338\& data-original=\&https:\u002F\\u002F21d0ddb358a30bfb11b1471_r.jpg\& data-actualsrc=\&https:\u002F\\u002F21d0ddb358a30bfb11b1471_b.jpg\&\u003E\u003Cbr\u003E随机生成k个聚类中心点（真心随机生成，因为无所谓~但是尽量不要生成在一起）：\u003Cbr\u003E而后分别计算每一个数据点对这些中心的距离，把距离最短的那个当成自己的类别，或者中心点。\u003Cbr\u003E就好比你去买菜，家门口有菜场的，我不会穿个城到另外一条街去买，对吧~\u003Cbr\u003E\u003Cbr\u003E这样每个点都会有一个中心点了，这是随机生成的中心点的结果，可以看到聚类的并不准确：\u003Cbr\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&2625\& data-rawwidth=\&3500\& src=\&https:\u002F\\u002Fb287a4a561_b.jpg\& class=\&origin_image zh-lightbox-thumb\& width=\&3500\& data-original=\&https:\u002F\\u002Fb287a4a561_r.jpg\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&2625\& data-rawwidth=\&3500\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='3500'%20height='2625'&&\u002Fsvg&\& class=\&origin_image zh-lightbox-thumb lazy\& width=\&3500\& data-original=\&https:\u002F\\u002Fb287a4a561_r.jpg\& data-actualsrc=\&https:\u002F\\u002Fb287a4a561_b.jpg\&\u003E\u003Cbr\u003E\u003Cbr\u003E这个时候，身为中心点，觉得自己不能离群众这么遥远，他要到群众中去，这样可以收复那些绿颜色的点，像这样：\u003Cbr\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&314\& data-rawwidth=\&341\& src=\&https:\u002F\\u002Fefb4aa42d827e779c326f4_b.png\& class=\&content_image\& width=\&341\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&314\& data-rawwidth=\&341\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='341'%20height='314'&&\u002Fsvg&\& class=\&content_image lazy\& width=\&341\& data-actualsrc=\&https:\u002F\\u002Fefb4aa42d827e779c326f4_b.png\&\u003E\u003Cbr\u003E那么他怎么知道移动到哪里呢？\u003Cbr\u003E当然是往群众的中心移动啦！所有的属于蓝色类的点的中心，或者说坐标的平均值，就是蓝色小圆圈要去的地方，于是他收获了更多的群众：\u003Cbr\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&303\& data-rawwidth=\&394\& src=\&https:\u002F\\u002Ff9c2648e90cce06c60725f_b.png\& class=\&content_image\& width=\&394\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&303\& data-rawwidth=\&394\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='394'%20height='303'&&\u002Fsvg&\& class=\&content_image lazy\& width=\&394\& data-actualsrc=\&https:\u002F\\u002Ff9c2648e90cce06c60725f_b.png\&\u003E\u003Cbr\u003E\u003Cbr\u003E绿色的点也往群众的中心移动，但是却少了一批数据跟随他，不过没关系，反正这些变蓝的点和现在自己所在的绿色大本营的格调（欧氏坐标）格格不入（距离太远）。\u003Cbr\u003E于是仅仅2步，情况就成了这样：\u003Cbr\u003E\u003Cnoscript\u003E\u003Cimg data-rawheight=\&2625\& data-rawwidth=\&3500\& src=\&https:\u002F\\u002Fe45d3abc380ec_b.jpg\& class=\&origin_image zh-lightbox-thumb\& width=\&3500\& data-original=\&https:\u002F\\u002Fe45d3abc380ec_r.jpg\&\u003E\u003C\u002Fnoscript\u003E\u003Cimg data-rawheight=\&2625\& data-rawwidth=\&3500\& src=\&data:image\u002Fsvg+utf8,&svg%20xmlns='http:\u002F\u002Fwww.w3.org\u002FFsvg'%20width='3500'%20height='2625'&&\u002Fsvg&\& class=\&origin_image zh-lightbox-thumb lazy\& width=\&3500\& data-original=\&https:\u002F\\u002Fe45d3abc380ec_r.jpg\& data-actualsrc=\&https:\u002F\\u002Fe45d3abc380ec_b.jpg\&\u003E\u003Cbr\u003E蓝色的中心点又试着微调了几次，绿色和红色的也一样，微调之后发现自己不需要动了，自己的群众基础已经稳定了，乱动可能脱离群众，众叛亲离，所以这个时候算法就收敛了。\u003Cbr\u003E\u003Cbr\u003E如果用伪代码描述，那么过程是这样的：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&k\&\u003Efunction\u003C\u002Fspan\u003E\u003Cspan class=\&w\&\u003E \u003C\u002Fspan\u003E\u003Cspan class=\&nf\&\u003EK-Means\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E输入数据，中心点个数K\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\u003Cspan class=\&w\&\u003E\u003C\u002Fspan\u003E\n\u003Cspan class=\&w\&\u003E
\u003C\u002Fspan\u003E获取输入数据的维度\u003Cspan class=\&n\&\u003EDim\u003C\u002Fspan\u003E和个数\u003Cspan class=\&n\&\u003EN\u003C\u002Fspan\u003E\n
随机生成\u003Cspan class=\&n\&\u003EK\u003C\u002Fspan\u003E个\u003Cspan class=\&n\&\u003EDim\u003C\u002Fspan\u003E维的点\n
\u003Cspan class=\&k\&\u003Ewhile\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E算法未收敛\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\n
对\u003Cspan class=\&n\&\u003EN\u003C\u002Fspan\u003E个点：计算每个点属于哪一类。\n
对于\u003Cspan class=\&n\&\u003EK\u003C\u002Fspan\u003E个中心点：\n
\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E，找出所有属于自己这一类的所有数据点\n
\u003Cspan class=\&mi\&\u003E2\u003C\u002Fspan\u003E，把自己的坐标修改为这些数据点的中心点坐标\n
\u003Cspan class=\&k\&\u003Eend\u003C\u002Fspan\u003E\n
输出结果：\n\u003Cspan class=\&k\&\u003Eend\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cp\u003E\u003Cbr\u003E很多人已经急着想试一下了，那么，在正式编程开始之前，我们不妨先使用Matlab提供的内置的K-Means感受一下（代码在GitHub上自己下载，你的Matlab要支持K-Means哦，我的版本是r2015a）\u003Cbr\u003E\u003Ca href=\&http:\u002F\\u002F?target=https%3A\\u002FTsingJyujing\u002FDataScienceNote\u002Fblob\u002Fmaster\u002FK-Means%2520Cluster\u002FTryKMeans.m\& class=\& wrap external\& target=\&_blank\& rel=\&nofollow noreferrer\&\u003EDataScienceNote\u002FTryKMeans.m at master · TsingJyujing\u002FDataScienceNote · GitHub\u003Ci class=\&icon-external\&\u003E\u003C\u002Fi\u003E\u003C\u002Fa\u003E\u003C\u002Fp\u003E\u003Cp\u003E实际编程的时候，我们会遇到如下问题：\u003Cbr\u003E1，怎么初始化才能更快收敛不震荡？\u003Cbr\u003E2，如果有一中心点初始化的时候离得远了，或者被其它中心点包围了，导致每个数据点都不肯找他怎么办？\u003Cbr\u003E3，如何评价算法是否收敛？ \u003Cbr\u003E4，算法不收敛怎么办？\u003Cbr\u003E5，能不能给每个点设置权重？\u003Cbr\u003E……\u003Cbr\u003E\u003Cbr\u003E还有这些奇奇怪怪的优化问题：\u003Cbr\u003E1，如何高效的使用Matlab计算欧氏距离？\u003Cbr\u003E2，如何快速计算出每一个点属于哪一类？\u003Cbr\u003E3，如何保存和输出结果？怎么设计数据结构？\u003Cbr\u003E……\u003Cbr\u003E\u003Cbr\u003E这些在\u003Ci\u003EK-Means聚类算法的思路、实现、改进及原理（二）：算法的实现\u003C\u002Fi\u003E里详细讨论。\u003C\u002Fp\u003E&,&updated&:new Date(&T09:55:27.000Z&),&canComment&:false,&commentPermission&:&anyone&,&commentCount&:22,&collapsedCount&:0,&likeCount&:138,&state&:&published&,&isLiked&:false,&slug&:&&,&isTitleImageFullScreen&:false,&rating&:&none&,&titleImage&:&https:\u002F\\u002F62f5abead8240cfbee947c_r.png&,&links&:{&comments&:&\u002Fapi\u002Fposts\u002F2Fcomments&},&reviewers&:[],&topics&:[{&url&:&https:\u002F\\u002Ftopic\u002F&,&id&:&&,&name&:&机器学习&},{&url&:&https:\u002F\\u002Ftopic\u002F&,&id&:&&,&name&:&聚类算法&}],&adminClosedComment&:false,&titleImageSize&:{&width&:830,&height&:403},&href&:&\u002Fapi\u002Fposts\u002F&,&excerptTitle&:&&,&column&:{&slug&:&TsingJyuData&,&name&:&清雨的 Data Science 笔记&},&tipjarState&:&inactivated&,&annotationAction&:[],&sourceUrl&:&&,&pageCommentsCount&:22,&hasPublishingDraft&:false,&snapshotUrl&:&&,&publishedTime&:&T17:55:27+08:00&,&url&:&\u002Fp\u002F&,&lastestLikers&:[{&bio&:&&,&isFollowing&:false,&hash&:&84c59a46002fdd3805f5&,&uid&:420400,&isOrg&:false,&slug&:&lina-28-90&,&isFollowed&:false,&description&:&&,&name&:&Lina&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Flina-28-90&,&avatar&:{&id&:&da8e974dc&,&template&:&https:\u002F\\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false},{&bio&:&BJTU通信小硕&,&isFollowing&:false,&hash&:&deef9d7a5ffd6a&,&uid&:790500,&isOrg&:false,&slug&:&xiang-xin-zi-ji-49&,&isFollowed&:false,&description&:&&,&name&:&相信自己&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Fxiang-xin-zi-ji-49&,&avatar&:{&id&:&d779c4f290a25a722b0ed0&,&template&:&https:\u002F\\u002F50\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false},{&bio&:&北京科技大学 控制科学与工程&,&isFollowing&:false,&hash&:&6f1390cabacc9&,&uid&:155400,&isOrg&:false,&slug&:&du-hai-peng-63&,&isFollowed&:false,&description&:&&,&name&:&杜海鹏&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Fdu-hai-peng-63&,&avatar&:{&id&:&v2-ff1e90ea49fc3781ef29&,&template&:&https:\u002F\\u002F50\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false},{&bio&:&IT咨询&,&isFollowing&:false,&hash&:&be004b37d5ec1ecd55ee50c&,&uid&:740600,&isOrg&:false,&slug&:&joshua-50-71&,&isFollowed&:false,&description&:&&,&name&:&Joshua&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Fjoshua-50-71&,&avatar&:{&id&:&da8e974dc&,&template&:&https:\u002F\\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false},{&bio&:null,&isFollowing&:false,&hash&:&dff426ee46874d7caba44&,&uid&:60,&isOrg&:false,&slug&:&sun-xiu-26&,&isFollowed&:false,&description&:&&,&name&:&孙秀&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Fsun-xiu-26&,&avatar&:{&id&:&da8e974dc&,&template&:&https:\u002F\\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false}],&summary&:&\u003Cimg data-rawheight=\&2513\& data-rawwidth=\&5937\& src=\&http:\u002F\\u002F6ax112.jpg\& class=\&origin_image inline-img zh-lightbox-thumb\& data-original=\&http:\u002F\\u002F6a4378159_r.jpg\&\u003E专栏刚刚成立，就有五十多人关注，让我这个小屌丝诚惶诚恐，仔细思索该为诸位读者大大们奉上怎样的文章。一番思索、最后决定先从K-Means写起，原因是，这个算法的\u003Cb\u003E思路好懂\u003C\u002Fb\u003E，不需要知道背后的数学背景也能玩的起来，实现简单（哪怕只要是能#include&math.h&…&,&reviewingCommentsCount&:0,&meta&:{&previous&:{&isTitleImageFullScreen&:false,&rating&:&none&,&titleImage&:&https:\u002F\\u002F50\u002F234e2daf01fe5efc6bc36c40c096b17c_xl.jpg&,&links&:{&comments&:&\u002Fapi\u002Fposts\u002F2Fcomments&},&topics&:[],&adminClosedComment&:false,&href&:&\u002Fapi\u002Fposts\u002F&,&excerptTitle&:&&,&author&:{&bio&:&Machine Learning in Factory&,&isFollowing&:false,&hash&:&fb8d6e26bced&,&uid&:12,&isOrg&:false,&slug&:&qing-yu-ying&,&isFollowed&:false,&description&:&求研究机构包养，会研究数据，会写程序，会卖萌，会讲笑话，喜欢喝咖啡。&,&name&:&清雨影&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Fqing-yu-ying&,&avatar&:{&id&:&4f1e1f3f31f82e106d373aeb&,&template&:&https:\u002F\\u002F50\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false},&column&:{&slug&:&TsingJyuData&,&name&:&清雨的 Data Science 笔记&},&content&:&\u003Cp\u003E学习就没有容易的事情，入个门或许很简单——那几乎不能算作学习。就好像大多数人的日语停留在五十音图，英语停留在Say Hello和How much，编程停留在Hello World，更有甚者会且只会用数十种语言编写Hello World……\u003C\u002Fp\u003E\u003Cp\u003E真正的学习，就是要沉下心，看自己看不懂的书看到懂，学自己不会的知识学到会，苦思冥想想不通的事到大彻大悟。其中苦乐，自有人知道。\u003C\u002Fp\u003E\u003Cp\u003E数据科学，看上去很美好，很高大上，万千数据流转在CPU，GPU之间，宛若一曲和谐的交响乐。但是实际工作的时候很多时候会做些穷尽人精力的事情，比如看着上面的已经聚类谱图再人肉聚类。 \u003Cbr\u003E\u003C\u002Fp\u003E\u003Cp\u003E我最近在看自动控制原理（胡寿松版），大多数人都能扯上一些，毕竟不少人本科都学过，但是，谁能回答如下问题：\u003C\u002Fp\u003E\u003Cp\u003E为什么线性系统传递函数的极点决定了系统的稳定性？\u003C\u002Fp\u003E\u003Cp\u003E为什么Laplace反变换前面有个\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cfrac%7B1%7D%7B2%5Cpi+j%7D+\& alt=\&\\frac{1}{2\\pi j} \& eeimg=\&1\&\u003E，那个虚数\u003Cimg src=\&http:\u002F\\u002Fequation?tex=j\& alt=\&j\& eeimg=\&1\&\u003E是怎么回事？\u003C\u002Fp\u003E\u003Cp\u003E梅森公式的原理是什么？如何证明？\u003C\u002Fp\u003E\u003Cp\u003E事实上，以上三个问题笔者也只能回答两个半，一旦学到学不动了，想要开始不求理解直接死记硬背搞定问题的时候，往往是功力不够。\u003C\u002Fp\u003E\u003Cp\u003E在这篇专栏中，我将分享我的关于数据科学的各种笔记，其中包括\u003Cb\u003E算法原理、工程应用、编程技巧、一些数学原理\u003C\u002Fb\u003E等等。每一篇力求从最深的地方理解问题，理解每一个符号，直到一切清清楚楚如明镜照人。\u003C\u002Fp\u003E\u003Cp\u003E专栏的文章发表基本没有任何顺序，想到就发。如果有任何原理上的错漏，包括错别字，欢迎指出~\u003C\u002Fp\u003E\u003Cbr\u003E\u003Cp\u003E\u003Cb\u003E吾生也有涯，而知也无涯，以有涯的生命投身无涯的学海，爽！\u003C\u002Fb\u003E\u003C\u002Fp\u003E\u003Cp\u003E祝各位学的开心。 \u003Cbr\u003E\u003C\u002Fp\u003E\u003Cp\u003E（PS：如果有人知道梅森公式的证明的请告诉我，谢谢~，~） \u003C\u002Fp\u003E&,&state&:&published&,&sourceUrl&:&&,&pageCommentsCount&:0,&canComment&:false,&snapshotUrl&:&&,&slug&:,&publishedTime&:&T22:07:15+08:00&,&url&:&\u002Fp\u002F&,&title&:&写在前面——学习之苦&,&summary&:&学习就没有容易的事情，入个门或许很简单——那几乎不能算作学习。就好像大多数人的日语停留在五十音图，英语停留在Say Hello和How much，编程停留在Hello World，更有甚者会且只会用数十种语言编写Hello World……真正的学习，就是要沉下心，看自己看不懂…&,&reviewingCommentsCount&:0,&meta&:{&previous&:null,&next&:null},&commentPermission&:&anyone&,&commentsCount&:15,&likesCount&:54},&next&:{&isTitleImageFullScreen&:false,&rating&:&none&,&titleImage&:&https:\u002F\\u002F50\u002Fdfd4f4ce0b855b76e8f04c43fbc811a8_xl.jpg&,&links&:{&comments&:&\u002Fapi\u002Fposts\u002F2Fcomments&},&topics&:[{&url&:&https:\u002F\\u002Ftopic\u002F&,&id&:&&,&name&:&机器学习&},{&url&:&https:\u002F\\u002Ftopic\u002F&,&id&:&&,&name&:&聚类算法&},{&url&:&https:\u002F\\u002Ftopic\u002F&,&id&:&&,&name&:&图片压缩&}],&adminClosedComment&:false,&href&:&\u002Fapi\u002Fposts\u002F&,&excerptTitle&:&&,&author&:{&bio&:&Machine Learning in Factory&,&isFollowing&:false,&hash&:&fb8d6e26bced&,&uid&:12,&isOrg&:false,&slug&:&qing-yu-ying&,&isFollowed&:false,&description&:&求研究机构包养，会研究数据，会写程序，会卖萌，会讲笑话，喜欢喝咖啡。&,&name&:&清雨影&,&profileUrl&:&https:\u002F\\u002Fpeople\u002Fqing-yu-ying&,&avatar&:{&id&:&4f1e1f3f31f82e106d373aeb&,&template&:&https:\u002F\\u002F50\u002F{id}_{size}.jpg&},&isOrgWhiteList&:false,&isBanned&:false},&column&:{&slug&:&TsingJyuData&,&name&:&清雨的 Data Science 笔记&},&content&:&（最近在车间干活的时候把手砸伤了，所以打字还是有点不便，大家原谅我更新的慢，加上赞比较少，心情比较低落TAT）\u003Cbr\u003E\u003Cbr\u003E首先介绍一下题图，这个是个小萝莉的照片（如下），每一个点都可以视作是一个三维向量（点？）（RGB三通道图片），那么，使用K-Means算法对这些点进行聚类，我们就很容易得到几个中心点和几类，把同一类的数据点（像素点）用中心点表示就可以得到压缩后的图片，以上分别是把3通道×每通道8bit=24bit的像素点压缩为1bit，2bit，3bit和4bit的效果，可以看到，虽然信息损失了6倍，但是对画质的影响没有想象的大。\u003Cbr\u003E\u003Cimg data-rawheight=\&377\& data-rawwidth=\&472\& src=\&http:\u002F\\u002F4c167e290a72c299e2c5_b.jpg\& class=\&origin_image zh-lightbox-thumb\& width=\&472\& data-original=\&http:\u002F\\u002F4c167e290a72c299e2c5_r.jpg\&\u003E\u003Cp\u003E忘了说了，我把图像压缩的代码传上去了，但是图片没办法传送，因为本人的GitHub抽风了（准确的说是网络抽风）\u003C\u002Fp\u003E\u003Cp\u003E\u003Ca href=\&http:\u002F\\u002F?target=https%3A\\u002FTsingJyujing\u002FDataScienceNote\u002Fblob\u002Fmaster\u002FK-Means%2520Cluster\u002FKMeans_Img.m\& class=\& wrap external\& target=\&_blank\& rel=\&nofollow noreferrer\&\u003EDataScienceNote\u002FKMeans_Img.m at master · TsingJyujing\u002FDataScienceNote · GitHub\u003Ci class=\&icon-external\&\u003E\u003C\u002Fi\u003E\u003C\u002Fa\u003E\u003Cbr\u003E\u003C\u002Fp\u003E\u003Cp\u003E请准备好loli.jpg文件，并且配合k_means.m一起食用~\u003C\u002Fp\u003E\u003Cp\u003Ek_means.m代码放在了GitHub上，大家自己下载着玩:P\u003Cbr\u003E\u003Ca class=\& wrap external\& href=\&http:\u002F\\u002F?target=https%3A\\u002FTsingJyujing\u002FDataScienceNote\u002Fblob\u002Fmaster\u002FK-Means%2520Cluster\u002Fk_means.m\& target=\&_blank\& rel=\&nofollow noreferrer\&\u003EDataScienceNote\u002Fk_means.m at master · TsingJyujing\u002FDataScienceNote · GitHub\u003Ci class=\&icon-external\&\u003E\u003C\u002Fi\u003E\u003C\u002Fa\u003E\u003Cbr\u003E\u003C\u002Fp\u003E\u003Cp\u003E其次修正一下上次的说法：并不只是欧氏空间可以用这个方法，只要是对于提供了以下几种算子且满足以下性质的空间都能用：\u003Cbr\u003E首先有个计算任意两点距离（或者叫不相似度）的算符记作\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%3C%5Cvec%7Ba%7D%2C%5Cvec%7Bb%7D%3E\& alt=\&&\\vec{a},\\vec{b}&\& eeimg=\&1\&\u003E\u003Cbr\u003E且有交换性：\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%3C%5Cvec%7Ba%7D%2C%5Cvec%7Bb%7D%3E%3D%3C%5Cvec%7Bb%7D%2C%5Cvec%7Ba%7D%3E\& alt=\&&\\vec{a},\\vec{b}&=&\\vec{b},\\vec{a}&\& eeimg=\&1\&\u003E\u003Cbr\u003E其次有求任意一堆点的平均值的算法：\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cvec%7B%5Cmu%7D%3DMean%28%5Cvec%7B%7Ba%7D_%7B1%7D%7D%2C...%2C+%5Cvec%7B%7Ba%7D_%7Bn%7D%7D%29\& alt=\&\\vec{\\mu}=Mean(\\vec{{a}_{1}},..., \\vec{{a}_{n}})\& eeimg=\&1\&\u003E\u003Cbr\u003E求出以后使得：\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%7B%28%5Cvec%7B%5Cmu%7D-%5Cvec%7B%7Ba%7D_%7Bi%7D%7D%29%7D%5E%7B2%7D\& alt=\&\\sum_{i=1}^{n}{(\\vec{\\mu}-\\vec{{a}_{i}})}^{2}\& eeimg=\&1\&\u003E\u003Cbr\u003E就可以了。\u003Cbr\u003E如果这一段有错误，求指出哈~\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E这一篇依旧不会涉及数学原理\u003C\u002Fb\u003E，我在纠结中，因为要从头说清楚EM算法是一件很费工夫的事情：首先是含有隐变量(Latent Variables)的模型去估计实际的数据，然后从概率论出发，到极大似然估计确定参数和E（Expectation）步和M（Maximization）步。以上是我清楚的，还有我到现在有云里雾里的收敛性证明。\u003Cbr\u003E并不是说费工夫就不写了，逃了，而是用最少的公式和步骤说清楚和K-Means有关的部分。\u003Cbr\u003E\u003Cbr\u003E下一章会比较高能，说是高能，其实也就是求个偏导数，极大似然估计啥的而已……而已……\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003EPart Ⅰ
编程实战的时候那些坑：\u003C\u002Fb\u003E\u003Cbr\u003E实战的时候是会遇到很多坑的，首先说第一个：\u003Cbr\u003E\u003Cb\u003E一、如何初始化中心点\u003C\u002Fb\u003E\u003Cbr\u003E事实上，初始化的不好，是会震荡的（当然，有了后面的解决震荡的办法要好得多）！\u003Cbr\u003E初始化的时候，不妨先估计一下数据的中心在哪里，数据的尺度（叫Scale合适么）有多大，然后在生成数据的时候以中心点为中心，以尺度为因子乘以服从标准正态分布的数据。\u003Cbr\u003E大致就是这样的一段代码：\u003Cbr\u003E\u003C\u002Fp\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Egroup_center\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Emean\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edata_set\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n\u003Cspan class=\&n\&\u003Egroup_range\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Erange\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edata_set\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n\u003Cspan class=\&n\&\u003Ecenters\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Erandn\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EK\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edim\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.*\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Erepmat\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Egroup_range\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EK\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.\u002F\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E3\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E+\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Erepmat\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Egroup_center\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EK\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E));\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E至于为什么要除以3，是因为这里\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7B%5Csigma%7D%3D1\& alt=\&{\\sigma}=1\& eeimg=\&1\&\u003E，一般数据不会越过\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%C2%B13%7B%5Csigma%7D\& alt=\&±3{\\sigma}\& eeimg=\&1\&\u003E。\u003Cbr\u003E这里根据每一个维度分别做了Scale，使得其能充填在数据中心点附近，然而又不太远。\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E二、如何计算没有“争取”到任意一点的中心点？\u003C\u002Fb\u003E\u003Cbr\u003E有的时候某些中心点太强势，直接把点抢没了：主要出现在点少类多的情况下。\u003Cbr\u003E这个时候，就需要忽略这些中心点。但是中心点不调整也不好，有可能就在那个地方注定孤独一生了。\u003Cbr\u003E这个时候我们把这个点初始化到中心点附近的地方：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecenters\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,:)\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Erandn\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edim\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.*\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Egroup_range\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.\u002F\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E3\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E+\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Egroup_center\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E让他重新来过。\u003Cbr\u003E这一点在有权重参与计算的时候特别重要么，因为没有争取到点，所以这个时候权重会是0，就出现除零错误了。\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E三、我怎么知道有没有收敛呢？\u003C\u002Fb\u003E\u003Cbr\u003E这个在书中已经说了，使用代价函数：\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cwidetilde%7BJ%7D%3D%5Csum_%7Bi%3D1%7D%5E%7BC%7D%7B%5Csum_%7Bj%3D1%7D%5E%7BN%7D%7B%7Br%7D_%7Bij%7D%5Ctimes%7B%5Cnu%28%7Bx%7D_%7Bj%7D%2C%7B%5Cmu%7D_%7Bi%7D%29%7D%7D%7D\& alt=\&\\widetilde{J}=\\sum_{i=1}^{C}{\\sum_{j=1}^{N}{{r}_{ij}\\times{\\nu({x}_{j},{\\mu}_{i})}}}\& eeimg=\&1\&\u003E\u003Cbr\u003E\u003Cp\u003E其中：\u003C\u002Fp\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cnu%28%7Bx%7D_%7Bj%7D%2C%7B%5Cmu%7D_%7Bi%7D%29%3D%7B%7C%7C%7Bx%7D_%7Bj%7D-%7B%5Cmu%7D_%7Bi%7D%7C%7C%7D%5E%7B2%7D\& alt=\&\\nu({x}_{j},{\\mu}_{i})={||{x}_{j}-{\\mu}_{i}||}^{2}\& eeimg=\&1\&\u003E\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7Br%7D_%7Bij%7D\& alt=\&{r}_{ij}\& eeimg=\&1\&\u003E的解释：如果第j个数据点属于第i类，那就记作1，否则记作0的一个\u003Cimg src=\&http:\u002F\\u002Fequation?tex=N+%5Ctimes+C\& alt=\&N \\times C\& eeimg=\&1\&\u003E 大小的矩阵。代价函数的差分值小于一定数值的时候（N次越不过最小值点）即可认为收敛了。\u003Cbr\u003E\u003Cbr\u003E\u003Ci\u003E（以下一段算是题外废话）\u003C\u002Fi\u003E\u003Cbr\u003E这里需要补充另外两种评价聚类算法的方法：F-Measure和信息熵\u003Cbr\u003E但是使用这两个代价函数以后就不能用原来提出的迭代算法了，因为原来的EM算法是针对上面的\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cwidetilde%7BJ%7D\& alt=\&\\widetilde{J}\& eeimg=\&1\&\u003E那个代价函数的。\u003Cbr\u003E关于这两个代价函数和如何推导会在下一篇讲清楚。\u003Cbr\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E四、代价函数不收敛，怎么破？\u003C\u002Fb\u003E\u003Cbr\u003E其实有一些论文和偏理论的书讲了代价函数的收敛性和初值敏感性的证明，然而不管是本文还是下一篇文章我都不准备讨论这些证明，主要原因是：我！不！太！懂！……（逃\u003Cbr\u003E\u003Cbr\u003E\u003Cu\u003E（如果有希望知道这些但是不知道哪里找资料的大犇，我推荐你《统计学习方法》中关于EM算法的收敛性讨论的部分，只不过该书没有说K-Means算法，直说了硬币游戏模型和Gaussian混合模型，真正找EM算法在K-Means上的推导在\u003Ci\u003EPattern Recognition and Machine Learning\u003C\u002Fi\u003E上，不过没有求偏导和导出求中心点的详细过程，直说了句we can easily solve，翻译过来就是“易证”、“易知”、“易求”或者“我们把这个简单有趣的证明留给读者”之类的鸟话）\u003C\u002Fu\u003E\u003Cbr\u003E\u003Cbr\u003E首先说一下什么时候容易发生震荡：在数据点个数比较少而且比较稀疏的时候容易发生这种事情，发生的原因大约有两种常见的：\u003Cbr\u003E1、陷入某个环里，然后开始震荡，你就会看见某个中心点绕了一圈一圈的……低频振荡。\u003Cbr\u003E2、两个点交换来交换去，每次交换不改变J的值就收敛了，如果交换以后不幸影响了其它的点，就出现了高频振荡（多一句嘴，为什么称之为高频呢？因为达到了奈奎斯特采样频率最大值啊）。\u003Cbr\u003E这个时候给出一种简单的解决方案：阻尼。\u003Cbr\u003E简而言之，就是更新自己位置的时候考虑一下原来的位置，一般阻尼比（在0~1之间取值）决定收敛速度，收敛的慢了也就不容易震荡，也就越容易陷入局部极小值，也就是说，不震荡的情况下我们应该把阻尼比尽可能取小一点\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cvec%7B%7BC%7D%7D%5E%7Bupd%7D%3D%5Cvec%7B%7BC%7D%7D%5E%7Bnew%7D%5Ctimes%281-%5Cxi%29%2B%5Cvec%7B%7BC%7D%7D%5E%7Bold%7D%5Ctimes%5Cxi\& alt=\&\\vec{{C}}^{upd}=\\vec{{C}}^{new}\\times(1-\\xi)+\\vec{{C}}^{old}\\times\\xi\& eeimg=\&1\&\u003E\u003Cbr\u003E\u003Cp\u003E其中：\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cvec%7B%7BC%7D%7D%5E%7Bupd%7D\& alt=\&\\vec{{C}}^{upd}\& eeimg=\&1\&\u003E是最后中心点的取值，\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cvec%7B%7BC%7D%7D%5E%7Bnew%7D\& alt=\&\\vec{{C}}^{new}\& eeimg=\&1\&\u003E是当前集合的中心点，\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cvec%7B%7BC%7D%7D%5E%7Bold%7D\& alt=\&\\vec{{C}}^{old}\& eeimg=\&1\&\u003E是原来的中心点坐标。\u003C\u002Fp\u003E\u003Cbr\u003E代码中的体现就是：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-text\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003Edumper = 0.1;\n...\ncenters = (1-dumper).*centers + dumper.*lst_\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E五、如何给某些点设置权重\u003C\u002Fb\u003E\u003Cbr\u003E首先明确一个问题：为什么要设置权重？\u003Cbr\u003E设置权重一般发生在两种情况下：\u003Cbr\u003E1，数据集中有大量的重复点，而且数据量比较大计算非常的烧CPU。\u003Cbr\u003E2，数据本身有轻重缓急之分，例如只买一两条裤子还扭扭捏捏挑挑选选的我这样的小屌丝客户和乔布斯那种为了自己喜欢的黑色套头衫让停产的生产线再运行的情怀客户的权重肯定是不一样的（请一口气读完）。\u003Cbr\u003E可以看看第一篇文章的标题图（封面）就是带权聚类的一个结果：\u003Cbr\u003E\u003Cimg data-rawheight=\&3269\& data-rawwidth=\&7175\& src=\&http:\u002F\\u002F9e5a4d8bc614f3ef8d739ebe7a1f9e35_b.jpg\& class=\&origin_image zh-lightbox-thumb\& width=\&7175\& data-original=\&http:\u002F\\u002F9e5a4d8bc614f3ef8d739ebe7a1f9e35_r.jpg\&\u003E\u003Cbr\u003E那么问题来了：\u003Cb\u003E\u003Cu\u003E如何设置权重\u003C\u002Fu\u003E\u003C\u002Fb\u003E？\u003Cbr\u003E设置权重其实不困难，首先要明确代价函数是什么：是点距离的和啊！那么更新策略是什么？是找中心点啊！那么现在我们就需要引入加权平均值的算法：\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BMean%7D_%7Bweight%7D%28%5C%7B%5Cvec%7B%7Bv%7D_%7Bi%7D%7D%5C%7D%2C%5Cvec%7Bw%7D%29%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%7B%7Bw%7D_%7Bi%7D%5Ctimes%5Cvec%7B%7Bv%7D_%7Bi%7D%7D%7D\& alt=\&{Mean}_{weight}(\\{\\vec{{v}_{i}}\\},\\vec{w})=\\sum_{i=1}^{n}{{w}_{i}\\times\\vec{{v}_{i}}}\& eeimg=\&1\&\u003E\u003Cbr\u003E每次移到这个地方就可以了，其中\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cvec%7Bw%7D\& alt=\&\\vec{w}\& eeimg=\&1\&\u003E满足\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BL%7D%5E%7B1%7D\& alt=\&{L}^{1}\& eeimg=\&1\&\u003E范数是1，这是文艺说法。\u003Cbr\u003E普通说法就是\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Csum%7B%7Bw%7D_%7Bi%7D%7D%3D1\& alt=\&\\sum{{w}_{i}}=1\& eeimg=\&1\&\u003E\u003Cbr\u003E如果不满足也懒得归一化可以：\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BMean%7D_%7Bweight%7D%28%5C%7B%5Cvec%7B%7Bv%7D_%7Bi%7D%7D%5C%7D%2C%5Cvec%7Bw%7D%29%3D%5Cfrac%7B1%7D%7B%5Csum%7B%7Bw%7D_%7Bi%7D%7D%7D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%7B%7Bw%7D_%7Bi%7D%5Ctimes%5Cvec%7B%7Bv%7D_%7Bi%7D%7D%7D\& alt=\&{Mean}_{weight}(\\{\\vec{{v}_{i}}\\},\\vec{w})=\\frac{1}{\\sum{{w}_{i}}}\\sum_{i=1}^{n}{{w}_{i}\\times\\vec{{v}_{i}}}\& eeimg=\&1\&\u003E\u003Cbr\u003E这就是我程序中使用的公式。\u003Cbr\u003E具体在代码中的表现就是：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecenters\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,:)\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Esum\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edata_set\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_idx\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,:)\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.*\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Erepmat\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Eweight\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_idx\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E),\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edim\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E))\u003C\u002Fspan\u003E\u003Cspan class=\&c\&\u003E...\u003C\u002Fspan\u003E\n
\u003Cspan class=\&o\&\u003E.\u002F\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Esum\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Eweight\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_idx\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E));\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E\u003Cb\u003EPart Ⅱ
\u003C\u002Fb\u003EMatlab编程技巧：\u003C\u002Fb\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E一、如何愉快的求取\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BL%7D%5E%0A%7B2%7D\& alt=\&{L}^\n{2}\& eeimg=\&1\&\u003E范数\u002F距离？\u003C\u002Fb\u003E\u003Cbr\u003E首先，我们一起确认一下\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BL%7D%5E%7B2%7D\& alt=\&{L}^{2}\& eeimg=\&1\&\u003E范数的公式：\u003Cbr\u003E对于任意一个向量：\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%5Cvec%7Bv%7D%3D%28%7Bv%7D_%7B1%7D%2C...%2C%7Bv%7D_%7Bd%7D%29+\& alt=\&\\vec{v}=({v}_{1},...,{v}_{d}) \& eeimg=\&1\&\u003E\u003Cbr\u003E其\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BL%7D%5E%7B2%7D\& alt=\&{L}^{2}\& eeimg=\&1\&\u003E范数是：\u003Cbr\u003E\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7B%5Cleft%7C+x+%5Cright%7C%7D+%5E%7B2%7D%3D+%5Csum_%7Bi%3D1%7D%5E%7BD%7D%7B%7B%7Bv%7D_%7Bi%7D%7D%5E%7B2%7D%7D\& alt=\&{\\left| x \\right|} ^{2}= \\sum_{i=1}^{D}{{{v}_{i}}^{2}}\& eeimg=\&1\&\u003E\u003Cbr\u003E随后，我们确认一下求范数的几个步骤：\u003Cbr\u003E对于已知的一点pnt和行向量组data_set，首先确认行向量组的向量个数：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E[\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EN\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E~\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E]=\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Esize\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edata_set\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E随后用repmat把pnt复制N遍，变成和data_set同样大小的一个矩阵。\u003Cbr\u003E然后那么一减啊，再求个平方，就可以开始求和了（就是那个Σ），但是是横向拍扁求和，因为我们是行向量啊。\u003Cbr\u003E所以给sum函数第二个参数：2\u003Cbr\u003E最后开平方即可：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edist_list\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Esqrt\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Esum\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E((\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edata_set\u003C\u002Fspan\u003E \u003Cspan class=\&o\&\u003E-\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Erepmat\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Epnt\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EN\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E))\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.^\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E2\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E2\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E))\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E二、如何愉快的计算某一个点属于哪一类：\u003C\u002Fb\u003E\u003Cbr\u003E我们刚才求出了很多的列（dist_list ），这些就是到每个点的距离的列表，这里一共有k个点，所以做成一个k*N的矩阵：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E
\u003Cspan class=\&k\&\u003Efor\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E:\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EK\u003C\u002Fspan\u003E\n
\u003Cspan class=\&c\&\u003E%求到每一个中心的距离向量，且不用张量求更加节约空间\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Edist_vec\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(:,\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Esqrt\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Esum\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E((\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edata_set\u003C\u002Fspan\u003E \u003Cspan class=\&o\&\u003E-\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Erepmat\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecenters\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,:),\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EN\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E))\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.^\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E2\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E2\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E));\u003C\u002Fspan\u003E\n
\u003Cspan class=\&k\&\u003Eend\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E这个时候，到第一个点距离最短那么就是1，第二个就是2，如果还用For循环一个个判断你就out了，min函数的第二个返回值是min值所在的位置：\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E[\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E~\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_vec\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E]\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Emin\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Edist_vec\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,[],\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E2\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E只要你乐意，其实还可以生成{r}_{n,k}矩阵（PRML书里用的，偏理论）\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ernk\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Ezeros\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ek\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EN\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n\u003Cspan class=\&n\&\u003Ernk\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Ernk\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E((\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E0\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E:(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003EN\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E-\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E))\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E.*\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ek\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E+\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_vec\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E'\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E;\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E\u003Cbr\u003E其实没必要。\u003Cbr\u003E\u003Cbr\u003E\u003Cb\u003E三、用什么做返回值\u003C\u002Fb\u003E\u003Cbr\u003E这是个仁者见仁丹、智者见智障的问题，Matlab中用刚才计算的cls_vec作为返回值，其实还可以设计一些更加实用的返回值（看你怎么用了）\u003Cbr\u003E\u003Cdiv class=\&highlight\&\u003E\u003Cpre\u003E\u003Ccode class=\&language-matlab\&\u003E\u003Cspan\u003E\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Enot_empty_cls\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Eunique\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_vec\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n\u003Cspan class=\&n\&\u003Ek_means_result\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Ecell\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Elength\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Enot_empty_cls\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E),\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n\u003Cspan class=\&k\&\u003Efor\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E:\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Elength\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Enot_empty_cls\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E)\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Ecls\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Enot_empty_cls\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Esub_res\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Ecell\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E3\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Ecls_idx\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&nb\&\u003Efind\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_vec\u003C\u002Fspan\u003E\u003Cspan class=\&o\&\u003E==\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E);\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Esub_res\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E{\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E1\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E}\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Ecenters\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,:);\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Esub_res\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E{\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E3\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E}\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Ecls_idx\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E;\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Esub_res\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E{\u003C\u002Fspan\u003E\u003Cspan class=\&mi\&\u003E2\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E}\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Edata_set\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E(\u003C\u002Fspan\u003E\u003Cspan class=\&n\&\u003Ecls_idx\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E,:);\u003C\u002Fspan\u003E\n
\u003Cspan class=\&n\&\u003Ek_means_result\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E{\u003C\u002Fspan\u003E\u003Cspan class=\&nb\&\u003Ei\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E}\u003C\u002Fspan\u003E \u003Cspan class=\&p\&\u003E=\u003C\u002Fspan\u003E \u003Cspan class=\&n\&\u003Esub_res\u003C\u002Fspan\u003E\u003Cspan class=\&p\&\u003E;\u003C\u002Fspan\u003E\n\u003Cspan class=\&k\&\u003Eend\u003C\u002Fspan\u003E\n\u003C\u002Fcode\u003E\u003C\u002Fpre\u003E\u003C\u002Fdiv\u003E首先看一下有那几类不空的，好、假设有N类。\u003Cbr\u003E然后生成一个\u003Cimg src=\&http:\u002F\\u002Fequation?tex=%7BN%7D%5Ctimes+%7B1%7D\& alt=\&{N}\\times {1}\& eeimg=\&1\&\u003E的Cell向量，每一个Cell里面放3个Cell：\u003Cbr\u003E1，中心点，2，属于这一类的原始数据，3，刚才那些数据在输入数据里的Index。\u003Cbr\u003E这样的好处是：信息比较全面，调用方便。\u003Cbr\u003E缺点是不够直观么，层次复杂。\u003Cbr\u003E你只要开心可