基于歐氏距離的K均方聚類算法研究與應用

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

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

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

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

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

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

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

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

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

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