1、學(xué)習(xí)算法 day02_Kmeans 聚類算法及應(yīng)用課程大綱課程目標(biāo)：1、理解 Kmeans 聚類算法的思想2、理解 Kmeans 聚類算法的代碼實(shí)現(xiàn)3、掌握 Kmeans 聚類算法的應(yīng)用步驟：數(shù)據(jù)處理、建模、運(yùn)算和結(jié)果判定Kmeans 聚類算法原理Kmeans 聚類算法概述Kmeans 聚類算法圖示Kmeans 聚類算法要點(diǎn)Kmeans 聚類算法案例需求用 Numpy 手動(dòng)實(shí)現(xiàn)用 Scikili學(xué)習(xí)算法庫(kù)實(shí)現(xiàn)Kmeans 聚類算法補(bǔ)充算法缺點(diǎn)改良思路1. Kmeans 聚類算法原理1.1 概述K-means 算法是集簡(jiǎn)單和經(jīng)典于一身的基于距離的聚類算法采用距離作為相似性的評(píng)價(jià)指標(biāo)，即認(rèn)為兩個(gè)對(duì)

2、象的距離越近，其相似度就越大。該算法認(rèn)為類簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且的簇作為最終目標(biāo)。1.2 算法圖示假設(shè)我們的 n 個(gè)樣本點(diǎn)分布在圖中所示的二。從數(shù)據(jù)點(diǎn)的大致形狀可以看出它們大致聚為三個(gè) cluster，其中兩個(gè)緊湊一些，剩下那個(gè)松散一些，：我們的目的是為這些數(shù)據(jù)分組，以便能區(qū)分出屬于不同的簇的數(shù)據(jù)，給它們標(biāo)上不同的顏色，如圖：1.3 算法要點(diǎn)思想1.3.1通過(guò)迭代尋找 k 個(gè)類簇的一種劃分方案，使得用這 k 個(gè)類簇的均值來(lái)代表相應(yīng)各類樣本時(shí)所得的總體誤差最小。k 個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類之間盡可能的。k-means 算法的基礎(chǔ)是最小誤差平方和準(zhǔn)

3、則,其代價(jià)函數(shù)是：式中，c(i)表示第 i 個(gè)聚類的均值。各類簇內(nèi)的樣本越相似，其與該類均值間的誤差平方越小，對(duì)所有類所得到的誤差平方求和，即可驗(yàn)證分為 k 類時(shí)，各聚類是否是最優(yōu)的。上式的代價(jià)函數(shù)無(wú)法用的方法最小化，只能有迭代的方法。1.3.2 算法步驟圖解下圖展示了對(duì) n 個(gè)樣本點(diǎn)進(jìn)行 K-means 聚類的效果，這里 k 取 2。1.3.3 算法實(shí)現(xiàn)步驟k-means 算法是將樣本聚類成 k 個(gè)簇（cluster），其中 k 是用戶給定的，其求解過(guò)程非常直觀簡(jiǎn)單，具體算法描述如下：1)隨機(jī)選取 k 個(gè)聚類質(zhì)心點(diǎn)2)重復(fù)下面過(guò)程直到收斂 對(duì)于每一個(gè)樣例 i，計(jì)算其應(yīng)該屬于的類：對(duì)于每一個(gè)類

4、 j，重新計(jì)算該類的質(zhì)心：其偽代碼如下：*創(chuàng)建 k 個(gè)點(diǎn)作為初始的質(zhì)心點(diǎn)（隨機(jī)選擇）當(dāng)任意一個(gè)點(diǎn)的簇分配結(jié)果發(fā)生改變時(shí)對(duì)數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)點(diǎn)對(duì)每一個(gè)質(zhì)心計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)的距離將數(shù)據(jù)點(diǎn)分配到距離最近的簇對(duì)每一個(gè)簇，計(jì)算簇中所有點(diǎn)的均值，并將均值作為質(zhì)心2. Kmeans 分類算法 Python 實(shí)戰(zhàn)2.1 需求對(duì)給定的數(shù)據(jù)集進(jìn)行聚類本案例采用二維數(shù)據(jù)集，共 80 個(gè)樣本，有 4 個(gè)類。樣例如下：testSet.txt1.6589854.285136-3.4536873.4243214.838138-1.151539-5.379713-3.3621040.9725642.924086-3.567

5、9191.5316110.450614-3.302219-3.487105-1.7244322.6687591.594842-3.1564853.1911373.165506-3.999838-2.786837-3.0993544.2081872.984927-2.1233372.9433660.704199-0.479481-0.392370-3.9637042.8316671.574018-0.7901533.3431442.943496-3.3570752.2 python 代碼實(shí)現(xiàn)2.2.1 利用 numpy 手動(dòng)實(shí)現(xiàn)from numpy import * #加載數(shù)據(jù)def loadD

6、ataSet(fileName): dataMat = fr = open(fileName)for line in fr.readlines():curLine = line.strip().split(t)fltLine = map(float, curLine)#變成 float 類型dataMat.append(fltLine) return dataMat# 計(jì)算歐幾里得距離def distEclud(vecA, vecB):return sqrt(sum(power(vecA - vecB, 2)#構(gòu)建聚簇中心，取 k 個(gè)(此例中為 4)隨機(jī)質(zhì)心def randCent(dataS

7、et, k):n = shape(dataSet)1centroids = mat(zeros(k,n)#每個(gè)質(zhì)心有 n 個(gè)坐標(biāo)值，總共要 k 個(gè)質(zhì)心for j in range(n):minJ = min(dataSet:,j) maxJ = max(dataSet:,j)rangeJ = float(maxJ - minJ)centroids:,j = minJ + rangeJ * random.rand(k, 1)return centroids#k-means 聚類算法def kMeans(dataSet, k, distMeans =distEclud, createCent =

8、randCent): m = shape(dataSet)0clusterAssment = mat(zeros(m,2)#用于存放該樣本屬于哪類及質(zhì)心距離centroids = createCent(dataSet, k)clusterChanged = True while clusterChanged:clusterChanged = False; for i in range(m):minDist = inf; minIndex = -1; for j in range(k):distJI = distMeans(centroidsj,:, dataSeti,:) if distJI

9、minDist:minDist = distJI; minIndex = jif clusterAssmenti,0 != minIndex: clusterChanged = True; clusterAssmenti,: = minIndex,minDist*2print centroidsfor cent in range(k):ptsInClust = dataSetnonzero(clusterAssment:,0.A = cent)0# 去第一列等于 cent 的所有列centroidscent,: = mean(ptsInClust, axis = 0)return centro

10、ids, clusterAssment2.2.2 利用 scikili 庫(kù)實(shí)現(xiàn)Scikit-Learn 是基于 python 的學(xué)習(xí)模塊，基于 BSD 開源證。scikit-learn 的基本功能主要被分為六個(gè)部分，分類，回歸，聚類，數(shù)據(jù)降維，模型選擇，數(shù)據(jù)預(yù)處理。包括 SVM，決策樹，GBDT，KNN，KMEANS 等等Kmeans 在 scikit 包中即已有實(shí)現(xiàn)，只要將數(shù)據(jù)按照算法要求處理好，傳入相應(yīng)參數(shù)，即可直接調(diào)用其 kmeans 函數(shù)進(jìn)行聚類# kmeans: k-means cluster #from numpy import * import timeimport matplo

11、tlib.pyplot as plt # step 1:加載數(shù)據(jù)print step 1: load data. dataSet = fileIn = open(E:/Python/ml-data/kmeans/testSet.txt) for line in fileIn.readlines():lineArr = line.strip().split(t)dataSet.append(float(lineArr0), float(lineArr1) # step 2: 聚類print step 2: clustering. dataSet = mat(dataSet)k = 4centro

12、ids, clusterAssment = kmeans(dataSet, k) # step 3:顯示結(jié)果print step 3: show the result.showCluster(dataSet, k, centroids, clusterAssment)2.2.3 運(yùn)行結(jié)果不同的類用不同的顏色來(lái)表示，其中的大菱形是對(duì)應(yīng)類的均值質(zhì)心點(diǎn)。3、Kmeans 算法補(bǔ)充3.1 kmeans 算法缺點(diǎn)k-means 算法比較簡(jiǎn)單，但也有幾個(gè)比較大的缺點(diǎn)：（1）k 值的選擇是用戶指定的，不同的 k 得到的結(jié)果會(huì)有挺大的不同，如下圖所示，左邊是 k=3 的結(jié)果，這個(gè)就太稀疏了，k=5 的結(jié)果，可以看到紅色菱形和的那個(gè)簇其實(shí)是可以再劃分成兩個(gè)簇的。而右圖是菱形這兩個(gè)簇應(yīng)該是可以合并成一個(gè)簇的：（2）對(duì) k 個(gè)初始質(zhì)心的選擇比較敏感，容易陷入局部最小值。例如，我們上面的算法運(yùn)行的時(shí)候，有可能會(huì)得到不同的結(jié)果，如下面這兩種情況。K-means 也是收斂了，只是收斂到了局部最小值：（3）存在局限性，如下面這種非球狀