聚類(lèi)算法的應(yīng)用

聚類(lèi)算法應(yīng)用主講：張旺01聚類(lèi)算法的介紹02應(yīng)用場(chǎng)景的介紹03三種聚類(lèi)算法04圖片分割目錄聚類(lèi)算法的介紹1何為聚類(lèi)？俗話說(shuō)：“物以類(lèi)聚，人以群分”，在自然科學(xué)和社會(huì)科學(xué)中，存在著大量的分類(lèi)問(wèn)題。所謂類(lèi)，通俗地說(shuō)，就是指相似元素的集合。何為聚類(lèi)？“聚類(lèi)”是無(wú)監(jiān)督學(xué)習(xí)的一種，目標(biāo)是通過(guò)對(duì)無(wú)標(biāo)記訓(xùn)練樣本的學(xué)習(xí)來(lái)屆時(shí)數(shù)據(jù)內(nèi)在的性質(zhì)及其規(guī)律。聚類(lèi)試圖將數(shù)據(jù)集中的樣本劃分為若干個(gè)通常不相交的子集，每個(gè)子集稱為一個(gè)“簇”。通過(guò)這樣的劃分，每個(gè)簇可能對(duì)應(yīng)一些潛在的概念。常見(jiàn)的聚類(lèi)算法有：K-Means(K均值)聚類(lèi)K最近鄰（KNN）分類(lèi)算法（監(jiān)督學(xué)習(xí)）均值漂移聚類(lèi)(Meanshift)應(yīng)用場(chǎng)景的介紹2應(yīng)用場(chǎng)景的介紹聚類(lèi)的用途是很廣泛的。在商業(yè)上，聚類(lèi)可以幫助市場(chǎng)分析人員從消費(fèi)者數(shù)據(jù)庫(kù)中區(qū)分出不同的消費(fèi)群體來(lái)，并且概括出每一類(lèi)消費(fèi)者的消費(fèi)模式或者說(shuō)習(xí)慣。它作為數(shù)據(jù)挖掘中的一個(gè)模塊，可以作為一個(gè)單獨(dú)的工具以發(fā)現(xiàn)數(shù)據(jù)庫(kù)中分布的一些深層的信息，并且概括出每一類(lèi)的特點(diǎn)，或者把注意力放在某一個(gè)特定的類(lèi)上以作進(jìn)一步的分析；并且，聚類(lèi)分析也可以作為數(shù)據(jù)挖掘算法中其他分析算法的一個(gè)預(yù)處理步驟。應(yīng)用場(chǎng)景的介紹圖片分類(lèi)

現(xiàn)實(shí)世界中我們往往容易獲得大量的無(wú)標(biāo)簽的數(shù)據(jù)集，如果我們能夠從無(wú)標(biāo)簽數(shù)據(jù)中學(xué)的模式，那么可以不必花費(fèi)大量時(shí)間和金錢(qián)來(lái)標(biāo)記標(biāo)簽數(shù)據(jù)用于監(jiān)督學(xué)習(xí)，因此我們可以將聚類(lèi)的方法應(yīng)用在圖片分類(lèi)上，使機(jī)器能夠自動(dòng)的將圖片進(jìn)行分類(lèi)。圖片分割

圖像分割技術(shù)已在實(shí)際生活中得到廣泛的應(yīng)用。例如：在機(jī)車(chē)檢驗(yàn)領(lǐng)域，可以應(yīng)用到輪轂裂紋圖像的分割，及時(shí)發(fā)現(xiàn)裂紋，保證行車(chē)安全；在生物醫(yī)學(xué)工程方面，對(duì)肝臟CT圖像進(jìn)行分割，為臨床治療和病理學(xué)研究提供幫助。應(yīng)用場(chǎng)景的介紹網(wǎng)頁(yè)聚類(lèi)

網(wǎng)頁(yè)聚類(lèi)是網(wǎng)絡(luò)挖掘的一種重要方法，用于從大量半結(jié)構(gòu)化數(shù)據(jù)(如網(wǎng)頁(yè))中發(fā)現(xiàn)未知知識(shí)或信息。實(shí)際上,HTML頁(yè)面是存儲(chǔ)在后臺(tái)數(shù)據(jù)庫(kù)中的數(shù)據(jù)和HTML內(nèi)容模板的結(jié)合體,在網(wǎng)站內(nèi)部的網(wǎng)頁(yè)大多都是由一套相同的內(nèi)容模板生成的,因此可以認(rèn)為網(wǎng)頁(yè)的設(shè)計(jì)是有一定規(guī)律的.通過(guò)這個(gè)規(guī)律,使用一定的聚類(lèi)算法來(lái)對(duì)網(wǎng)頁(yè)進(jìn)行分類(lèi)。社交網(wǎng)絡(luò)聚

社交網(wǎng)絡(luò)是一種以用戶為節(jié)點(diǎn)、以用戶關(guān)系為邊的網(wǎng)絡(luò)結(jié)構(gòu),用戶的興趣、行為、功能等關(guān)系使社交網(wǎng)絡(luò)中存在多個(gè)社區(qū)或簇。社交網(wǎng)絡(luò)的結(jié)構(gòu)對(duì)于探求信息的傳播方式和獲取價(jià)值信息(如廣告投放、潛在商機(jī)發(fā)現(xiàn))等具有重要價(jià)值和意義。大部分社交網(wǎng)絡(luò)均可抽象為無(wú)向或有向圖,研究這些圖結(jié)構(gòu),有利于挖掘出其中潛在的有價(jià)值信息。電商用戶聚類(lèi)

現(xiàn)如今,網(wǎng)上購(gòu)物已經(jīng)成為了人們?nèi)粘Ｉ畈豢苫蛉钡囊粋€(gè)部分。在網(wǎng)上購(gòu)物的情境下,買(mǎi)家和賣(mài)家不再需要進(jìn)行面對(duì)面的交易,這給賣(mài)家直觀的掌握顧客的需求和反饋提供了一定的障礙。但在另一方面,網(wǎng)上購(gòu)物為數(shù)據(jù)分析提供了便利。顧客在網(wǎng)上發(fā)生的所有購(gòu)物行為都被計(jì)算機(jī)記錄在案,這使得商家能夠通過(guò)這些數(shù)據(jù)分析顧客的行為從而了解消費(fèi)者的需求和偏好,甚至能夠預(yù)測(cè)顧客的購(gòu)買(mǎi)行為。三種聚類(lèi)算法3K-means聚類(lèi)算法k均值聚類(lèi)算法（k-meansclusteringalgorithm）是一種迭代求解的聚類(lèi)分析算法，其步驟是，預(yù)將數(shù)據(jù)分為K組，則隨機(jī)選取K個(gè)對(duì)象作為初始的聚類(lèi)中心，然后計(jì)算每個(gè)對(duì)象與各個(gè)種子聚類(lèi)中心之間的距離，把每個(gè)對(duì)象分配給距離它最近的聚類(lèi)中心。聚類(lèi)中心以及分配給它們的對(duì)象就代表一個(gè)聚類(lèi)。每分配一個(gè)樣本，聚類(lèi)的聚類(lèi)中心會(huì)根據(jù)聚類(lèi)中現(xiàn)有的對(duì)象被重新計(jì)算。這個(gè)過(guò)程將不斷重復(fù)直到滿足某個(gè)終止條件。終止條件可以是沒(méi)有（或最小數(shù)目）對(duì)象被重新分配給不同的聚類(lèi)，沒(méi)有（或最小數(shù)目）聚類(lèi)中心再發(fā)生變化，誤差平方和局部最小K-means聚類(lèi)算法算法流程（1）選取K個(gè)點(diǎn)做為初始聚集的簇心（也可選擇非樣本點(diǎn)）;（2）分別計(jì)算每個(gè)樣本點(diǎn)到K個(gè)簇核心的距離（這里的距離一般取歐氏距離或余弦距離），找到（3）離該點(diǎn)最近的簇核心，將它歸屬到對(duì)應(yīng)的簇；所有點(diǎn)都?xì)w屬到簇之后，M個(gè)點(diǎn)就分為了K個(gè)簇。之后重新計(jì)算每個(gè)簇的重心（平均距離中心），將其定為新的“簇核心”；（4）反復(fù)迭代2-3步驟，直到達(dá)到某個(gè)中止條件。KNN算法KNN算法又稱k近鄰分類(lèi)(k-nearestneighborclassification)算法。它是根據(jù)不同特征值之間的距離來(lái)進(jìn)行分類(lèi)的一種簡(jiǎn)單的機(jī)器學(xué)習(xí)方法，它是一種簡(jiǎn)單但是懶惰的算法。他的訓(xùn)練數(shù)據(jù)都是有標(biāo)簽的數(shù)據(jù)，即訓(xùn)練的數(shù)據(jù)都有自己的類(lèi)別。KNN算法主要應(yīng)用領(lǐng)域是對(duì)未知事物進(jìn)行分類(lèi)，即判斷未知事物屬于哪一類(lèi)，判斷思想是，基于歐幾里得定理，判斷未知事物的特征和哪一類(lèi)已知事物的的特征最接近。它也可以用于回歸，通過(guò)找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。KNN算法算法過(guò)程：1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；2）按照距離的遞增關(guān)系進(jìn)行排序；3）選取距離最小的K個(gè)點(diǎn)；4）確定前K個(gè)點(diǎn)所在類(lèi)別的出現(xiàn)頻率；5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類(lèi)別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類(lèi)核心思想：KNN的原理就是當(dāng)預(yù)測(cè)一個(gè)新的值x的時(shí)候，根據(jù)它距離最近的K個(gè)點(diǎn)是什么類(lèi)別來(lái)判斷x屬于哪個(gè)類(lèi)別Meanshift算法meanShift,均值漂移，在聚類(lèi)、圖像平滑、分割、跟蹤等方面有著廣泛的應(yīng)用。meanShift這個(gè)概念最早是由Fukunage在1975年提出的，其最初的含義正如其名：偏移的均值向量；但隨著理論的發(fā)展，meanShift的含義已經(jīng)發(fā)生了很多變化。如今，我們說(shuō)的meanShift算法，一般是指一個(gè)迭代的步驟，即先算出當(dāng)前點(diǎn)的偏移均值，然后以此為新的起始點(diǎn)，繼續(xù)移動(dòng)，直到滿足一定的結(jié)束條件。Meanshift算法算法過(guò)程：1、在未被標(biāo)記的數(shù)據(jù)點(diǎn)中隨機(jī)選擇一個(gè)點(diǎn)作為中心center；2、找出離center距離在bandwidth之內(nèi)的所有點(diǎn)，記做集合M，認(rèn)為這些點(diǎn)屬于簇c。同時(shí)，把這些求內(nèi)點(diǎn)屬于這個(gè)類(lèi)的概率加1，這個(gè)參數(shù)將用于最后步驟的分類(lèi)3、以center為中心點(diǎn)，計(jì)算從center開(kāi)始到集合M中每個(gè)元素的向量，將這些向量相加，得到向量shift。4、center

=

center+shift。即center沿著shift的方向移動(dòng)，移動(dòng)距離是||shift||。5、重復(fù)步驟2、3、4，直到shift的大小很?。ň褪堑绞諗浚涀〈藭r(shí)的center。注意，這個(gè)迭代過(guò)程中遇到的點(diǎn)都應(yīng)該歸類(lèi)到簇c。6、如果收斂時(shí)當(dāng)前簇c的center與其它已經(jīng)存在的簇c2中心的距離小于閾值，那么把c2和c合并。否則，把c作為新的聚類(lèi)，增加1類(lèi)。6、重復(fù)1、2、3、4、5直到所有的點(diǎn)都被標(biāo)記訪問(wèn)。7、分類(lèi)：根據(jù)每個(gè)類(lèi)，對(duì)每個(gè)點(diǎn)的訪問(wèn)頻率，取訪問(wèn)頻率最大的那個(gè)類(lèi)，作為當(dāng)前點(diǎn)集的所屬類(lèi)。核心思想求解一個(gè)向量，使得圓心一直往數(shù)據(jù)集密度最大的方向移動(dòng)。說(shuō)的再簡(jiǎn)單一點(diǎn)，就是每次迭代的時(shí)候，都是找到圓里面點(diǎn)的平均位置作為新的圓心位置圖片分割4圖片分割使用k-means對(duì)圖像進(jìn)行分割,我們將每個(gè)像素點(diǎn)劃分到不同的簇上,并用每個(gè)簇質(zhì)心的值來(lái)代替這個(gè)簇的所有像素點(diǎn)的值,實(shí)現(xiàn)簡(jiǎn)單的圖像分割算法流程：Step1：初始化每個(gè)類(lèi)別的中心點(diǎn):

這里根據(jù)圖像通道數(shù)進(jìn)行初始化,如果是rgb圖像,每個(gè)類(lèi)別的中心點(diǎn)需

要包含三個(gè)通道,每個(gè)通道可以看作原始k-means聚類(lèi)的一個(gè)維度(即特征的數(shù)量,有多少個(gè)屬性).Step2：循環(huán)以下,直到每次計(jì)算中心點(diǎn)后其值不變化2.1.根據(jù)中心點(diǎn)聚類(lèi):計(jì)算圖像中每個(gè)像素點(diǎn)與每個(gè)類(lèi)別中心點(diǎn)的距離,距離最小的那個(gè)類(lèi)別為該像素點(diǎn)所屬的類(lèi)別.2.2.根據(jù)每個(gè)類(lèi)別更新中心點(diǎn):根據(jù)每個(gè)類(lèi)別的所有像素點(diǎn),計(jì)算這些像素點(diǎn)每個(gè)通道的均值,以