一.聚类算法的简介
 
        对于"监督学习"(supervised learning)，其训练样本是带有标记信息的，并且监督学习的目的是：对带有标记的数据集进行模型学习，从而便于对新的样本进行分类。而在“无监督学习”(unsupervised learning)中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。对于无监督学习，应用最广的便是"聚类"(clustering)。
         "聚类算法"试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”(cluster)，通过这样的划分，每个簇可能对应于一些潜在的概念或类别。
         我们可以通过下面这个图来理解：
 
         上图是未做标记的样本集，通过他们的分布，我们很容易对上图中的样本做出以下几种划分。
                 当需要将其划分为两个簇时，即 k=2时：
 
         当需要将其划分为四个簇时，即 k=4 时：
 
 
二.K-means聚类算法
 
        kmeans算法又名k均值算法,K-means算法中的k表示的是聚类为k个簇，means代表取每一个聚类中数据值的均值作为该簇的中心，或者称为质心，即用每一个的类的质心对该簇进行描述。
         其算法思想大致为：先从样本集中随机选取 k个样本作为簇中心，并计算所有样本与这 k个“簇中心”的距离，对于每一个样本，将其划分到与其距离最近的“簇中心”所在的簇中，对于新的簇计算各个簇的新的“簇中心”。
         根据以上描述，我们大致可以猜测到实现kmeans算法的主要四点：
           （1）簇个数 k 的选择
           （2）各个样本点到“簇中心”的距离
           （3）根据新划分的簇，更新“簇中心”
           （4）重复上述2、3过程，直至"簇中心"没有移动
         优缺点：
 
优点：容易实现
缺点：可能收敛到局部最小值，在大规模数据上收敛较慢
 
三.K-means算法步骤详解
 
Step1.K值的选择
 
k 的选择一般是按照实际需求进行决定，或在实现算法时直接给定 k 值。
 
 
 
说明：
 A.质心数量由用户给出，记为k，k-means最终得到的簇数量也是k
 B.后来每次更新的质心的个数都和初始k值相等
 C.k-means最后聚类的簇个数和用户指定的质心个数相等，一个质心对应一个簇，每个样本只聚类到一个簇里面
 D.初始簇为空
 
 
Step2.距离度量
 
        将对象点分到距离聚类中心最近的那个簇中需要最近邻的度量策略，在欧式空间中采用的是欧式距离，在处理文档中采用的是余弦相似度函数，有时候也采用曼哈顿距离作为度量，不同的情况实用的度量公式是不同的。
 
2.1.欧式距离
 
 
2.2.曼哈顿距离
 
 
2.3.余弦相似度
 
        A与B表示向量(x1,y1)，(x2,y2)
         分子为A与B的点乘，分母为二者各自的L2相乘，即将所有维度值的平方相加后开方。
 
 
 
 
说明：
 A.经过step2，得到k个新的簇，每个样本都被分到k个簇中的某一个簇
 B.得到k个新的簇后，当前的质心就会失效，需要计算每个新簇的自己的新质心
 
 
Step3.新质心的计算
 
        对于分类后的产生的k个簇，分别计算到簇内其他点距离均值最小的点作为质心（对于拥有坐标的簇可以计算每个簇坐标的均值作为质心）
 
 
 
说明：
 A.比如一个新簇有3个样本：[[1,4], [2,5], [3,6]]，得到此簇的新质心=[(1+2+3)/3, (4+5+6)/3]
 B.经过step3，会得到k个新的质心，作为step2中使用的质心
 
 
Step4.是否停止K-means
 
        质心不再改变，或给定loop最大次数loopLimit
 
 
 
说明：
 A当每个簇的质心，不再改变时就可以停止k-menas
 B.当loop次数超过looLimit时，停止k-means
 C.只需要满足两者的其中一个条件，就可以停止k-means
 C.如果Step4没有结束k-means，就再执行step2-step3-step4
 D.如果Step4结束了k-means，则就打印(或绘制)簇以及质心
 
 
四.python实现+代码详解
 
        以下是python得实例代码以及代码的详解，应该可以理解的。
 
import random
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

# 计算欧拉距离
def calcDis(dataSet, centroids, k):
    clalist=[]
    for data in dataSet:
        diff = np.tile(data, (k, 1)) - centroids  #相减   (np.tile(a,(2,1))就是把a先沿x轴复制1倍，即没有复制，仍然是 [0,1,2]。 再把结果沿y方向复制2倍得到array([[0,1,2],[0,1,2]]))
        squaredDiff = diff ** 2     #平方
        squaredDist = np.sum(squaredDiff, axis=1)   #和  (axis=1表示行)
        distance = squaredDist ** 0.5  #开根号
        clalist.append(distance) 
    clalist = np.array(clalist)  #返回一个每个点到质点的距离len(dateSet)*k的数组
    return clalist

# 计算质心
def classify(dataSet, centroids, k):
    # 计算样本到质心的距离
    clalist = calcDis(dataSet, centroids, k)
    # 分组并计算新的质心
    minDistIndices = np.argmin(clalist, axis=1)    #axis=1 表示求出每行的最小值的下标
    newCentroids = pd.DataFrame(dataSet).groupby(minDistIndices).mean() #DataFramte(dataSet)对DataSet分组，groupby(min)按照min进行统计分类，mean()对分类结果求均值
    newCentroids = newCentroids.values
 
    # 计算变化量
    changed = newCentroids - centroids
 
    return changed, newCentroids

# 使用k-means分类
def kmeans(dataSet, k):
    # 随机取质心
    centroids = random.sample(dataSet, k)
    
    # 更新质心 直到变化量全为0
    changed, newCentroids = classify(dataSet, centroids, k)
    while np.any(changed != 0):
        changed, newCentroids = classify(dataSet, newCentroids, k)
 
    centroids = sorted(newCentroids.tolist())   #tolist()将矩阵转换成列表 sorted()排序
 
    # 根据质心计算每个集群
    cluster = []
    clalist = calcDis(dataSet, centroids, k) #调用欧拉距离
    minDistIndices = np.argmin(clalist, axis=1)  
    for i in range(k):
        cluster.append([])
    for i, j in enumerate(minDistIndices):   #enymerate()可同时遍历索引和遍历元素
        cluster[j].append(dataSet[i])
        
    return centroids, cluster
 
# 创建数据集
def createDataSet():
    return [[1, 1], [1, 2], [2, 1], [6, 4], [6, 3], [5, 4]]

if __name__=='__main__': 
    dataset = createDataSet()
    centroids, cluster = kmeans(dataset, 2)
    print('质心为：%s' % centroids)
    print('集群为：%s' % cluster)
    for i in range(len(dataset)):
      plt.scatter(dataset[i][0],dataset[i][1], marker = 'o',color = 'green', s = 40 ,label = '原始点')
                                                    #  记号形状       颜色      点的大小      设置标签
      for j in range(len(centroids)):
        plt.scatter(centroids[j][0],centroids[j][1],marker='x',color='red',s=50,label='质心')
        plt.show
 
五.K-means算法补充
 
1.对初始化敏感，初始质点k给定的不同，可能会产生不同的聚类结果。如下图所示，右边是k=2的结果，这个就正好，而左图是k=3的结果，可以看到右上角得这两个簇应该是可以合并成一个簇的。
 
改进：
 对k的选择可以先用一些算法分析数据的分布，如重心和密度等，然后选择合适的k
 
 2.使用存在局限性，如下面这种非球状的数据分布就搞不定了：
 
 3.数据集比较大的时候，收敛会比较慢。
 
4.最终会收敛。不管初始点如何选择，最终都会收敛。可是是全局收敛，也可能是局部收敛。
 
六.小结
 
        1. 聚类是一种无监督的学习方法。聚类区别于分类，即事先不知道要寻找的内容，没有预先设定好的目标变量。
 
        2. 聚类将数据点归到多个簇中，其中相似的数据点归为同一簇，而不相似的点归为不同的簇。相似度的计算方法有很多，具体的应用选择合适的相似度计算方法
 
        3. K-means聚类算法，是一种广泛使用的聚类算法，其中k是需要指定的参数，即需要创建的簇的数目，K-means算法中的k个簇的质心可以通过随机的方式获得，但是这些点需要位于数据范围内。在算法中，计算每个点到质心得距离，选择距离最小的质心对应的簇作为该数据点的划分，然后再基于该分配过程后更新簇的质心。重复上述过程，直至各个簇的质心不再变化为止。
 
        4. K-means算法虽然有效，但是容易受到初始簇质心的情况而影响，有可能陷入局部最优解。为了解决这个问题，可以使用另外一种称为二分K-means的聚类算法。二分K-means算法首先将所有数据点分为一个簇；然后使用K-means（k=2）对其进行划分；下一次迭代时，选择使得SSE下降程度最大的簇进行划分；重复该过程，直至簇的个数达到指定的数目为止。实验表明，二分K-means算法的聚类效果要好于普通的K-means聚类算法。

K-means聚类算法和模糊C-means聚类算法
 
1.K-means聚类算法
 
K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最优分类，使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。
 

 
k-means聚类算法原理简介
 
概要
算法思想
算法流程图解
代码实现
算法优化
代价函数（Distortion function）
如何选取k值
聚类中心的初始化
 

 
概要
 
K-means算法是最普及的聚类算法，也是一个比较简单的聚类算法，所以刚接触的同学不要感到害怕。算法接受一个未标记的数据集，然后将数据聚类成不同的组，同时，k-means算法也是一种无监督学习。
 
算法思想
 
k-means算法的思想比较简单，假设我们要把数据分成K个类，大概可以分为以下几个步骤：
 
随机选取k个点，作为聚类中心；
计算每个点分别到k个聚类中心的聚类，然后将该点分到最近的聚类中心，这样就行成了k个簇；
再重新计算每个簇的质心（均值）；
重复以上2~4步，直到质心的位置不再发生变化或者达到设定的迭代次数。
 
算法流程图解
 
下面我们通过一个具体的例子来理解这个算法（我这里用到了Andrew Ng的机器学习教程中的图）：
 假设我们首先拿到了这样一个数据，要把它分成两类：
 
 我们人眼当然可以很快的分辨出来，可以在两个聚类间找到一条合理的分界线，那么用k-means算法来解决这个问题会是怎样的呢？
 首先我们随机选取两个点作为聚类中心（因为已经明确是分为两类）：
 
 接下来就可以开始计算每个点到红点和蓝点的距离了，离红点近就标记为红色，离蓝点近就标记为蓝色。结果为下图：
 
 很明显，这样完全不是我们想要的结果，接下来我们进行第三步，重新计算聚类中心的位置。
 
 红X和蓝X都向中间靠拢了一点。我们可以看到，聚类中心发生改变后，其他点离两个聚类中心的距离也跟随着发生了变化。然后我们重复第二步，根据每个点到两个聚类中心的距离远近来进行重新分类，离红X近的归为红类，离蓝X近的归为蓝类。
 
 之前站错了队伍的一些点重新进行了调整，现在的分类离我们的目标越来越近了，但还没有达到最佳的分类效果。接下来继续重复上面的步骤，重新计算聚类中心的位置，再重新分类，不断迭代，直至聚类中心的位置不再变化（变化范围达到设定值）或达到迭代次数为止。
 
 这样我们就利用k-means算法把这个数据很好的分为两类啦。
 我们可以看到，在整个过程中，我们都没有去监督算法，告诉他具体是分错了还是对了，只是在开始的时候告诉他要把这个数据分成多少类，然后后面的操作都是由他自己完成，完全没有人为的让他进行分类的学习，也没有帮助他纠正错误，所以k-means算法也是一种无监督学习方法。
 相信看到这里你对k-means算法的原理也有了一个大概的了解啦。下面我们再来看看这个算法的代码实现吧。
 
代码实现
 
下面就放一个Andrew Ng 机器学习教程的习题答案吧，把k-means算法的具体流程大概实现了一下：
 
function [centroids, idx] = runkMeans(X, initial_centroids, ...
                                      max_iters, plot_progress)
%RUNKMEANS runs the K-Means algorithm on data matrix X, where each row of X
%is a single example
%   [centroids, idx] = RUNKMEANS(X, initial_centroids, max_iters, ...
%   plot_progress) runs the K-Means algorithm on data matrix X, where each 
%   row of X is a single example. It uses initial_centroids used as the
%   initial centroids. max_iters specifies the total number of interactions 
%   of K-Means to execute. plot_progress is a true/false flag that 
%   indicates if the function should also plot its progress as the 
%   learning happens. This is set to false by default. runkMeans returns 
%   centroids, a Kxn matrix of the computed centroids and idx, a m x 1 
%   vector of centroid assignments (i.e. each entry in range [1..K])
%

% Set default value for plot progress
if ~exist('plot_progress', 'var') || isempty(plot_progress)
    plot_progress = false;
end

% Plot the data if we are plotting progress
if plot_progress
    figure;
    hold on;
end

% Initialize values
[m n] = size(X);
K = size(initial_centroids, 1);
centroids = initial_centroids;
previous_centroids = centroids;
idx = zeros(m, 1);

% Run K-Means
for i=1:max_iters
    
    % Output progress
    fprintf('K-Means iteration %d/%d...\n', i, max_iters);
    if exist('OCTAVE_VERSION')
        fflush(stdout);
    end
    
    % For each example in X, assign it to the closest centroid
    idx = findClosestCentroids(X, centroids);
    
    % Optionally, plot progress here
    if plot_progress
        plotProgresskMeans(X, centroids, previous_centroids, idx, K, i);
        previous_centroids = centroids;
        fprintf('Press enter to continue.\n');
        pause;
    end
    
    % Given the memberships, compute new centroids
    centroids = computeCentroids(X, idx, K);
end

% Hold off if we are plotting progress
if plot_progress
    hold off;
end

end
 
算法优化
 
代价函数（Distortion function）
 
要是k-means最后的分类结果最好，也就是要是K-均值最小化，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和，因此我们可以设计 K-均值的代价函数（又称 畸变函数 Distortion function）为：
 
 其中μ c (i)代表与 x (i) 最近的聚类中心点。 我们的的优化目标也就是要找出使得代价函数最小的 c (1) ,c (2) ,…,c (m) 和μ 1 ,μ 2 ,…,μ k 。
 我们再回顾一下刚才给出的 K-means算法的迭代过程，我们知道，第一个步骤（根据聚类中心分类）是用于减小 c (i) 引起的代价，而第二个步骤（重新定位聚类中心）则是用于减小μ i 引起的代价。所以迭代的过程一定会是每一次迭代都在减小代价函数，如果发生迭代之后代价函数反而增加，则很可能是出现了错误。
 
如何选取k值
 
对于一个给定没有分类的数据集，最后具体应该分为多少类呢？这确实是一个问题，比如我们前面的那个例子，通过人眼观察，很明显可以分为两类，那么我们选取K值为2，可以得到一个比较好的聚类结果。那如果K选择3或者其他值行不行呢？当然也可以。
 比如下图，有一个数据经过统计之后发现随着K值的增加其畸变函数在不断变小，但是我们发现在k=3时，畸变函数随着k值变化的幅度显著降低，在k>3之后所带来的好处并不是特别明显，所以我们可以选择k=3作为我们的聚类数目。由于其形状像我们人类的肘部，我们也称其为“肘部法则”。
 
 但是实际应用中，k值的变换规律都不是和上图一样存在突变点，多数情况如下图所示：
 
 随着k值的增大，其畸变函数也随着不断减小，根本就不存在明显的拐点。那么这种情况，K值的选择主要还是根据经验以及利用k-means聚类的目的来决定。
 
聚类中心的初始化
 
前面提到代价函数的建立，可以方便我们来对k-means算法的结果进行优化，方便我们察觉出算法迭代过程中的收敛问题，是否达到局部最小化，或者检查算法迭代过程中是否出现问题。而通过k值的选取也可能使我们的代价函数尽量的减小，以得到更好的聚类效果。
 那么还有什么其他优化的方法呢？
 我们还可以通过选取更优的聚类中心来优化聚类效果。
 上面的例图是一个简单的二分类问题，并且不同类之间的界限也比较明显，最后我们得到的聚类结果也相对比较理想。但实际上聚类中心选择的不同，最终的聚类结果肯定也是会不一样的。
 比如对于下面这张图：
 
 我把初始的聚类中心选择在这两个不同的位置，最后导致的分类结果和迭代次数都会不一样。聚类中心的选取主要还是以随机为主，并且初始的时候最好是选择数据中的点。
 对于多分类，甚至还会出现下面这种情况：
 
 
 最后很可能仅仅实现了局部最优，把本来不是一类的多个类分为了一类，或者把本来是一类的分成了多个类，这些都是有可能的。那么对于这种情况怎么办呢？
 对于聚类数目K值较小（K<10）的情况下，我们可以多次随机选取不同聚类中心，最后比较各自迭代完成后的畸变函数值，畸变函数越小，则说明聚类效果更优。但是在k值较大的情况下，比如上百类甚至上千万类，这时候重新选取不同的聚类中心可能就没有很好的效果了。

K-Means聚类算法
 
K-Means聚类算法是典型的基于距离的非层次聚类算法，在最小化误差的函数的基础上将数据划分为预设的类数K，采用距离作为相似性的评价标准，即认为两个对象的距离越近，其相似度就越大。
 
1.算法过程：
 
从N个样本数据中随机选取K个对象作为初始的聚类中心。 
分别计算每个样本到各个聚类中心的距离，将对象分配到距离最近的聚类中。
所有对象分配完成之后，重新计算K个聚类的中心。
与前一次计算得到的K个聚类中心相比较，如果聚类中心发生了变化，则执行步骤2。否则就转步骤5。
当聚类中心不发生变化的时停止并输出聚类的结果。
 
在所有的对象分配完成后，重新计算K个聚类中心的时候，对于连续数据，聚类中心选择该簇的均值，但是当样本的一些属性是离散（分类变量）时，均值是无定义的，可以使用K-众数方法。
 
2距离的计算
 
距离的种类，有三种： 
 1）样本与样本。 
 2）样本与簇（样本与簇中心）。 
 3）簇与簇（簇中心和簇中心）。 
 连续属性： 
 欧几里得距离; 曼哈吨距离; 闵可夫斯基距离; 
 欧几里得距离： 
 曼哈吨距离： 
 闵可夫斯基距离：
 
文档数据（以每个单词作为属性，次数为值，组成一个向量）。 
 余弦相似性度量： 
  
 其中a，b为两个向量。
 
3目标函数
 
使用的是平方和SSE作为聚类质量的目标函数，对于两种不同的聚类结果，选择误差平方和最小的分类结果。
 
连续属性的SSE计算公式为： 
  
 文本数据的SSE计算公式为： 
 
 
下面对上面公式的符号进行说明: 
 Ci:簇i的聚类中心 
 K：聚类的簇数 
 迭代符下的Ci是第i簇 
 x：样本