機器學習kmeans聚類算法與應用

機器學習算法day02_Kmeans聚類算法及應用課程大綱Kmeans聚類算法原理Kmeans聚類算法概述Kmeans聚類算法圖示Kmeans聚類算法要點Kmeans聚類算法案例需求用Numpy手動實現(xiàn)用Scikili機器學習算法庫實現(xiàn)Kmeans聚類算法補充算法缺點改進思路課程目標：理解Kmeans聚類算法的核心思想理解Kmeans聚類算法的代碼實現(xiàn)掌握Kmeans聚類算法的應用步驟：數(shù)據(jù)處理、建模、運算和結果判定1.Kmeans聚類算法原理1.1概述K-means算法是集簡單和經(jīng)典于一身的基于距離的聚類算法采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。該算法認為類簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。1.2算法圖示假設我們的n個樣本點分布在圖中所示的二維空間。從數(shù)據(jù)點的大致形狀可以看出它們大致聚為三個cluster，其中兩個緊湊一些，剩下那個松散一些，如下圖：我們的目的是為這些數(shù)據(jù)分組，以便能區(qū)分出屬于不同的簇的數(shù)據(jù)，給它們標上不同的顏色，如圖：1.3算法要點1.3.1核心思想通過迭代尋找k個類簇的一種劃分方案，使得用這k個類簇的均值來代表相應各類樣本時所得的總體誤差最小。k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

k-means算法的根底是最小誤差平方和準那么,其代價函數(shù)是：

式中，μc(i)表示第i個聚類的均值。各類簇內的樣本越相似，其與該類均值間的誤差平方越小，對所有類所得到的誤差平方求和，即可驗證分為k類時，各聚類是否是最優(yōu)的。上式的代價函數(shù)無法用解析的方法最小化，只能有迭代的方法。1.3.2算法步驟圖解下列圖展示了對n個樣本點進行K-means聚類的效果，這里k取2。1.3.3算法實現(xiàn)步驟k-means算法是將樣本聚類成k個簇〔cluster〕，其中k是用戶給定的，其求解過程非常直觀簡單，具體算法描述如下：隨機選取k個聚類質心點重復下面過程直到收斂

{

對于每一個樣例i，計算其應該屬于的類：

對于每一個類j，重新計算該類的質心：}其偽代碼如下：********************************************************************創(chuàng)立k個點作為初始的質心點〔隨機選擇〕當任意一個點的簇分配結果發(fā)生改變時

對數(shù)據(jù)集中的每一個數(shù)據(jù)點

對每一個質心

計算質心與數(shù)據(jù)點的距離

將數(shù)據(jù)點分配到距離最近的簇

對每一個簇，計算簇中所有點的均值，并將均值作為質心2.Kmeans分類算法Python實戰(zhàn)2.1需求對給定的數(shù)據(jù)集進行聚類本案例采用二維數(shù)據(jù)集，共80個樣本，有4個類。樣例如下：testSet.txt1.658985 4.285136-3.453687 3.4243214.838138 -1.151539-5.379713 -3.3621040.972564 2.924086-3.567919 1.5316110.450614 -3.302219-3.487105 -1.7244322.668759 1.594842-3.156485 3.1911373.165506 -3.999838-2.786837 -3.0993544.208187 2.984927-2.123337 2.9433660.704199 -0.479481-0.392370 -3.9637042.831667 1.574018-0.790153 3.3431442.943496 -3.3570752.2python代碼實現(xiàn)2.2.1利用numpy手動實現(xiàn)fromnumpyimport*#加載數(shù)據(jù)defloadDataSet(fileName):dataMat=[]fr=open(fileName)forlineinfr.readlines():curLine=line.strip().split('\t')fltLine=map(float,curLine)#變成float類型dataMat.append(fltLine)returndataMat#計算歐幾里得距離defdistEclud(vecA,vecB):returnsqrt(sum(power(vecA-vecB,2)))#構建聚簇中心defrandCent(dataSet,k):n=shape(dataSet)[1]centroids=mat(zeros((k,n)))forjinrange(n):minJ=min(dataSet[:,j])maxJ=max(dataSet[:,j])rangeJ=float(maxJ-minJ)centroids[:,j]=minJ+rangeJ*random.rand(k,1)returncentroids#k-means聚類算法defkMeans(dataSet,k,distMeans=distEclud,createCent=randCent):m=shape(dataSet)[0]clusterAssment=mat(zeros((m,2)))#用于存放該樣本屬于哪類及質心距離centroids=createCent(dataSet,k)clusterChanged=TruewhileclusterChanged:clusterChanged=False;foriinrange(m):minDist=inf;minIndex=-1;forjinrange(k):distJI=distMeans(centroids[j,:],dataSet[i,:])ifdistJI<minDist:minDist=distJI;minIndex=jifclusterAssment[i,0]!=minIndex:clusterChanged=True;clusterAssment[i,:]=minIndex,minDist**2printcentroidsforcentinrange(k):ptsInClust=dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#去第一列等于cent的所有列centroids[cent,:]=mean(ptsInClust,axis=0)returncentroids,clusterAssment2.2.2利用scikili庫實現(xiàn)Scikit-Learn是基于python的機器學習模塊，基于BSD開源許可證。scikit-learn的根本功能主要被分為六個局部，分類，回歸，聚類，數(shù)據(jù)降維，模型選擇，數(shù)據(jù)預處理。包括SVM，決策樹，GBDT，KNN，KMEANS等等Kmeans在scikit包中即已有實現(xiàn)，只要將數(shù)據(jù)按照算法要求處理好，傳入相應參數(shù)，即可直接調用其kmeans函數(shù)進行聚類##################################################kmeans:k-meanscluster#################################################fromnumpyimport*importtimeimportmatplotlib.pyplotasplt##step1:加載數(shù)據(jù)print"step1:loaddata..."dataSet=[]fileIn=open('E:/Python/ml-data/kmeans/testSet.txt')forlineinfileIn.readlines(): lineArr=line.strip().split('\t') dataSet.append([float(lineArr[0]),float(lineArr[1])])##step2:聚類print"step2:clustering..."dataSet=mat(dataSet)k=4centroids,clusterAssment=kmeans(dataSet,k)##step3:顯示結果print"step3:showtheresult..."showCluster(dataSet,k,centroids,clusterAssment)2.2.3運行結果不同的類用不同的顏色來表示，其中的大菱形是對應類的均值質心點。Kmeans算法補充3.1kmeans算法缺點k-means算法比擬簡單，但也有幾個比擬大的缺點：〔1〕k值的選擇是用戶指定的，不同的k得到的結果會有挺大的不同，如下列圖所示，左邊是k=3的結果，這個就太稀疏了，藍色的那個簇其實是可以再劃分成兩個簇的。而右圖是k=5的結果，可以看到紅色菱形和藍色菱形這兩個簇應該是可以合并成一個簇的：〔2〕對k個初始質心的選擇比擬敏感，容易陷入局部最小值。例如，我們上面的算法運行的時候，有可能會得到不同的結果，如下面這兩種情況。K-means也是