機(jī)器學(xué)習(xí)kmeans聚類算法與應(yīng)用

機(jī)器學(xué)習(xí)算法day02_Kmeans聚類算法及應(yīng)用課程大綱Kmeans聚類算法原理Kmeans聚類算法概述Kmeans聚類算法圖示Kmeans聚類算法要點(diǎn)Kmeans聚類算法案例需求用Numpy手動(dòng)實(shí)現(xiàn)用Scikili機(jī)器學(xué)習(xí)算法庫實(shí)現(xiàn)Kmeans聚類算法補(bǔ)充算法缺點(diǎn)改進(jìn)思路課程目標(biāo)：理解Kmeans聚類算法的核心思想理解Kmeans聚類算法的代碼實(shí)現(xiàn)掌握Kmeans聚類算法的應(yīng)用步驟：數(shù)據(jù)處理、建模、運(yùn)算和結(jié)果判定1.Kmeans聚類算法原理1.1概述K-means算法是集簡單和經(jīng)典于一身的基于距離的聚類算法采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似度就越大。該算法認(rèn)為類簇是由距離靠近的對象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(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核心思想通過迭代尋找k個(gè)類簇的一種劃分方案，使得用這k個(gè)類簇的均值來代表相應(yīng)各類樣本時(shí)所得的總體誤差最小。k個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

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

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

{

對于每一個(gè)樣例i，計(jì)算其應(yīng)該屬于的類：

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

對數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)點(diǎn)

對每一個(gè)質(zhì)心

計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)的距離

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

對每一個(gè)簇，計(jì)算簇中所有點(diǎn)的均值，并將均值作為質(zhì)心2.Kmeans分類算法Python實(shí)戰(zhàn)2.1需求對給定的數(shù)據(jù)集進(jìn)行聚類本案例采用二維數(shù)據(jù)集，共80個(gè)樣本，有4個(gè)類。樣例如下：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代碼實(shí)現(xiàn)2.2.1利用numpy手動(dòng)實(shí)現(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#計(jì)算歐幾里得距離defdistEclud(vecA,vecB):returnsqrt(sum(power(vecA-vecB,2)))#構(gòu)建聚簇中心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)))#用于存放該樣本屬于哪類及質(zhì)心距離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庫實(shí)現(xiàn)Scikit-Learn是基于python的機(jī)器學(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-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:顯示結(jié)果print"step3:showtheresult..."showCluster(dataSet,k,centroids,clusterAssment)2.2.3運(yùn)行結(jié)果不同的類用不同的顏色來表示，其中的大菱形是對應(yīng)類的均值質(zhì)心點(diǎn)。Kmeans算法補(bǔ)充3.1kmeans算法缺點(diǎn)k-means算法比擬簡單，但也有幾個(gè)比擬大的缺點(diǎn)：〔1〕k值的選擇是用戶指定的，不同的k得到的結(jié)果會有挺大的不同，如下列圖所示，左邊是k=3的結(jié)果，這個(gè)就太稀疏了，藍(lán)色的那個(gè)簇其實(shí)是可以再劃分成兩個(gè)簇的。而右圖是k=5的結(jié)果，可以看到紅色菱形和藍(lán)色菱形這兩個(gè)簇應(yīng)該是可以合并成一個(gè)簇的：〔2〕對k個(gè)初始質(zhì)心的選擇比擬敏感，容易陷入局部最小值。例如，我們上面的算法運(yùn)行的時(shí)候，有可能會得到不同的結(jié)果，如下面這兩種情況。K-means也是