1. 首页
  2. 自学中心
  3. 理论
  4. 机器学习

数据挖掘领域十大经典算法之—K-Means算法(超详细附代码)

from https://blog.csdn.net/fuqiuai/article/details/79458331

简介

又叫K-均值算法,是非监督学习中的聚类算法。

基本思想

k-means算法比较简单。在k-means算法中,用cluster来表示簇;容易证明k-means算法收敛等同于所有质心不再发生变化。基本的k-means算法流程如下:

选取k个初始质心(作为初始cluster,每个初始cluster只包含一个点);  
repeat:  
    对每个样本点,计算得到距其最近的质心,将其类别标为该质心所对应的cluster;  
    重新计算k个cluster对应的质心(质心是cluster中样本点的均值);  
until 质心不再发生变化  

数据挖掘领域十大经典算法之—K-Means算法(超详细附代码)

repeat的次数决定了算法的迭代次数。实际上,k-means的本质是最小化目标函数,目标函数为每个点到其簇质心的距离的平方和:

数据挖掘领域十大经典算法之—K-Means算法(超详细附代码)

N是元素个数,x表示元素,c(j)表示第j簇的质心

算法复杂度

时间复杂度是O(nkt) ,其中n代表元素个数,t代表算法迭代的次数,k代表簇的数目

优缺点

优点

  1. 简单、快速;
  2. 对大数据集有较高的效率并且是可伸缩性的;
  3. 时间复杂度近于线性,适合挖掘大规模数据集。

缺点

  1. k-means是局部最优,因而对初始质心的选取敏感;
  2. 选择能达到目标函数最优的k值是非常困难的。

代码

代码已在github上实现,这里也贴出来

# coding:utf-8

import numpy as np
import matplotlib.pyplot as plt


def loadDataSet(fileName):
    '''
    加载测试数据集,返回一个列表,列表的元素是一个坐标
    '''
    dataList = []
    with open(fileName) as fr:
        for line in fr.readlines():
            curLine = line.strip().split('\t')
            fltLine = list(map(float,curLine))
            dataList.append(fltLine)
    return dataList


def randCent(dataSet, k):
    '''
    随机生成k个初始的质心
    '''
    n = np.shape(dataSet)[1] # n表示数据集的维度
    centroids = np.mat(np.zeros((k,n)))
    for j in range(n):
        minJ = min(dataSet[:,j])
        rangeJ = float(max(dataSet[:,j]) - minJ)
        centroids[:,j] = np.mat(minJ + rangeJ * np.random.rand(k,1))
    return centroids


def kMeans(dataSet, k):
    '''
    KMeans算法,返回最终的质心坐标和每个点所在的簇
    '''
    m = np.shape(dataSet)[0] # m表示数据集的长度(个数)
    clusterAssment = np.mat(np.zeros((m,2)))

    centroids = randCent(dataSet, k) # 保存k个初始质心的坐标
    clusterChanged = True
    iterIndex=1 # 迭代次数
    while clusterChanged:
        clusterChanged = False
        for i in range(m):
            minDist = np.inf; minIndex = -1
            for j in range(k):
                distJI = np.linalg.norm(np.array(centroids[j,:])-np.array(dataSet[i,:]))
                if distJI < minDist:
                    minDist = distJI; minIndex = j
            if clusterAssment[i,0] != minIndex: clusterChanged = True
            clusterAssment[i,:] = minIndex,minDist**2
            print("第%d次迭代后%d个质心的坐标:\n%s"%(iterIndex,k,centroids)) # 第一次迭代的质心坐标就是初始的质心坐标
            iterIndex+=1
        for cent in range(k):
            ptsInClust = dataSet[np.nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
            centroids[cent,:] = np.mean(ptsInClust, axis=0)
    return centroids, clusterAssment


def showCluster(dataSet, k, centroids, clusterAssment):
    '''
    数据可视化,只能画二维的图(若是三维的坐标图则直接返回1)
    '''
    numSamples, dim = dataSet.shape
    if dim != 2:
        return 1

    mark = ['or', 'ob', 'og', 'ok','oy','om','oc', '^r', '+r', 'sr', 'dr', '<r', 'pr']

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    mark = ['Pr', 'Pb', 'Pg', 'Pk','Py','Pm','Pc','^b', '+b', 'sb', 'db', '<b', 'pb']
    # draw the centroids
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)

    plt.show()

if __name__ == '__main__':

    dataMat = np.mat(loadDataSet('./testSet')) #mat是numpy中的函数,将列表转化成矩阵

    k = 4 # 选定k值,也就是簇的个数(可以指定为其他数)
    cent, clust = kMeans(dataMat, k)

    showCluster(dataMat, k, cent, clust)

测试数据集获取地址为testSet

原创文章,作者:xsmile,如若转载,请注明出处:http://www.17bigdata.com/%e6%95%b0%e6%8d%ae%e6%8c%96%e6%8e%98%e9%a2%86%e5%9f%9f%e5%8d%81%e5%a4%a7%e7%bb%8f%e5%85%b8%e7%ae%97%e6%b3%95%e4%b9%8b-k-means%e7%ae%97%e6%b3%95%ef%bc%88%e8%b6%85%e8%af%a6%e7%bb%86%e9%99%84/

联系我们

在线咨询:点击这里给我发消息

邮件:23683716@qq.com

跳至工具栏