K-means算法如何實(shí)現(xiàn)二維數(shù)據(jù)聚類

所謂聚類分析，就是給定一個(gè)元素集合D，其中每個(gè)元素具有n個(gè)觀測屬性，對這些屬性使用某種算法將D劃分成K個(gè)子集，要求每個(gè)子集內(nèi)部的元素之間相似度盡可能高，而不同子集的元素相似度盡可能低。聚類分析是一種無監(jiān)督的觀察式學(xué)習(xí)方法，在聚類前可以不知道類別甚至不用給定類別數(shù)量。目前聚類廣泛應(yīng)用于統(tǒng)計(jì)學(xué)、生物學(xué)、數(shù)據(jù)庫技術(shù)和市場營銷等領(lǐng)域。

聚類算法有很多種，如K-means（K均值聚類）、K中心聚類、密度聚類、譜系聚類、最大期望聚類等。這里我們重點(diǎn)介紹K-means聚類算法，該算法的基本思想是以空間中K個(gè)點(diǎn)為中心進(jìn)行聚類，對最靠近它們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。K-means算法實(shí)現(xiàn)簡單、計(jì)算速度快、原理易于理解、具有理想的聚類效果，因此該算法是公認(rèn)的經(jīng)典數(shù)據(jù)挖掘方法之一。

例如對于常見的二維數(shù)據(jù)集，設(shè)計(jì)K-means聚類方法，對80個(gè)二維數(shù)據(jù)點(diǎn)進(jìn)行聚類分析。K-means算法的Python語言實(shí)現(xiàn)及處理過程如下：

如下圖所示的80個(gè)二維樣本數(shù)據(jù)集，存儲為testSet文本文檔。經(jīng)過數(shù)據(jù)預(yù)處理和簡單分析，得知該數(shù)據(jù)集共有4個(gè)類別，因而能確定聚類數(shù)K為4。

首先導(dǎo)入必要的模塊：

import kmeans

import numpy as np

import matplotlib.pyplot as plt

from math import sqrt

（1） 從文件加載數(shù)據(jù)集

構(gòu)建數(shù)據(jù)矩陣，從文本中逐行讀取數(shù)據(jù)，形成供后繼使用的數(shù)據(jù)矩陣。

dataSet=[]

fileIn=open('testSet.txt')

for line in fileIn.readlines():

    lineArr=line.strip().split('\t')

    dataSet.append([float(lineArr[0]),float(lineArr[1])])

（2） 調(diào)用kmeans算法進(jìn)行數(shù)據(jù)聚類

通過以下命令調(diào)用設(shè)計(jì)的kmeans模塊，進(jìn)行數(shù)據(jù)聚類。

dataSet=np.mat(dataSet)

k=4

centroids,clusterAssment=kmeans.kmeanss(dataSet,k)

kmeans模塊主要包含如下幾個(gè)函數(shù)。

距離度量函數(shù)。這里使用的是歐氏距離，計(jì)算過程如下：

def eucDistance(vec1,vec2):

   return sqrt(sum(pow(vec2-vec1,2)))

初始聚類中心選擇。從數(shù)據(jù)集中隨機(jī)選擇K個(gè)數(shù)據(jù)點(diǎn)，用作初始聚類中心。

def initCentroids(dataSet,k):

    numSamples,dim=dataSet.shape

    centroids=np.zeros((k,dim))

    for i in range(k):

        index=int(np.random.uniform(0,numSamples))

        centroids[i,:]=dataSet[index,:]

    return centroids

K-Means 聚類算法。該算法會(huì)創(chuàng)建k個(gè)質(zhì)心，然后將每個(gè)點(diǎn)分配到最近的質(zhì)心，再重新計(jì)算質(zhì)心。這個(gè)過程重復(fù)數(shù)次，直到數(shù)據(jù)點(diǎn)的簇分配結(jié)果不再改變位置。

def kmeanss(dataSet,k):

numSamples=dataSet.shape[0]

    clusterAssement=np.mat(np.zeros((numSamples,2)))

    clusterChanged=True

    ##step1:init centroids

    centroids=initCentroids(dataSet,k)

    while clusterChanged:

        clusterChanged=False

        for i in range(numSamples):

            minDist = 100000.0

            minIndex=0

            ##step2 find the centroid who is closest

            for j in range(k):

                distance=eucDistance(centroids[j,:],dataSet[i,:])

                if distance < minDist:

                    minDist=distance

                    minIndex=j

            ##step3: update its cluster

            clusterAssement[i,:]=minIndex,minDist**2

            if clusterAssement[i,0]!=minIndex:

                clusterChanged=True

        ##step4: update centroids

        for j in range(k):

            pointsInCluster=dataSet[np.nonzero(clusterAssement[:,0].A==j)[0]]

            centroids[j,:]=np.mean(pointsInCluster,axis=0)

    print ('Congratulations,cluster complete!')

    return centroids,clusterAssement

聚類結(jié)果顯示。將聚類劃分在的不同簇的數(shù)據(jù)，用不同的顏色和符號進(jìn)行顯示，同時(shí)畫出最終的聚類中心。

def showCluster(dataSet,k,centroids,clusterAssement):

numSamples,dim=dataSet.shape

mark=['or','ob','og','ok','^r','+r','<r','pr']

if k > len(mark):

          print("Sorry!")

          return 1

for i in np.xrange(numSamples):

          markIndex=int(clusterAssement[i,0])

          plt.plot(centroids[i,0],centroids[i,1],mark[i],markersize=12)

plt.show()

（3） 聚類結(jié)果顯示

對80個(gè)二維數(shù)據(jù)，使用K-means方法進(jìn)行聚類，聚類結(jié)果如圖13-5所示，迭代后的聚類中心用方形表示，其他數(shù)據(jù)用不同顏色的原點(diǎn)表示。

圖 二維數(shù)據(jù)的聚類結(jié)果