聚类分析与相关算法(Kmeans等)详解
聚類分析與相關(guān)算法詳解
- 1 距離度量
- 1.1歐幾里得距離定義
- 1.2其他距離度量的補(bǔ)充
- 1.3余弦距離
- 1.4簡(jiǎn)單匹配系數(shù)
- 1.5jaccard系數(shù)
- 1.6海明距離
- 2 聚類問(wèn)題
- 2.1非監(jiān)督學(xué)習(xí)中的Kmeans算法
- 2.2K-means算法 --均值作為聚類中心點(diǎn)
- 3 聚類的其他算法
- 3.1K-medoids聚類簡(jiǎn)介 --中位數(shù)作為聚類中心點(diǎn)
- 3.2層次聚類 --沒(méi)有中心點(diǎn)
- 3.3基于密度的聚類(DBSCAN)
- 3.4高斯混合聚類
- 4 總結(jié)
- 5 API補(bǔ)充
- 5.1kmeans算法
- 5.2DBSCAN算法
- 5.3層次聚類
? 聚類是一種無(wú)監(jiān)督學(xué)習(xí)技術(shù)(包括 聚類,屬性約減的 PCA),可以在事先不知道正確結(jié)果(即無(wú)類標(biāo)簽,或預(yù)測(cè)輸出值)的情況下,發(fā)現(xiàn)數(shù)據(jù)本身蘊(yùn)含的結(jié)構(gòu)等信息
?聚類的 本質(zhì)是一種分組方法,分組的標(biāo)準(zhǔn)是 組內(nèi)的樣本之間相似度盡可能高,而 組間樣本之間的相似度盡可能低
?可將聚類理解為:對(duì)對(duì)象集合分組的過(guò)程
1 距離度量
1.1歐幾里得距離定義
1.2其他距離度量的補(bǔ)充
p =1 曼哈頓距離
p=2 歐幾里得距離
1.3余弦距離
余弦相似度也稱為余弦距離
余弦相似度為1,則x,y之間的夾角為0度,此時(shí)兩個(gè)向量完全一樣,如果余弦相似度為0,則x,y之間的夾角為90度,說(shuō)明兩個(gè)向量不包含相同的詞
1.4簡(jiǎn)單匹配系數(shù)
簡(jiǎn)單匹配系數(shù)度量的是最簡(jiǎn)單的二元屬性(屬性可以理解為特征)的對(duì)象(可以理解為向量)之間的相似性度量
所以要度量二元屬性的對(duì)象,對(duì)象中的二元屬性個(gè)數(shù)應(yīng)該相同
假設(shè)x,y兩個(gè)數(shù)據(jù)對(duì)象,都由n個(gè)二元屬性組成,這樣的兩個(gè)對(duì)象做相似性度量可以生成四個(gè)量:
?此時(shí)簡(jiǎn)單匹配數(shù)SMC的定義:
?度量值不匹配的屬性個(gè)數(shù):
實(shí)例:
1.5jaccard系數(shù)
?當(dāng)分析購(gòu)買商品數(shù)據(jù)時(shí),由于未被購(gòu)買的商品數(shù)量遠(yuǎn)遠(yuǎn)大于被其購(gòu)買的商品數(shù)量,像上述的SMC計(jì)算公式會(huì)判斷所有的事務(wù)都是類似的,所以引出jaccard系數(shù)來(lái)處理僅包含非對(duì)稱二元屬性的對(duì)象.
1.6海明距離
?在信息編碼中,兩個(gè)合法(長(zhǎng)度相同)代碼(字符串/int/float類型)對(duì)應(yīng)位上編碼不同的位數(shù)稱為碼距,又叫海明距離
它的意義:就是將一個(gè)字符串替換成另一個(gè)字符串所需要替換的字符個(gè)數(shù)
它的作用:
用于編碼的檢錯(cuò)與糾錯(cuò),為了檢測(cè)d個(gè)1位錯(cuò)誤,需要一個(gè)海明距離為d+1的方案.因?yàn)樵谶@樣的編碼方案中,d個(gè)1位的錯(cuò)誤不可能將一個(gè)有效碼字改編成另一個(gè)有效碼字.當(dāng)接收方看到一個(gè)無(wú)效碼字時(shí),他就知道已經(jīng)發(fā)生了傳輸錯(cuò)誤.類似的為了糾正d個(gè)1位錯(cuò)誤,需要一個(gè)距離為2d+1的編碼方案,因?yàn)樵谶@樣的編碼方案中,合法碼字之間的距離足夠遠(yuǎn),因而即使發(fā)生了d為變化,則還是原來(lái)的碼字離最近,從而可以唯一確定原來(lái)的碼字,達(dá)到糾錯(cuò)的目的.
2 聚類問(wèn)題
2.1非監(jiān)督學(xué)習(xí)中的Kmeans算法
?聚類屬于非監(jiān)督學(xué)習(xí),無(wú)類別標(biāo)簽,基于原型的算法
?原理就是相同類別的通過(guò)屬性之間的相似性聚集在一起,算法中并未涉及類別標(biāo)記的問(wèn)題.
2.2K-means算法 --均值作為聚類中心點(diǎn)
CLustering中的經(jīng)典算法,數(shù)據(jù)挖掘十大算法之一
算法接受參數(shù)K(在實(shí)際生產(chǎn)環(huán)境中一般根據(jù)業(yè)務(wù)經(jīng)驗(yàn)設(shè)定),然后將事先輸入的n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類,得到的聚類滿足:同一聚類中對(duì)象的相似性高,不同聚類中對(duì)象的相似度低
算法思想:
?以空間中K個(gè)點(diǎn)為中心進(jìn)行聚類,對(duì)最靠近他們的對(duì)象歸類(這里用到了距離度量,度量之前要先對(duì)對(duì)象中的特征做特征工程使得特征值滿足算法的需求).通過(guò)迭代的方法,逐次更新各個(gè)聚類中心的值(它是一個(gè)點(diǎn),每一個(gè)對(duì)象都理解為一個(gè)點(diǎn)),直到得到最好的聚類結(jié)果(迭代之后K個(gè)聚類重心的值不再發(fā)生變化/或變化的范圍小于設(shè)定的閾值)
?變化的范圍:當(dāng)前聚類中的對(duì)象在經(jīng)過(guò)一次迭代移動(dòng)到其他組的個(gè)數(shù)的范圍(暫時(shí)的理解)
算法描述:
?1.隨機(jī)選取k個(gè)聚類重心(值)
?2.在第j次迭代中,對(duì)任意一個(gè)樣本,求其到所有k個(gè)聚類重心的距離(這里使用了距離度量),將該樣本歸到距離最短的那個(gè)聚類中心點(diǎn)對(duì)應(yīng)的聚類中
?3.訓(xùn)練完樣本數(shù)據(jù)后得到k個(gè)聚類,利用均值等方法更新每一個(gè)聚類的重心(后面留意一下怎么更新的)
?均值更新聚類中心點(diǎn):
??假如第n個(gè)聚類重心對(duì)應(yīng)的聚類中有c個(gè)樣本,每個(gè)樣本中3個(gè)特征,把所有c個(gè)樣本中的特征對(duì)應(yīng)相加,然后除3,得到了更新之后的第n個(gè)聚類重心
?4.對(duì)所有的k個(gè)聚類重心,如果利用2,3的迭代法更新后,各個(gè)重心保持不變(或變化的范圍小于閾值),則迭代結(jié)束,否則繼續(xù)迭代.
總結(jié):
?簡(jiǎn)單來(lái)說(shuō),K-Means是一種基于屬性/特征將對(duì)象分類或分組為K的算法組數(shù),K是正整數(shù)
?K均值算法將會(huì)執(zhí)行以下三個(gè)步驟,直到收斂
??1.確定初始重心坐標(biāo)
??2.確定每個(gè)樣本與重心的距離
??3.根據(jù)最小距離對(duì)樣本進(jìn)行歸類,更新聚類重心然后進(jìn)行迭代
Means性能評(píng)價(jià)指標(biāo)
一種度量K-Means算法的聚類效果的指標(biāo):誤差平方和SSE(Sum of Squared Error)
:表明用的是均值更新重心的方式,ci是每個(gè)聚類的重心
:一個(gè)聚類中,每個(gè)樣本與重心的差的平方
所以SSE求解的是:所有聚類的重心分別與對(duì)應(yīng)聚類中所有樣本差的平方和
直觀的說(shuō)SSE越小,表名樣本越接近他們的重心,聚類效果越好,因?yàn)閷?duì)誤差取了平方,更加重視那些遠(yuǎn)離重心的點(diǎn)
?可證明使簇的SSE最小的重心是均值:
在聚類算法的性能評(píng)價(jià)中,還有ARI指數(shù)(Adjusted Rand Index),值越接近1,性能越好
K-Means算法特點(diǎn)
優(yōu)點(diǎn):速度快,簡(jiǎn)單
缺點(diǎn):最終結(jié)果與初始點(diǎn)的選擇有關(guān),容易陷入局部最優(yōu)
?K均值中的K是現(xiàn)實(shí)給定的,而這個(gè)K值的選取往往是根據(jù)業(yè)務(wù)經(jīng)驗(yàn)選取的
?K均值的聚類算法需要不斷的進(jìn)行樣本的分類調(diào)整,不斷的計(jì)算調(diào)整后的聚類重心,當(dāng)數(shù)據(jù)量大的時(shí)候,算法開(kāi)銷很大
?K均值是求得局部最優(yōu)的算法,所以對(duì)于初始化時(shí)選取的k個(gè)聚類重心比較敏感,不同的重心選取策略可能得到不同的結(jié)果.
3 聚類的其他算法
3.1K-medoids聚類簡(jiǎn)介 --中位數(shù)作為聚類中心點(diǎn)
K-medoids選擇數(shù)據(jù)集中有代表性的樣本(而不是均值)來(lái)代表整個(gè)簇,即選取靠近中心點(diǎn)(medoids)的那個(gè)樣本(中位數(shù))代表整個(gè)簇
K-medoids的特點(diǎn):
?是對(duì)kmeans的改進(jìn),由于k均值對(duì)噪聲,孤立點(diǎn)數(shù)據(jù)時(shí)敏感的,為了修改這種敏感行(距離矩陣的敏感行),將kmeans中的均值作為更新點(diǎn),修改為聚類中位置最中心的那個(gè)對(duì)象,即中心點(diǎn).
與kmeans的區(qū)別:
?k-medoids中心點(diǎn)的選取限制在當(dāng)前簇中所包含的數(shù)據(jù)點(diǎn)集合中.一個(gè)是數(shù)據(jù)樣本的均值,一個(gè)是樣本數(shù)據(jù)的中位數(shù),兩者的區(qū)別在于平均值的選取是連續(xù)空間中的任意值,后者只能在樣本給定的點(diǎn)中選擇
這樣做的優(yōu)勢(shì)之處:
?k-medoids不容易受到誤差之類的原因產(chǎn)生離群點(diǎn)現(xiàn)象
?k均值要求數(shù)據(jù)只能落在二維的歐式空間中,但并不是所有的數(shù)據(jù)都可以滿足這樣的需求,特別是類別型的變量用歐氏距離是無(wú)法適用的
存在的問(wèn)題:
?k-medoids:也會(huì)陷入局部最優(yōu)解
?K-medoids選取初值點(diǎn)需要枚舉每個(gè)點(diǎn),并要求他到所有點(diǎn)的距離之和,復(fù)雜度為O(N2),kmeans僅計(jì)算一個(gè)平均值,復(fù)雜度為O(N)
3.2層次聚類 --沒(méi)有中心點(diǎn)
?上述的兩種方式都需要手動(dòng)的選取類的初始重心,層次聚類是一種樹(shù)狀的聚類算法,反復(fù)將數(shù)據(jù)進(jìn)行分類和聚合,以形成一個(gè)層次序列的聚類問(wèn)題,層次的基本方法可以分為:凝聚與分裂—這種方式?jīng)]有重心
?凝聚是由下向上構(gòu)造樹(shù)的方法,將每一個(gè)對(duì)象作為一個(gè)類,然后合并這些原子聚類為越來(lái)越大的聚類,直到所有的對(duì)象都在一個(gè)聚類中,或者滿足某個(gè)終結(jié)條件(達(dá)到聚類數(shù)目)
?分裂是由上向下的方法,它的策略是將所有的對(duì)象都置于一個(gè)聚類中,然后逐漸細(xì)分為越來(lái)越小的聚類,直到每個(gè)對(duì)象自成一聚類,或者達(dá)到某個(gè)結(jié)束條件
算法原理:
假設(shè)有N個(gè)待聚類樣本,對(duì)于層次聚類來(lái)說(shuō),步驟:
?1.(初始化)把每個(gè)樣本歸為一類,計(jì)算每?jī)蓚€(gè)類之間的距離,也就是各個(gè)樣本之間的相似度
?2.尋找各個(gè)類之間相似度最近的兩個(gè)類,把他們歸為一類(這樣類的總數(shù)就少了一個(gè))
?3.重新計(jì)算新生成的這個(gè)類(均值?不是,后面會(huì)介紹)與各個(gè)剩下的類(舊類)之間的相似度
?4.重復(fù)2,3直到所有的樣本點(diǎn)都?xì)w為一類,結(jié)束
如圖:
?假設(shè)有5個(gè)待聚類樣本,把每個(gè)樣本歸為一類(1,2,3,4,5),計(jì)算每?jī)蓚€(gè)類之間的距離,得到樣本1,2是距離最近所對(duì)應(yīng)的兩個(gè)樣本,將1,2歸為一類(均值?不是,看后面的解答)得到類6,然后計(jì)算3,4,5,6之間的距離,得到類7,然后迭代下去最后將所有的類歸為類9,迭代結(jié)束
?迭代終止的條件:
??1.所有的類都?xì)w為一類
2??.在第二步上設(shè)置一個(gè)閾值,當(dāng)最近的兩個(gè)類之間的距離大于這個(gè)閾值,則認(rèn)為迭代可以終止
如何判斷兩個(gè)類之間的相似度(怎么求距離度量)有以下幾種方法
?1.SingleLinkage:又叫nearest-neighbor,就是取兩個(gè)類中距離最近的兩個(gè)樣本(分別來(lái)自兩個(gè)聚類)的距離作為這兩個(gè)聚類的距離
?這種方式容易造成一種叫做chaining的效果,兩個(gè)cluster明明從”大局”上看離得比較遠(yuǎn),但是由于其中個(gè)別點(diǎn)距離比較近就被合并了,并且這樣合并之后的chaining效應(yīng)會(huì)進(jìn)一步擴(kuò)大,最后會(huì)得到比較松散的cluster
?2.CompleteLinkage:與SingleLinkage相反,取兩個(gè)聚類中相互距離最遠(yuǎn)的兩個(gè)點(diǎn)作為聚類之間的距離
?這種方式兩個(gè)cluster之間即使已經(jīng)很接近了,但是只有有不配合的點(diǎn)存在,就頑固到底,老死不相合并.這兩種相似度的定義方法的共同問(wèn)題就是只考慮額某個(gè)特點(diǎn)得數(shù)據(jù),而沒(méi)有考慮類中數(shù)據(jù)的整體特點(diǎn)
?3.Average-linkage:把兩個(gè)集合中的所有點(diǎn)兩兩的距離全都算出來(lái),然后求一個(gè)平均值作為兩個(gè)集合的距離
?4.average-linkage:取兩個(gè)集合中所有點(diǎn)兩兩的距離的中值(中位數(shù)),與去平均值相比更加能夠解除個(gè)別偏離樣本對(duì)結(jié)果的干擾
基于原型的聚類 --層次聚類
?優(yōu)勢(shì)1:它能夠使得我們繪制出樹(shù)狀圖(基于二叉層次聚類的可視化)
?優(yōu)勢(shì)2:不需要事先指定簇?cái)?shù)量
3.3基于密度的聚類(DBSCAN)
?聚類中除了上述的kmeans的聚類屬于基于原型的聚類,kmedoids是基于劃分的聚類,另外還有層次聚類和基于密度的聚類.基于原型意味著每個(gè)簇都對(duì)應(yīng)一個(gè)模型(模型是選取中心點(diǎn)的規(guī)則:如均值).
?基于密度的聚類是基于距離的聚類的變型.純粹的基于距離的聚類只能發(fā)現(xiàn)球狀的分組,而在發(fā)現(xiàn)任意形狀的簇上遇到了困難.
概念:
?核心對(duì)象:如果給定對(duì)象E領(lǐng)域內(nèi)的樣本點(diǎn)個(gè)數(shù)大于等于設(shè)定的閾值,則稱該對(duì)象為核心對(duì)象
?直接密度可達(dá):對(duì)于樣本集合D,如果樣本點(diǎn)2在1的E領(lǐng)域內(nèi),并且1為核心對(duì)象,那么對(duì)象2從對(duì)象1(核心)直接密度可達(dá)
&emsp==;密度可達(dá)==:對(duì)于樣本集合D,給定一串樣本點(diǎn)p1,p2…pn, 假如對(duì)象pi從pi-1直接密度可達(dá),那么對(duì)象pn從對(duì)象p1密度可達(dá)(相當(dāng)于密度直接可達(dá)的間接傳遞,簡(jiǎn)單的說(shuō)就是p1雖然從對(duì)象pn直接密度不可達(dá),但是密度可達(dá))
?密度相連:對(duì)于樣本集合D中的任意一點(diǎn)2,如果存在對(duì)象1到對(duì)象2密度可達(dá),并且對(duì)象3到對(duì)象2密度可達(dá),那么對(duì)象1到對(duì)象2密度相連(密度可達(dá)的間接傳遞)
算法思路:
?1.從數(shù)據(jù)中抽出一個(gè)未處理(還沒(méi)有歸類)的樣本
?2.統(tǒng)計(jì)該樣本周圍半徑E范圍內(nèi)的樣本數(shù)量,如果小于閾值,則該點(diǎn)為噪聲點(diǎn).回到步驟1繼續(xù)處理.
?3.如果大于閾值,則該點(diǎn)稱為一個(gè)新簇的核心點(diǎn),將所有從該點(diǎn)密度可達(dá)的點(diǎn)加入到當(dāng)前新簇中.最后由一個(gè)核心對(duì)象和其密度可達(dá)的所有對(duì)象構(gòu)成一個(gè)聚類
?4.重復(fù)算法過(guò)程,直到所有樣本都被處理
A點(diǎn)分別與B,C點(diǎn)密度可達(dá)
B,C點(diǎn)之間密度相連
DBSCAN算法的最大特點(diǎn)就是:
?抗噪聲干擾
?可以發(fā)現(xiàn)任意形狀的聚類
3.4高斯混合聚類
?高斯混合聚類就是通過(guò)概率模型表示聚類原型,和K均值都是基于原型的聚類(假設(shè)聚類結(jié)構(gòu)能夠通過(guò)一組原型或模型刻畫)
?這塊還沒(méi)弄懂.
4 總結(jié)
?在實(shí)際的應(yīng)用中,對(duì)于給定的數(shù)據(jù)集,往往不太確定使用哪種算法是最為合適的,特別是面對(duì)難以或者無(wú)法進(jìn)行可視化處理的高維數(shù)據(jù)集.另外,一個(gè)好的聚類算法并不是僅僅依賴與算法及其超參數(shù)的調(diào)整,相反,選擇合適的距離度量標(biāo)準(zhǔn)和專業(yè)的領(lǐng)域知識(shí)在實(shí)驗(yàn)設(shè)定的應(yīng)用可能很有用
5 API補(bǔ)充
5.1kmeans算法
?from sklearn.cluster import KMeans
Parameters:
??n_clusters:int類型,分類簇的數(shù)量 默認(rèn)值為8
??max_iter:int類型,最大迭代次數(shù) 默認(rèn)值為300
??n_init:int類型,指定K均值算法運(yùn)行的次數(shù)
??init:初始均值向量,取值為:”k-meas++”,”random”,an ndarray
??precompute_distances:是否提前計(jì)算好樣本之間的距離
??tol:float類型,算法收斂的閾值 默認(rèn)值le-4
??n_jobs:int類型,指定CPU的數(shù)量, 為什么我的只能指定為1
??random_state:設(shè)置了之后每次切分的數(shù)據(jù)內(nèi)容是相同的
?Attributes:
??cluster_centers:給出分類簇的均值向量(重心)
??labels_:給出每個(gè)樣本所屬簇的標(biāo)記(0,1…)
??inertia_:float類型,給出每個(gè)樣本距離他們各自最近的簇中心的距離,然后求和
?mehtods:
??==fit(X,y)==訓(xùn)練模型
??fit_predict(X,y);訓(xùn)練模型并預(yù)測(cè)每個(gè)樣本點(diǎn)所屬的簇,等價(jià)于先調(diào)用fit方法,再調(diào)用predict方法
??predict(X):預(yù)測(cè)樣本所屬的簇
??score(X,y):給出樣本距離各個(gè)簇中心偏移量的相反數(shù) 是屬性inertia相反數(shù)
5.2DBSCAN算法
?Parameters:
??eps:float類型,半徑 用于確定領(lǐng)域大小
??min_sample:int類型, MinPts:用于判定核心對(duì)象
??metric:string or Callable類型,用于計(jì)算距離
??algorithm:{“auto”,”ball_tree”,”kd_tree”,”brute”} ,用于計(jì)算兩個(gè)點(diǎn)之間的距離找到最近鄰的點(diǎn)
??leaf_size:int類型,BallTree,KDTree樹(shù)的參數(shù),葉子節(jié)點(diǎn)的個(gè)數(shù), 默認(rèn)為30
??random_state:保證每次run時(shí)對(duì)數(shù)據(jù)集切分后的內(nèi)容與前面幾次切分的都相同
?Attributes:
??core_sample_indices:核心樣本在原始訓(xùn)練集中的位置
??components_:核心樣本點(diǎn)的一個(gè)副本
??labels_:每個(gè)樣本所屬的簇標(biāo)簽
?Methods:
??fit(X,y):訓(xùn)練模型
??fit_predict(X,y):訓(xùn)練模型并預(yù)測(cè)每個(gè)樣本點(diǎn)所屬的簇,等價(jià)于先調(diào)用fit方法,再調(diào)用predict方法
5.3層次聚類
?from sklearn.cluster import AgglomerativeClustering
?Parameters:
??n_clusters:指定分類簇的數(shù)量 默認(rèn)為2
??affinity:string類型,用于計(jì)算距離 默認(rèn)值”euclidean” 歐幾里得
??memory:用于緩存輸出結(jié)果,默認(rèn)不緩存
??linkage:{“ward”,”complete”,”average”}, 表示使用哪種方式作為聚類之間的距離,默認(rèn)值是”ward”
??“ward”:SingleLinkage
??“complete”:CompleteLinkage
??“average”:Average-linkage:
?Attributes:
??labels_:每個(gè)樣本的簇的標(biāo)記
??n_leaves:分層樹(shù)的葉子節(jié)點(diǎn)數(shù)量 --橫著
??children_:一個(gè)數(shù)組,給出了每個(gè)非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量 --豎著
?Methods:
??fit(X,y):訓(xùn)練模型
??fit_predict(X,y):訓(xùn)練模型并預(yù)測(cè)每個(gè)樣本點(diǎn)所屬的簇,等價(jià)于先調(diào)用fit方法,在調(diào)用predict方法.
總結(jié)
以上是生活随笔為你收集整理的聚类分析与相关算法(Kmeans等)详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： schema约束文档与xml文件详解
- 下一篇： 快速了解Bagging算法