- <span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">今天繼續(xù)和小伙伴們分享聚類算法和R語言的實(shí)現(xiàn)，上篇和大家分享了聚類中的距離、類間距離和最古典的層次聚類法，今天和大家分享幾個(gè)動(dòng)態(tài)聚類算法。</span>
首先和大家分享被評為十大數(shù)據(jù)挖掘算法之一的K-means 算法（K為分類的個(gè)數(shù)，mean為平均值，該算法的難點(diǎn)即為K的指點(diǎn)）
- Step1：選擇K個(gè)點(diǎn)作為初始質(zhì)心；
- Step2：將剩余每個(gè)點(diǎn)指派到最近的質(zhì)心，形成K個(gè)簇（聚類）；
- Step3：重新計(jì)算簇的質(zhì)心（坐標(biāo)平均值）；
- Step4：重復(fù)2-3直至質(zhì)心不發(fā)生變化；
接下來看看R語言如何實(shí)現(xiàn)K-means:
- X=iris[,1:4]
- km=kmeans(X,3)#數(shù)據(jù)庫+分類數(shù)
可見R語言的強(qiáng)大性，但是K的指定確實(shí)很有技巧，可以先做一次層次聚類法，得出K取多少會相對合適；
K-means優(yōu)點(diǎn)：
有效率，且不容易受初始值選擇的影響；
缺點(diǎn)：
1、 不能處理非球形的簇；
2、 不能處理不同尺度，不同密度的簇（聚類的球大小層次不齊）；
3、 離群值可能會有較大的干擾（因此要先剔除）
基于密度的方法：DBSCAN（Density-Based Spatial Clustering of Applications with Noise）
前面提到的K-means比較適合球形分布的案例，對于下圖所示的點(diǎn)群則效果不好，接下來引入另一種聚類方法來解決這類問題。
首先解釋下基本的概念：
r-鄰域：給定點(diǎn)半徑r內(nèi)的區(qū)域
核心點(diǎn)：如果一個(gè)點(diǎn)的r-鄰域至少包含最少數(shù)目M個(gè)點(diǎn)，則稱該點(diǎn)為核心點(diǎn)
直接密度可達(dá)：如果點(diǎn)p在核心點(diǎn)q的r-鄰域內(nèi)，則稱p是從q出發(fā)可以直接密度可達(dá)
如果存在點(diǎn)鏈p1,p2, …, pn，p1=q，pn=p，pi+1是從pi關(guān)于r和M直接密度可達(dá)，則稱點(diǎn)p是從q關(guān)于r和M密度可達(dá)的（見下圖）,注意密度可達(dá)是單向的。
Ps:密度可達(dá)即可以納入同一類；
如果樣本集D中存在點(diǎn)o，使得點(diǎn)p、q是從o關(guān)于 r和M密度可達(dá)的，那么點(diǎn)p、q是關(guān)于r和M密度相連（見下圖）
DBSCAN基本算法：
- Step1：指定合適的 r 和 M；
- Step2： 計(jì)算所有的樣本點(diǎn)，如果點(diǎn)p的r鄰域里有超過M個(gè)點(diǎn)，則創(chuàng)建一個(gè)以p為核心點(diǎn)的新簇；
- Step3： 反復(fù)尋找這些核心點(diǎn)直接密度可達(dá)（之后可能是密度可達(dá)）的點(diǎn)，將其加入到相應(yīng)的簇，對于核心點(diǎn)發(fā)生“密度相連”狀況的簇，給予合并
- Step4 ：當(dāng)沒有新的點(diǎn)可以被添加到任何簇時(shí)，算法結(jié)束
- Ps：DBSCAN對用戶定義的參數(shù)很敏感，細(xì)微的不同都可能導(dǎo)致差別很大的結(jié)果，而參數(shù)的選定無規(guī)律可循，只能靠經(jīng)驗(yàn)確定。
- install.packages(fpc)
- library(fpc)
- iris.data<-iris[,-5]
- ds<-dbscan(iris.data,1.5,MinPts=30,scale=TRUE,showplot=TRUE,method="raw")
結(jié)果如下圖：
|
