基于歐氏距離的K均方聚類算法研究與應(yīng)用

1、基于歐氏間隔 的K均方聚類算法研究與應(yīng)用摘要：將所學(xué)的高等工程應(yīng)用數(shù)學(xué)知識與本專業(yè)內(nèi)容有效的結(jié)合起來，系統(tǒng)全面的介紹了間隔 度量與相異度計算、聚類的概念及聚類步驟，K-means算法根本思想及其實現(xiàn)過程，最后給出一個樹葉自動分類的應(yīng)用例如，并使用matlab工具實現(xiàn)，研究分析了基于歐氏間隔 的K-means算法的優(yōu)勢與缺乏。關(guān)鍵詞：歐氏間隔 ；聚類；K均方算法中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416202104-0148-03數(shù)學(xué)在科學(xué)開展過程中始終起著舉足輕重的作用，它深化浸透到各個學(xué)科領(lǐng)域的幾乎所有分支中。俗話說：“物以類聚，人以群分，在自然科學(xué)和社會科學(xué)中，存在

2、的大量分類問題同樣可以利用數(shù)學(xué)工具進(jìn)展定量分類。隨著人類科學(xué)技術(shù)的開展，對分類的要求越來越高，人們逐漸把數(shù)學(xué)工具引用到了分類學(xué)中形成了數(shù)值分類學(xué)，之后又將多元分析技術(shù)引入到數(shù)值分類學(xué)形成了聚類分析。聚類分析將大量數(shù)據(jù)劃分為性質(zhì)一樣的子類，更方便理解數(shù)據(jù)的分布情況，對識別數(shù)據(jù)的內(nèi)在構(gòu)造具有極其重要的作用，廣泛應(yīng)用于形式識別、圖像處理、數(shù)據(jù)壓縮、Web智能、生物信息等眾多領(lǐng)域。1 間隔 度量與相異度計算1.1 間隔 與間隔 空間設(shè)V是一個非空集合，V到實數(shù)集R的一個代數(shù)運(yùn)算記為，假設(shè)滿足：1正定性，并且；2對稱性=；3三角不等式。其中是V中的任意元素，那么稱是V中兩點為之間的距，并稱V按間隔 成為

3、間隔 空間或度量空間，記為V，d1。顯然間隔 是一種標(biāo)量，不具有方向而僅含量。在一個n維歐氏空間點集中，它的每個點X可以表示為x1，x2，xn，其中xii=1，2，n是實數(shù)，稱為X的第i個坐標(biāo)，兩個點A=a1，a2，an和B=b1，b2，bn之間的間隔 可用來描繪兩點的相對位移、遠(yuǎn)近、相似性等。常見的幾種間隔 空間中的代數(shù)運(yùn)算有歐氏間隔 、曼哈頓間隔 、明氏間隔 、切比雪夫間隔 等。歐氏間隔 是歐幾里得n維空間中兩點間的真實間隔 。其間隔 公式為：意義為兩元素在歐氏空間中的集合間隔 ，當(dāng)n=2時歐氏間隔 就是兩點之間的直線段間隔 。曼哈頓間隔 是使用在歐幾里得幾何度量空間的幾何學(xué)用語，用以標(biāo)明

4、兩點在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距總和，即在歐幾里得空間的固定直角坐標(biāo)系上兩點所形成的線段對軸投影的間隔 和。其間隔 公式為。明氏間隔 又稱明可夫斯基間隔 ，是歐氏空間中的一種測度，被看做是歐氏間隔 和曼哈頓間隔 的一種推廣。其間隔 公式為：，當(dāng)p=2時即為歐氏間隔 ，而p=1時那么為曼哈頓間隔 ，當(dāng)p取無窮時的極限情況下，還可以得到切比雪夫間隔 ：此外間隔 度量可以加權(quán)，從而盡可能真實地反映不同分量的影響力大小。1.2 相異度計算相異度通常用來衡量兩個可比較元素的差異度。例如臉與手掌的相異度明顯大于手掌與腳掌的相異度，這種感觀對于人是很直觀的，但計算機(jī)卻不具備這種直觀感受才能，因此我們必須從數(shù)學(xué)的

5、角度，形式化定量定義相異度。假設(shè)訓(xùn)練樣本用m個特征屬性來描繪，那么可以把每個訓(xùn)練樣本點看作m維空間中的一點，并使用某種間隔 比方歐氏間隔 ，來表示訓(xùn)練樣本點間的相異度，可定義間隔 較近的點性質(zhì)比較相似，從而斷定兩者的相異度較小，定義間隔 較遠(yuǎn)的點性質(zhì)有較大差異，相異度較大。如今考慮元素的所有特征屬性都是標(biāo)量的情況，設(shè)，X和Y是具有m個可度量特征屬性的兩個不同元素項，那么它們的相異度可定義為：，其中R為實數(shù)域。比方計算X=1，66，3和Y=101，2，7的相異度，可以進(jìn)一步將定義為歐氏間隔 ，那么X和Y的相異度為：=118.8。上述這種相異度的計算方式存在一個問題：屬性的取值范圍越大對間隔 的影

6、響越明顯。上例中第一個特征屬性的取值跨度就遠(yuǎn)大于第三個，這對于相異度的真實反映是非常不利的。為此，我們通常采取把每個特征屬性值比例映射到一樣區(qū)間，即對特征屬性值規(guī)格化，從而使各個屬性能平衡地影響間隔 。一般映射到的取值區(qū)間是0，1，映射公式為：式中是所有元素項中第i個特征屬性最大值，相應(yīng)的為最小值。對上例，中每個元，素規(guī)，格化并映射到區(qū)間0，1，那么X=0，1，0，Y=1，0，1，重新計算歐氏間隔 約為1.732。，2 聚類問題2.1 類由于自然界事務(wù)特性紛繁復(fù)雜，用來表示樣本點性質(zhì)的變量也種類繁多，在對數(shù)據(jù)聚類特征屬性提取的過程中有多種不同選擇，使得樣本點的表達(dá)形式各不一樣，在不同問題域中一

7、樣稱謂的類的定義也有不同，所以在對數(shù)據(jù)對象聚類前，應(yīng)先給出類的定義2。幾種類的定義形式如下：設(shè)U是集合，Si是U中的樣本元素，樣本個數(shù)為k，T和V為預(yù)設(shè)的閥值，那么有：1假設(shè)，都有，那么U稱為一類；2假設(shè)，都有，那么U稱為一類；3假設(shè)，都有，且DSi，SjT，那么U稱為一類；4假設(shè)，都，滿足DSi，SjT，那么稱U為一類。上述幾中不同的類的定義，定義1的要求是最高的，定義2次之。只要符合定義1的類，必定符合其他定義；只要符合定義2的類，同樣符合定義3。無論何種定義，均是使用元素間的間隔 來定義，不同的是間隔 的限制程度。2.2 聚類2.2.1 聚類定義一個問題域的數(shù)據(jù)量往往是寵大的，要對這些數(shù)

8、據(jù)進(jìn)展分類處理存在很大的難度，有時候用戶也不明確要做何種分類，在這種情況下，采用監(jiān)視學(xué)習(xí)方法進(jìn)展分類，往往會因為信息缺乏、預(yù)處理代價大等問題使得分類效果并不令人滿意。聚類方法是一種無監(jiān)視或半監(jiān)視的學(xué)習(xí)方法，處理此類問題有較明顯的優(yōu)勢。聚類是將待處理問題域的數(shù)據(jù)對象集合劃分成由相似對象構(gòu)成的多種不同類的過程。通常先給定一組元素的集合U，集合中每個元素有N個可觀察性能，運(yùn)用特定算法劃分U為K個子集類簇，每個子集內(nèi)元素的相異度盡量小，不同子集間元素的相異盡量大。這是一個觀察式的無監(jiān)視學(xué)習(xí)過程，與分類不同，聚類前不需要明確分類數(shù)量或類別，沒有可提供的先驗知識。聚類形式定義如下： 令U=p1，p2，pn

9、表示一個形式實體集合，pi 表示第i個形式i=1，2，n；Ct U，t=1，2，k，；有，式中下標(biāo)ms表示形式所屬的類，下標(biāo)ir表示類中某一形式，proximity函數(shù)是間隔 函數(shù)，用來描繪形式的相似性。假設(shè)類Ct集為聚類結(jié)果，那么Ct應(yīng)滿足的條件如下：1；2對于Cm，CrU，CmCr，有僅限于剛性聚類，且2.2.2 聚類步驟聚類的主要步驟3包括樣本數(shù)據(jù)準(zhǔn)備、特征子集選擇、特征提取、相異度計算、集群或分組、結(jié)果有效性評估等步驟。數(shù)據(jù)準(zhǔn)備通常包括標(biāo)準(zhǔn)化特征屬性和對樣本數(shù)據(jù)的降維，從而構(gòu)造出一個初始特征數(shù)據(jù)集。特征子集選擇那么是將初始特征數(shù)據(jù)中不相關(guān)或冗余的特征去除，選擇最有效的特征存放在特征向量

10、中，從而進(jìn)步模型準(zhǔn)確度和減少運(yùn)行時間。特征提?。和ㄟ^某種變換將測量空間的特征轉(zhuǎn)換成新的能突出其本質(zhì)功能、優(yōu)勢的特征，其結(jié)果通常稱為特征向量。集群或分組是基于某種間隔 的特征屬性相異度度量的結(jié)果，間隔 相近的聚類，實現(xiàn)分組。聚類結(jié)果要求類簇內(nèi)是高內(nèi)聚，類簇間是低耦合。結(jié)果有效性評估根據(jù)該要求主要有內(nèi)部和外部有效性評估，相關(guān)性測試評估三種評估方式。聚類結(jié)果優(yōu)劣的評判標(biāo)準(zhǔn)通常包括處理不同類型數(shù)據(jù)才能，大數(shù)據(jù)處理才能，臟數(shù)據(jù)處理才能，不同排列的數(shù)據(jù)處理才能，可解釋性等。3 K均值K-means算法1967 年，MacQueen 首次提出了K均值聚類算法K-means 算法，是聚類的經(jīng)典算法之一。K-means算法是非常典型的基于間隔 計算的聚類算法，它把間隔 作為相似性/相異性的度量，認(rèn)為對象的相異性/相似性與間隔 的遠(yuǎn)/近成正比。該算法的根本思想：首先隨機(jī)或有規(guī)那么地選擇k個對象，分別作為k個簇的中心或初始均值，對于剩下的每個對象，計算其與各個簇中心的間隔 ，并將它分配到最近的簇中，分配完后重新計算每個簇新的中心或均值。通過迭代運(yùn)算，直到最小平方誤差準(zhǔn)那么收斂出最后的聚類結(jié)果。k均值算法的計算過程非常直觀4，詳細(xì)實現(xiàn)偽代碼如下，假定對n 個樣本進(jìn)展聚類：1Input k，n，m；/m為可能的孤立元素個數(shù)；2計算樣本間間隔 di，j；Delete m個maxdi，j對象；3Cen