聚类问题

1.非监督学习和聚类算法介绍

在监督学习中，所有的训练数据、测试数据、都有一系列标签，我们需要据此拟合一个假设函数。与此不同的是，在非监督学习中，数据没有附带任何标签，数据只有一些列的特征，而我们的训练目标就是通过不同特征的训练集，将不同的训练集分为K个类别。

如上图，通过数据特征可以绘制出一些列的点，但是没有标签。也就是说，在非监督学习中，需要将一系列无标签的训练数据，输入到一个算法中，然后我们告诉这个算法，通过我们给定的数据，为我们找到这个数据的内在结构。图上的数据看起来可以分成两个分开的点集（称为簇），一个能够找到上面的点集的可以分为两个分类的算法，就被称为聚类算法， 接下来就通过学习聚类算法来了解非监督学习。

聚类算法的一些应用:

1. 市场分割：比如在数据库中存储了许多客户的信息，希望将他们分成不同的客户群，这样你可以对不同类型的客户分别销售产品或者分别提供更适合的服务。
2. 社交网络分析：关注个人的社交信息，例如Facebook，Google+，或者是其他的一些信息，比如说：经常跟哪些人联系，而这些人又经常给哪些人发邮件，由此找到关系密切的人群
3. 星系分类: 通过聚类算法将不同的行星划分到各个星系

2.K-means算法

K-means是最普及的聚类算法，算法接受一个未标记的数据集，然后将数据聚类成不同的组。
K-means也是一个迭代算法，假设我们想要将数据聚类成n个组，其步骤为:

1. 首先选择K个随机的点，称为聚类中心（cluster centroids）；
2. 对于数据集中的每一个数据，按照距离K个中心点的距离
3. 将其与距离最近的中心点关联起来，与同一个中心点关联的所有点聚成一类。
4. 计算每一个组的平均值，将该组所关联的中心点移动到平均值的位置。
5. 重复步骤2-4直至中心点不再变化。

一个聚类过程示例：

假如进行了10次迭代

用$u^{(1)}, u^{(2)}, …., u^{(k)}$来表示聚类中心，用$c^{(1)}, c^{(2)}, ….., c^{(m)}$ 来存储与第 i 个实例数据最近的聚类中心的索引，K-均值算法的
伪代码如下：

Repeat {

for i = 1 to m

c(i) := index (form 1 to K) of cluster centroid closest to x(i)

for k = 1 to K

μk := average (mean) of points assigned to cluster k

}

算法步骤:

1. 对于每一个样例，计算其应该属于的类。
2. 移动聚类中心，对于每一个类，重新计算该类的中心。

K-均值算法也可以很便利地用于将数据分为许多不同组，即使在没有非常明显区分的组群的情况下也可以。下图所示的数据集包含身高和体重两项特征构成的，利用K-均值算法将数据分为三类，用于帮助确定将要生产的T-恤衫的三种尺寸。

3. K-means优化目标

K-均值最小化问题，是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和

K-均值的代价函数（又称畸变函数 Distortion function）的公式为：

$J \left( c ^ { ( 1 ) } , \ldots , c ^ { ( m ) } , \mu _ { 1 } , \ldots , \mu _ { K } \right) = \frac { 1 } { m } \sum _ { i = 1 } ^ { m } \left| X ^ { ( i ) } - \mu _ { c ^ { ( i ) } } \right| ^ { 2 }$

其中，$u_{c^{(i)}}$代表距离$x^{(i)}$最近的聚类中心， 我们的的优化目标便是找出使得代价函数最小的$c^{(1)}, c^{(2)}, …,c^{(m)}$ 和 $u_1, u_2, …,u_k$, 其优化目标的公式为：

${\min \over { c ^ { ( 1 ) } , \ldots , c ^ { ( m ) } \atop \mu _ { 1 } , \ldots , \mu _ { K } }} J \left( c ^ { ( 1 ) } , \ldots , c ^ { ( m ) } , \mu _ { 1 } , \ldots , \mu _ { K } \right)$

通过对代价函数的构建，可以将K-means每次迭代的两次循环的目的做一个归纳:

1. 第一个循环是重新将样本划分到距离最近的聚类中心点，是用于减小$c^{(i)}$引起的代价；
2. 第二个循环 是重新调整中心点，使其位于该分类的中心， 是用于减小$u_{c^{(i)}}$引起的代价

4. 随机初始化聚类中心

运行K-means算法，首先要随机初始化所有的聚类中心点，通常采用的方式是：

1. 确定聚类中心个数 K，注意聚类中心点的个数 K 要小于所有训练集实例的数量, 即: K < m；
2. 随机选择 K个训练实例，然后令个聚类中心分别与这 K 个训练实例相等;

K-means算法有一个常见的问题，即它有可能会停留在一个局部最小值处，而这取决于初始化的情况， 如下图:

由于聚类中心初始化的距离过近，导致最终只能获得局部的最优解，这样往往不是我们想要的分类结果。

如果想解决这个问题，通常需要多次运行K-means算法，每一次都重新进行随机初始化，最后再比较多次运行K-means的结果，选择代价函数最小的结果。这种方法在 K 较小的时候（2–10）还是可行的，但是如果 K 较大，这么做也可能不会有明显地改善, 但是通常K比较大的时候，局部最优解已经可以很接近最优解。

7.二分K-means算法

二分k-means算法介绍

基于kmeans算法容易使得结果为局部最小值而非全局最小值这一缺陷，对算法加以改进。使用一种用于度量聚类效果的指标SSE(Sum of Squared Error)，即对于第 i 个簇，其SSE为各个样本点到“簇中心”点的距离的平方的和，SSE值越小表示数据点越接近于它们的“簇中心”点，聚类效果也就越好。以此作为划分簇的标准。

算法思想是：先将整个样本集作为一个簇，该“簇中心”点向量为所有样本点的均值，计算此时的SSE。若此时簇个数小于 k，对每一个簇进行kmeans聚类(k=2) ，计算将每一个簇一分为二后的总误差SSE，选择SSE最小的那个簇进行划分操作。

算法计算过程

输入：训练数据集 D=x(1),x(2),…,x(m) ,聚类簇数 k ;
过程：函数 kMeans(D,k,maxIter) .
  1：将所有点看做一个簇，计算此时“簇中心”向量：$\mu ^ { ( 1 ) } = \frac { 1 } { m } \sum _ { x \in D } x​$
  2：while “簇中心”个数h<k“：
  3：  for i=1,2,…,h do
  4：    将第 i 个簇使用 kmeans算法进行划分，其中 k=2
  5：    计算划分后的误差平方和 SSEi
  5：  比较 k 种划分的SSE值，选择SSE值最小的那种簇划分进行划分
  5：  更新簇的分配结果
  5：  添加新的“簇中心”
  18：until 当前“簇中心”个数达到 k
  输出：簇划分 C=C1,C2,…,CK

6.选取聚类数量

聚类选择的通常做法

通常没有具体的聚类数量选择的方法，最普遍的方法就是根据不同的问题和不同的需求，人工进行选择。

通常我们需要知道，进行聚类数量选择的时候需要思考我们运用K-means算法聚类的动机是什么，然后选择能最好服务于该目的标聚类数。

肘部法则

当人们在讨论，选择聚类数目的方法时，有一个可能会谈及的方法叫作“肘部法则”。关于“肘部法则”，我们所需要做的是改变 K 值，也就是聚类类别数目的总数。我们用 K 个聚类来运行K-means聚类方法。这就意味着，所有的数据都会分到 K 个聚类里，然后计算成本函数 J 或者计算畸变函数。K 代表聚类数字。

经过聚类运算，可能会得到一条类似于左边这样的曲线。像一个人的肘部。这就是“肘部法则”所做的，让我们来看这样一个图，看
起来就好像有一个很清楚的肘在那儿。好像人的手臂，如果你伸出你的胳膊，那么这就是你的肩关节、肘关节、手。这就是“肘部法则”。

你会发现这种模式，它的畸变值会迅速下降，从1到2，从2到3之后，你会在3的时候达到一个肘点。在此之后，畸变值就下降的非常慢，看起来就像使用3个聚类来进行聚类是正确的，这是因为那个点是曲线的肘点，畸变值下降得很快， K = 3之后就下降得很慢，那么我们就选 K= 3。当你应用“肘部法则”的时候，如果你得到了一个像上面这样的图，那么这将是一种用来选择聚类个数的合理方法。

总结: 选择聚类数量最好是根据我们的需求，和场景来确定我们是需要多少种聚类，如果我们不能根据使用场景和需求确定下来聚类的数量，那么我们可以通过肘部法则，来选择一个比较合理的聚类数量。

pyhton实现

# coding:utf-8
import numpy as np


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


def randCent(dataSet, k):  # 初始化k个随机簇心
    n = np.array(dataSet).shape[1]  # 特征个数
    centroids = np.mat(np.zeros((k, n)))  # 簇心矩阵k*n
    for j in range(n):  # 特征逐个逐个地分配给这k个簇心。每个特征的取值需要设置在数据集的范围内
        minJ = min(dataSet[:, j])  # 数据集中该特征的最小值
        rangeJ = float(max(dataSet[:, j]) - minJ)  # 数据集中该特征的跨度
        centroids[:, j] = np.mat(minJ + rangeJ * np.random.rand(k, 1))  # 为k个簇心分配第j个特征，范围需限定在数据集内。
    return centroids  # 返回k个簇心


def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    """随机初始化k-means"""
    m = np.array(dataSet).shape[0]  # 数据个数
    clusterAssment = np.mat(np.zeros((m, 2)))  # 记录每个数据点被分配到的簇，以及到簇心的距离
    centroids = createCent(dataSet, k)  # 初始化k个随机簇心
    clusterChanged = True  # 记录一轮中是否有数据点的归属出现变化，如果没有则算法结束
    while clusterChanged:
        clusterChanged = False
        for i in range(m):  # 枚举每个数据点，重新分配其簇归属
            minDist = np.inf  # 先假设距离簇心的距离为无穷大，则先随机分配一个簇心给数据点
            minIndex = -1  # 记录最近簇心及其距离
            for j in range(k):  # 枚举每个簇心
                distJI = distMeas(centroids[j, :], dataSet[i, :])  # 计算数据点与簇心的距离
                if distJI < minDist:  # 更新最近簇心
                    minDist = distJI
                    minIndex = j
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True  # 更新“变化”记录
                clusterAssment[i, :] = minIndex, minDist ** 2  # 更新数据点的簇归属
        print(centroids)
        for cent in range(k):  # 枚举每个簇心，更新其位置
            ptsInClust = dataSet[np.nonzero(clusterAssment[:, 0].A == cent)[0]]  # 得到该簇所有的数据点
            centroids[cent, :] = np.mean(ptsInClust, axis=0)  # 将数据点的均值作为簇心的位置
    return centroids, clusterAssment  # 返回簇心及每个数据点的簇归属


def biKmeans(dataSet, k, distMeas=distEclud):
    """随机初始化二值化k-means"""
    m = np.array(dataSet).shape[0]
    centroid0 = np.mean(dataSet, axis=0).tolist()[0]  # 创建初始簇心，标号为0
    centList = [centroid0]  # 创建簇心列表
    clusterAssment = np.array(np.zeros((m, 2)))  # 初始化所有数据点的簇归属(为0)
    for j in range(m):  # 计算所有数据点与簇心0的距离
        clusterAssment[j, 1] = distMeas(np.array(centroid0), dataSet[j, :]) ** 2
    while len(centList) < k:  # 分裂k-1次，形成k个簇
        lowestSSE = np.inf  # 初始化最小sse为无限大
        for i in range(len(centList)):  # 枚举已有的簇，尝试将其一分为二
            ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:, 0].A == i)[0], :]  # 将该簇的数据点提取出来
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)  # 利用普通k均值将其一分为二
            sseSplit = np.sum(splitClustAss[:, 1])  # 计算划分后该簇的SSE
            sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:, 0].A != i)[0], 1])  # 计算该簇之外的数据点的SSE
            print("sseSplit, and notSplit: ", sseSplit, sseNotSplit)
            if (sseSplit + sseNotSplit) < lowestSSE:  # 更新最小总SSE下的划分簇及相关信息
                bestCentToSplit = i  # 被划分的簇
                bestNewCents = centroidMat  # 划分后的两个簇心
                bestClustAss = splitClustAss.copy()  # 划分后簇内数据点的归属及到新簇心的距离
                lowestSSE = sseSplit + sseNotSplit  # 更新最小总SSE
        print('the bestCentToSplit is: ', bestCentToSplit)
        print('the len of bestClustAss is: ', len(bestClustAss))
        centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]  # 一个新簇心的标号为旧簇心的标号，所以将其取代就簇心的位置
        centList.append(bestNewCents[1, :].tolist()[0])  # 另一个新簇心加入到簇心列表的尾部，标号重新起
        bestClustAss[np.nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)  # 更新旧簇内数据点的标号
        bestClustAss[np.nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit  # 同上
        clusterAssment[np.nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] = bestClustAss  # 将更新的簇归属统计到总数据上
    return np.mat(centList), clusterAssment