K-means算法源于信号处理中的一种向量量化方法,现在则更多地作为一种聚类分析方法流行于数据挖掘领域

K-means算法

K-means算法源于信号处理中的一种向量量化方法,现在则更多地作为一种聚类分析方法流行于数据挖掘领域。K-means的目的是:把n个点(可以是样本的一次观察或一个实例)划分到K个聚类中,使得每个点都属于离他最近的均值(此即聚类中心)对应的聚类,以之作为聚类的标准。

这个问题在计算上是NP困难[1] ,不过存在高效的启发式算法。一般情况下,都使用效率比较高的启发式算法,它们能够快速收敛于一个局部最优解。这些算法通常类似于通过迭代优化方法处理高斯混合分布的最大期望算法[2] 。而且,它们都使用聚类中心来为数据建模;然而K-means倾向于在可比较的空间范围内寻找聚类。

需要注意的是,K-means与K-NN算法之间没有任何关系。

算法描述

已知观测集(x1,x2,...,xn),其中每个观测都是一个d-维实向量,K-means要把这n个观测值划分到k个集合中(k<=n),使得组内平方和最小。换句话说,他的目标是找到使得下式满足的聚类Si

avatar

其中ui是Si中所有点的均值

算法

标准算法

最常用的算法使用了迭代优化的技术。已知初始的k个均值点m_{1}{{(1)}},...,m_{k}{{(1)}},算法的按照下面两个步骤交替进行

  • 分配:将每个观测分配到聚类中,使得组内平方和达到最小

因为这一平方和就是平方后的欧式距离,所以很直观地把观测分配到离它最近的均值点即可。

avatar

其中每个avatar都只被分配到一个确定的聚类S^{{t}}中,尽管在理论上它可能被分配到2个或者更多的聚类。

  • 更新:对于上一步得到的每一个聚类,以聚类中观测值的图心,作为新的均值点。
avatar

因为算术平均是最小二乘估计,所以这一步同样减小了目标函数组内平方和的值。

这一算法将在对于观测的分配不再变化时收敛。由于交替进行的两个步骤都会减小目标函数组内平方和的值,并且分配方案只有有限种,所以算法一定会收敛于某一(局部)最优解。

注意:使用这一算法无法保证得到全局最优解。

这一算法经常被描述为“把观测按照距离分配到最近的聚类”。标准算法的目标函数是组内平方和,而且按照“最小二乘和”来分配观测,确实是等价于按照最小欧氏距离来分配观测的。如果使用不同的距离函数来代替(平方)欧氏距离,可能使得算法无法收敛。然而,使用不同的距离函数,也能得到k-均值聚类的其他变体,如球体k-均值算法和k-中心点算法。

初始化方法

通常使用的初始化方法有Forgy和随机划分方法。Forgy方法随机地从数据集中选择k个观测作为初始的均值点;而随机划分方法则随机地为每一观测指定聚类,然后运行“更新(Update)”步骤,即计算随机分配的各聚类的图心,作为初始的均值点。Forgy方法易于使得初始均值点散开,随机划分方法则把均值点都放到靠近数据集中心的地方。对于期望-最大化(EM)算法和标准k-均值算法,Forgy方法作为初始化方法的表现会更好一些。

复杂度

在d维空间中找到K-means问题的最优解的时间复杂度为

avatar

其中n为待聚类的观测点数目

相关应用

向量的量化

k-means起源于信号处理领域,并且现在也能在这一领域找到应用。例如在计算机图形学中,色彩量化的任务,就是要把一张图像的色彩范围减少到一个固定的数目k上来。k-means算法就能很容易地被用来处理这一任务,并得到不错的结果。其它得向量量化的例子有非随机抽样,在这里,为了进一步的分析,使用k-means算法能很容易的从大规模数据集中选出k个合适的不同观测

聚类分析

在聚类分析中,k-means算法被用来将输入数据划分到k个部分(聚类)中。 然而,纯粹的k-means算法并不是非常灵活,同样地,在使用上有一定局限(不过上面说到的向量量化,确实是一个理想的应用场景)。特别是,当没有额外的限制条件时,参数k是很难选择的(正如上面讨论过的一样)。算法的另一个限制就是它不能和任意的距离函数一起使用、不能处理非数值数据。而正是为了满足这些使用条件,许多其他的算法才被发展起来。

特征学习

在(半)监督学习或无监督学习中,k-means被用来进行特征学习(或字典学习)步骤。基本方法是,首先使用输入数据训练出一个k-means表示,然后把任意的输入数据投射到这一新的特征空间。 k-means的这一应用能成功地与自然语言处理和计算机视觉中半监督学习的简单线性分类器结合起来。在对象识别任务中,它能展现出与其他复杂特征学习方法(如自动编码器、受限Boltzmann机等)相当的效果。然而,相比复杂方法,它需要更多的数据来达到相同的效果,因为每个数据点都只贡献了一个特征(而不是多重特征)。

简单实现

代码块

# -*- coding: UTF-8 -*-
import numpy
import random
import matplotlib.pyplot as plt


def findCentroids(data_get, k):  # 随机获取k个质心

    return random.sample(data_get, k)


def calculateDistance(vecA, vecB):  # 计算向量vecA和向量vecB之间的欧氏距离

    return numpy.sqrt(numpy.sum(numpy.square(vecA - vecB)))


def minDistance(data_get, centroidList):
    # 计算data_get中的元素与centroidList中k个聚类中心的欧式距离,找出距离最小的
    # 将该元素加入相应的聚类中

    clusterDict = dict()  # 用字典存储聚类结果
    for element in data_get:
        vecA = numpy.array(element)  # 转换成数组形式
        flag = 0  # 元素分类标记,记录与相应聚类距离最近的那个类
        minDis = float("inf")  # 初始化为最大值

        for i in range(len(centroidList)):
            vecB = numpy.array(centroidList[i])
            distance = calculateDistance(vecA, vecB)  # 两向量间的欧式距离
            if distance < minDis:
                minDis = distance
                flag = i  # 保存与当前item距离最近的那个聚类的标记

        if flag not in clusterDict.keys():  # 簇标记不存在,进行初始化
            clusterDict[flag] = list()
        clusterDict[flag].append(element)  # 加入相应的类中

    return clusterDict  # 返回新的聚类结果


def getCentroids(clusterDict):
    centroidList = list()
    for key in clusterDict.keys():
        centroid = numpy.mean(numpy.array(clusterDict[key]), axis=0)  # 求聚类中心即求解每列的均值
        centroidList.append(centroid)

    return numpy.array(centroidList).tolist()


def calculate_Var(clusterDict, centroidList):
    # 计算聚类间的均方误差
    # 将类中各个向量与聚类中心的距离进行累加求和

    sum = 0.0
    for key in clusterDict.keys():
        vecA = numpy.array(centroidList[key])
        distance = 0.0
        for item in clusterDict[key]:
            vecB = numpy.array(item)
            distance += calculateDistance(vecA, vecB)
        sum += distance

    return sum


def showCluster(centroidList, clusterDict):
    # 画聚类结果

    colorMark = ['or', 'ob', 'og', 'ok', 'oy', 'ow']  # 元素标记
    centroidMark = ['dr', 'db', 'dg', 'dk', 'dy', 'dw']  # 聚类中心标记
    for key in clusterDict.keys():
        plt.plot(centroidList[key][0], centroidList[key][1], centroidMark[key], markersize=12)  # 画聚类中心
        for item in clusterDict[key]:
            plt.plot(item[0], item[1], colorMark[key])  # 画类下的点

    plt.show()


data = [[0.0, 0.0], [3.0, 8.0], [2.0, 2.0], [1.0, 1.0], [5.0, 3.0],
        [4.0, 8.0], [6.0, 3.0], [5.0, 4.0], [6.0, 4.0], [7.0, 5.0]]

if __name__ == '__main__':

    centroidList = findCentroids(data, 3)  # 随机获取3个聚类中心
    clusterDict = minDistance(data, centroidList)  # 第一次聚类迭代
    newVar = calculate_Var(clusterDict, centroidList)  # 计算均方误差值,通过新旧均方误差来获得迭代终止条件
    oldVar = -0.0001  # 初始化均方误差

    print('***** 第1次迭代 *****')
    for key in clusterDict.keys():
        print('聚类中心: ', centroidList[key])
        print('对应聚类: ', clusterDict[key])
    print('平均均方误差: ', newVar)
    showCluster(centroidList, clusterDict)  # 展示聚类结果

    k = 2
    while abs(newVar - oldVar) >= 0.0001:  # 当连续两次聚类结果差距小于0.0001时,迭代结束
        centroidList = getCentroids(clusterDict)  # 获得新的聚类中心
        clusterDict = minDistance(data, centroidList)  # 新的聚类结果
        oldVar = newVar
        newVar = calculate_Var(clusterDict, centroidList)

        print('***** 第%d次迭代 *****' % k)

        for key in clusterDict.keys():
            print('聚类中心: ', centroidList[key])
            print('对应聚类: ', clusterDict[key])
        print('平均均方误差: ', newVar)
        showCluster(centroidList, clusterDict)  # 展示聚类结果

        k += 1

测试结果

avatar

应用场景描述

在数据化运营方面,聚类分析的一个重要用途就是目标群体进行多指标的群体划分,而类似这种目标群体的分类常常就是精细化运营,个性化运营的基础和核心,只有进行了正确的分类,才可以有效进行个性化和精细化的运营,服务及产品支持等。从这个角度来看,聚类分析技术对于数据化运营是非常重要和基础的。

总的来说,聚类分析技术在数据化运营实践中常见的业务应用场景如下:

  • 目标用户的群体分类:通过为特定运营目的和商业目的所挑选出的指标变量进行聚类分析,把目标群体划分成几个具有明显特征区别的细分群体,从而可以在运营活动中为这些细分群体采用精细化、个性化的运营和服务,最终提升运营的效率和商业的效果。
  • 不同产品的价值组合:企业可以按照不同的商业目的,并依照特定的指标变量来为众多的产品种类进行聚类分析,把企业的产品体系进一步细分成具有不同价值、不同目的多维度的产品组合,并且可在此基础上分别制定相应的产品开发计划、运营计划和服务规划。
  • 探测,发现孤立点,异常值:孤立点就是指相对于整体数据对象而言的少数数据对象,这些对象的行为特征与整体的数据行为特征很不一致。虽然在一般的数据处理过程中会把孤立点作为噪声而剔除出去,但是在许多业务领域里,孤立点的价值非常重要。比如说,互联网的风险管理里,就非常强调对于风险的预防和预判,而相关的风险控制分析中的孤立点很多时候又是风险的最大嫌疑和主要来源。及时发现这些特殊行为对于互联网的风险管理来说至关重要。比如,某B2C电商平台上,比较昂贵的、频繁的交易,就有可能隐含着欺诈的风险成分,需要风控部门提前关注、监控,防患于未然。

方法步骤

处理数据噪声和异常值

K-Means算法对噪声和异常值非常敏感,这些个别数据对于平均值的影响非常大,鉴于K-means算法的这一局限性,我们在使用该算法时需要特别注意这些数据噪音和异常值。

常见的处理方法有:

  • 直接删除那些比其他任何数据点都要远离数据中心点的异常值。但同时为了防止误删,数据分析师需要监控这些异常值进行对比后再决定是否删除这些异常值。
  • 使用随机抽样的方法。数据噪音和异常值本来就很少,因此被随机抽进样本中的概率很低。

数据标准化

在数据化运营中,参与聚类的变量绝大多数都是区间型变量,不同区间型变量之间的数量单位不同,如果不进行标准化处理,容易造成聚类结果的失真。比如长度单位有的是公里,有的是米,有的是毫米。质量单位有的是吨,有的是克。因此为了避免这些影响,在聚类之前要采取的一个重要技术措施就是进行数据标准化。

数据标准化有许多方法。其中,标准差标准化最常用,又叫Z-score标准化,经过这种方法处理后的数据符合标准正态分布。

def z_score(x, axis):
    x = np.array(x).astype(float)
    xr = np.rollaxis(x, axis=axis)
    xr -= np.mean(x, axis=axis)
    xr /= np.std(x, axis=axis)
    # print(x)
    return x

聚类变量少而精

在聚类分析中,参与聚类的指标变量不能太多,如果太多,一方面会显著增加运算的时间,更重要的是变量之间或多或少的相关性会严重损害聚类的效果。因此,如何精心挑选特定的少数变量参与聚类也是聚类分析应用中的有一个关键点

伪代码

avatar

结果评估

通过聚类分析,业务方从所有用户中提取出两个群体:

  • 群体A:占样本数量的15%,主要特征为:全部是企业俱乐部用户,全部有在线交易历史,俱乐部年限小于4年,登录次数大于110次,访问量大于10 000。
  • 群体B:占样本数量的10%,主要特征为:全部是个人俱乐部用户,全部有在线交易历史,俱乐部年限小于2年,登录次数大于100次,并且俱乐部指数小于80。

运营方根据上述两个群体特征,提取出满足上述阈值的20000潜在目标用户,并进行1周的定向在线运营活动,通过3轮营销推广活动,最后付费转换率为4.69%

作为对比,2006年,世界知名的计算机硬件和软件系统服务提供商Oracle公司在中国市场做过一次比较成功的定向运营推广活动。先向200 000企业高层相关人士通过EDM(电子邮件营销)、Banner(官方网站的横幅广告)、直邮、电话访问以及夹报广告等各种传播方式传达Oracle的产品理念,经过两个月运营,有20 000目标受众对此表示出了兴趣,其阅读了宣传资料或者访问了产品宣传网站,进一步跟进,有2000人填写了反馈问卷,并下载了相关资料,最终,Oracle得到了900个销售机会。Oracle公司本次为期3个月的定向运营,得到的销售计划转化率为0.45%。

可以看见,经过K-means算法聚类分析后的准确投放,转换率得到了大大的提高。

优缺点分析

聚类分析的优势在实践中十分明显,尤其是在针对大数据集的时候,具体来讲,其应用优势体现在以下几个方面:

  • 目前聚类技术十分成熟,算法可靠,长期的商业实践已经证明它是一个很好的数据群体细分的工具和方法
  • K-means算法简洁,高效。前面已经说了它的时间复杂度。可以看见K-means算法的时间复杂度与数据集的大小是线性相关的。
  • K-means算法不依赖顺序,给定一个初始分布,无论顺序如何,聚类过程结束后的数据分区结果都是一样的。

说了这几个优点,那么它的缺点呢?

  • 如前所述,K-means算法对数据噪音和异常值比较敏感。
  • 同时,K-means算法的K需要事先指定聚类的数目k。在实践中,要测试多个不同的k值才能根据效果比较来选择最合适的K值,这个过程可能会比较耗时。

优化——K-means++算法

缘由

由于K-means算法的分类结果会受初始点的选取而有所区别,因此提出了K-means++这一算法

算法步骤

只是对初始点的选择有改进,其余步骤都一样。初始质心选取的基本思想就是:初始的聚类中心之间的相互距离要尽可能的远。

avatar

参考

  • https://en.wikipedia.org/wiki/K-means_clustering
  • https://en.wikipedia.org/wiki/K-means%2B%2B
  • https://www.cnblogs.com/wang2825/articles/8696830.html
  • 《数据挖掘与数据化运营实战:思路、方法、技巧与应用》

p


  1. 介绍NP困难之前要说到P问题和NP问题,P问题是在多项式时间内可以被解决的问题,而NP问题实在多项式时间内可以被验证其正确性的问题。NP困难问题是计算复杂性理论中最重要的复杂性类之一。如果所有NP问题都可以多项式时间归约到某个问题,则称该问题为NP困难。 ↩︎

  2. 在统计中被用于寻找,依赖于不可观察的隐性变量的概率模型中,参数的最大似然估计。 ↩︎