朱俚治

(南京航空航天大學(xué)信息中心　南京　210016)

?

一種加權(quán)歐氏距離聚類算法的改進(jìn)*

朱俚治

(南京航空航天大學(xué)信息中心南京210016)

摘要聚類算法是一種無(wú)監(jiān)督學(xué)習(xí)的算法,能夠?qū)⑾嗨贫葟?qiáng)的數(shù)據(jù)聚類到一個(gè)族內(nèi),并且能夠?qū)傩韵喈惖臄?shù)據(jù)劃分到不同的族里。當(dāng)今聚類算法可分為傳統(tǒng)的聚類算法和非傳統(tǒng)的聚類算法。傳統(tǒng)的聚算法有:基于劃分聚類算法、基于層次聚類算法等算法。人們?cè)谑褂脛澐址ê蛯哟畏ㄟM(jìn)行聚類時(shí),是通過(guò)計(jì)算聚類對(duì)象之間屬性的距離來(lái)實(shí)現(xiàn)聚類,因此歐氏距離公式和加權(quán)歐氏距離公式在這兩種聚類算法中常用的算法。加權(quán)歐氏距離計(jì)算公式在聚類時(shí)著重聚類對(duì)象屬性權(quán)重的選擇,所以此文從聚類對(duì)象的相似度和對(duì)象屬性對(duì)應(yīng)的權(quán)重,這兩個(gè)方面來(lái)考慮聚類成功的概率。論文作者提出的算法思想是,如果某個(gè)聚類對(duì)象具有若干的屬性,那么首先計(jì)算該聚類對(duì)象屬性的相似度,再根據(jù)該屬性對(duì)應(yīng)的權(quán)重是否為關(guān)鍵權(quán)重,如果是此屬性對(duì)應(yīng)的權(quán)重是關(guān)鍵權(quán)重,那么該對(duì)象聚類的成功率較高。

關(guān)鍵詞加權(quán)歐氏距離; 相似度; 權(quán)重; 屬性; 聚類

Improvement of Weighted Euclidean Distance Clustering Algorithm

ZHU Lizhi

(Information Center, Nanjing University of Aeronautics & Astronautics, Nanjing210016)

AbstractClustering algorithm is an unsupervised learning algorithm, which can cluster the data with strong similarity to a family, and can divide the data into different groups. Clustering algorithms can be classified into the traditional clustering algorithm and the non traditional clustering algorithm. The traditional clustering algorithms are based on clustering algorithm and hierarchical clustering algorithm. When clustering is used to cluster by dividing method and hierarchy process, the distance between the attributes of clustering objects is calculated. So the Euclidean distance formula and the weighted Euclidean distance formula are used in the two clustering algorithms. Weighted Euclidean distance formula in the clustering object class attribute weights of reunion, so this paper from the object cluster similarity and the properties of an object corresponding to the weights, the two aspects to consider clustering success probability. The algorithm proposed by this paper is that if a clustering object has a number of attributes, then it first calculates the similarity of the clustering object attributes, and then according to the weight of the attributes corresponding to the weight is the key, then the success rate of the object clustering is higher.

Key Wordsweighted Euclidean distance, similarity, weight, attribute, clustering

Class NumberTP391.41

1引言

隨著信息技術(shù)的發(fā)展,人們積累的音、視頻數(shù)據(jù),以及文本、圖片等數(shù)據(jù)越來(lái)越多,為了從這些大量的數(shù)據(jù)中提取對(duì)人們有用的信息數(shù)據(jù),必須將不同類的數(shù)據(jù)進(jìn)行分類和聚類,因此就出現(xiàn)聚類技術(shù)[7~9]。分類技術(shù)和聚類技術(shù)是截然不同的兩種技術(shù),分類必須根據(jù)已有的知識(shí)進(jìn)行分類,而聚類是一種無(wú)監(jiān)督學(xué)習(xí)技術(shù)。聚類分析是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要分支,是人們認(rèn)識(shí)和探索事物之間內(nèi)在聯(lián)系的有效手段,它既可以用作獨(dú)立的數(shù)據(jù)挖掘工具,來(lái)發(fā)現(xiàn)數(shù)據(jù)庫(kù)中數(shù)據(jù)分布的一些深入信息,也可作為其它數(shù)據(jù)挖掘算法中的預(yù)處理步驟[7~9]。

當(dāng)今聚類算法有基于劃分的聚類算法、基于層次的聚類算法、基于密度的算法等聚類算法。盡管當(dāng)今出現(xiàn)多種新技術(shù)的聚類算法,但傳統(tǒng)的聚類算法仍然有著廣泛的應(yīng)用領(lǐng)域。傳統(tǒng)的聚類算法中的劃分法,是通過(guò)最大距離和最小距離來(lái)完成聚類的。為了改進(jìn)某些聚類算法,有人提出了馬氏距離聚類算法、歐氏距離聚類算法、加權(quán)歐氏距離聚類算法。加權(quán)歐氏距離聚類算法是歐氏距離聚類算法一種改進(jìn)算法,其算法的創(chuàng)新之處是引入權(quán)重的概念。權(quán)重的引入有利于聚類時(shí)成功的概率。本文在加權(quán)歐氏距離聚類算法中,引入了當(dāng)對(duì)象進(jìn)行聚類之時(shí),首先計(jì)算對(duì)象屬性相似度的概率。如果聚類對(duì)象某些屬性的相似程度為強(qiáng)的概率較大,那么這將為聚類是否成功提供重要參考依據(jù)。

2聚類的算法簡(jiǎn)介

1) 聚類分析的定義

聚類是將數(shù)據(jù)劃分成群組的過(guò)程,研究如何在沒(méi)有訓(xùn)練的條件下把對(duì)象劃分為若干類。通過(guò)確定數(shù)據(jù)之間在預(yù)先制定的屬性上的相似性來(lái)完成聚類任務(wù),這樣最相似的數(shù)據(jù)就聚集成族[7~9]。

2) 聚類算法

聚類算法主要有以下幾種:劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基于模型方法[7~9]。劃分方法的經(jīng)典算法有:K—MEANS算法,K—MEDOIDS算法。層次方法的經(jīng)典算法有:BIRCH算法、CURE算法、CHAMELEON算法等。基于密度的經(jīng)典算法有:DBSCAN算法、OPTICS算法和DENCLUE算法。基于網(wǎng)格的經(jīng)典算法有:STING算法和CLIQUE算法等。

3) 聚類算法的規(guī)則

在聚類算法中劃分方法,層次方法和基于網(wǎng)格的聚類算法都是通過(guò)計(jì)算對(duì)象屬性之間的距離來(lái)判斷屬性的相似性[7~9]。應(yīng)用于聚類算法中的對(duì)象屬性的距離計(jì)算的公式有:歐氏距離聚類公式、加權(quán)歐氏距離聚類公式、馬氏距離聚類公式。因此距離計(jì)算公式在聚類算法中有相當(dāng)重要的作用。

3加權(quán)歐氏距離簡(jiǎn)介

在傳統(tǒng)的聚類算法中常用的聚類方法是通過(guò)對(duì)象的距離來(lái)完成聚類[2~3]。在很多的聚類算法中都采用歐氏距離公式作為聚類時(shí)的依據(jù)。在歐氏距離聚類方法中有兩種歐氏距離公式:非加權(quán)歐氏距離和加權(quán)歐氏距離,本文將采用加權(quán)歐氏距離作為研究的對(duì)象。

1) 非加權(quán)歐氏距離計(jì)算公式[2]:

------------------------------2) 加權(quán)歐氏距離計(jì)算法公式[2]:

------------------------------其中,i=(Xi1,Xi2,…,Xip)和j=(Xj1,Xj2,…,Xjp)是兩個(gè)p維的數(shù)據(jù)對(duì)象,Wp表示每個(gè)變量的權(quán)重值。在進(jìn)行聚類時(shí)合理地運(yùn)用加權(quán)歐氏距離,可以反映出各變量在數(shù)據(jù)中的不同作用,對(duì)改進(jìn)聚類結(jié)果能起到較好的效果。

4加權(quán)歐氏距離公式中聚類對(duì)象屬性的比較

需要聚類的對(duì)象A′有若干屬性Xi1,Xi2,…,Xip,聚類對(duì)象A有若干屬性Xj1,Xj2,…,Xjp。

1) 需要聚類對(duì)象A′的若干屬性與聚類對(duì)象A的若干屬性之間的比較:

如果對(duì)象A′某些屬性十分接近對(duì)象A某些屬性,那么有:Xi1-Xj1≈0,Xi2-Xj2≈0,…,Xip-Xjp≈0。

3) 根據(jù)以上的討論和分析有以下的結(jié)論:

如果對(duì)象A′某些屬性十分接近于對(duì)象A的某些屬性時(shí):

(1)它們屬性的差值十分接近于0。

(2)它們屬性的比值十分接近于1。

5聚類對(duì)象屬性相似度的計(jì)算

5.1聚類對(duì)象的屬性偏離概率估量

根據(jù)上一節(jié)的研究有以下的分析和討論:

本文用A′表示是需要聚類對(duì)象的屬性值,用A表示聚類對(duì)象的屬性值。

如果A′與A屬于惡意軟件,當(dāng)對(duì)象A′的屬性與對(duì)象A的屬性偏離程度達(dá)到了100%時(shí),這時(shí)它們的屬性完全沒(méi)有相同之處。但是當(dāng)對(duì)象A′的屬性與對(duì)象A的屬性相似程度達(dá)到了100%時(shí),這時(shí)它們的屬性完全相同,相似程度非常強(qiáng)。

如果A′與A屬于非惡意軟件,當(dāng)對(duì)象A′的屬性與對(duì)象A的屬性偏離程度達(dá)到了100%時(shí),這時(shí)它們的屬性完全沒(méi)有相同之處。但是當(dāng)對(duì)象A′的屬性與對(duì)象A的屬性相似程度達(dá)到了100%時(shí),這時(shí)它們的屬性完全相同,相似程度非常強(qiáng)。

進(jìn)行對(duì)象聚類的時(shí)候,只有同為惡意軟件的對(duì)象或同為非惡意軟件的對(duì)象之間才有相似之處,才能夠進(jìn)行聚類。惡意軟件的對(duì)象與非惡意軟件是截然不同屬性的兩種軟件,它們之間的聚類是不可能的,不能聚成一個(gè)族。

以下對(duì)象之間的分析和討論都是基于同屬于惡意軟件或同屬于非惡意軟件相似度概率的計(jì)算。

1) 在聚類過(guò)程之中,如果需對(duì)象A′的屬性十分接近于已知對(duì)象A的屬性時(shí),那么A′/A的比值將十分逼近1值。當(dāng)A′/A的比值十分逼近1時(shí),函數(shù)f(x)=|1-A′/A|就十分接近于0的值,這時(shí)對(duì)象A′的屬性偏離已知對(duì)象A的屬性的值將趨向于0,因此當(dāng)f(x)=|1-A′/A|的值越小,值的大小趨向于0時(shí),這時(shí)對(duì)象A′的屬性值非常接近于已知對(duì)象A的屬性值,則A′的屬性偏離A的概率就越小。

2) 在聚類過(guò)程之中,如果需對(duì)象A′的屬性大于已知對(duì)象A的屬性時(shí),那么A′/A的比值將大于1。當(dāng)A′/A的比值越大時(shí),函數(shù)f(x)=|1-A′/A|的值大于0的程度將越明顯。這時(shí)對(duì)象A′的屬性值大于或遠(yuǎn)大于已知對(duì)象A的屬性值時(shí),則A′的屬性偏離A的概率就越大。

3) 在聚類過(guò)程中,如果需對(duì)象A′的屬性小于已知對(duì)象A的屬性時(shí),那么A′/A的比值將小于1。當(dāng)A′/A的比值越小時(shí),這時(shí)對(duì)象A′的屬性值小于或遠(yuǎn)小于已知對(duì)象A的屬性值時(shí),則A′的屬性偏離A的概率就越大。

5.2聚類對(duì)象屬性相似度的估計(jì)

函數(shù):g(x)=1-f(x)

說(shuō)明:函數(shù)y=g(x)的含義是聚類對(duì)象相似程度的判斷函數(shù)。以下分析和討論是對(duì)函數(shù)g(x)=1-f(x)進(jìn)行討論:

1) 當(dāng)y=f(x)的值越小,則有對(duì)象A′的屬性偏離A的概率就越小。如果y=f(x)的值越小,那么g(x)=1-f(x)的值就越大,就表示對(duì)象A′的屬性偏離A的概率就越小。這時(shí)對(duì)象A′的屬性與A的相似的概率就越大,則聚類對(duì)象之間的相似度就越強(qiáng)。

2) 當(dāng)y=f(x)的值越大,則有對(duì)象A′的屬性偏離A的概率就越大。如果y=f(x)的值越大,那么g(x)=1-f(x)的值就越小,就表示對(duì)象A′的屬性偏離A的概率就越大。這時(shí)對(duì)象A′的屬性與A的相似的概率就越小,則聚類對(duì)象之間的相似度就越弱。

6聚類對(duì)象的屬于與權(quán)重

1) 聚類對(duì)象的屬性

(1)A′具有的屬性為Xi1,Xi2,…,Xip。A具有的屬性為Xj1,Xj2,…,Xjp。

(2)A′的屬性Xi1與A的屬性Xj1相對(duì)應(yīng),A′的屬性Xi2與A的屬性Xj2相對(duì)應(yīng),…,A′的屬性Xip與A的屬性Xjp相對(duì)應(yīng)。

2) 聚類對(duì)象的屬性與其權(quán)重

(1)A′的屬性Xip與A的屬性Xjp相對(duì)應(yīng)

權(quán)重Wi1與Xi1-Xj1對(duì)應(yīng),權(quán)重Wi2與Xi2-Xj2對(duì)應(yīng),…,權(quán)重Wip與Xip-Xjp對(duì)應(yīng)。

(2)如果Xip-Xjp十分接近于0,那么Xip與Xjp的比值十分接近于1,并且它們的相似概率值十分接近于1。如果此時(shí)與該屬性對(duì)應(yīng)的權(quán)重為關(guān)鍵權(quán)重,那么有以下的結(jié)論:那么在進(jìn)行對(duì)象聚類時(shí)該屬性為重要屬性,能夠作為聚類是否成功的關(guān)鍵性參考條件。

7結(jié)語(yǔ)

在進(jìn)行聚類對(duì)象的屬性可能是n維的,因此在進(jìn)行聚類時(shí)對(duì)象之間必須進(jìn)行屬性值的匹配和計(jì)算。在屬性的計(jì)算過(guò)程中,屬性之間的相似程度是不同的,有些屬性相似程度強(qiáng)些,而有些屬性相似程度弱些。加權(quán)歐氏距離的聚類公式能夠計(jì)算多個(gè)屬性的相似度,再根據(jù)該屬性對(duì)應(yīng)的權(quán)重是否為關(guān)鍵權(quán)重來(lái)為這次聚類是否成功提供重要依據(jù)。如果對(duì)象的某些屬性相似的概率較大,并且與該屬性對(duì)應(yīng)的權(quán)重為重要的權(quán)重,那么這些因素同樣是聚類時(shí)是否成功的重要參考條件。

參 考 文 獻(xiàn)

[1] 孟海東,張玉英,宋飛燕.一種基于加權(quán)歐氏距離聚類方法的研究[J].計(jì)算機(jī)應(yīng)用,2006,26(12):152-153.

MENG Haidong, ZHANG Yuying, SONG Feiyan. Research based on euclid distance with weights of clustering method[J]. Journal of Computer Application,2006,26(12):152-153.

[2] 董旭,魏振軍.一種加權(quán)歐氏距離聚類方法[J],信息工程大學(xué)學(xué)報(bào),2005,6(1):23-25.

DONG Xu, WEI Zhenjun. A Clustering Method of Euclid Distance with Weights[J]. Journal of Information Engineering,2005,6(1):23-25.

[3] 吳香華,牛生杰,吳誠(chéng),等.馬氏距離聚類分析中協(xié)方差矩陣估算的改進(jìn)[J].數(shù)理統(tǒng)計(jì)與管理,2011,30(2):240-245.

WU Xianghua, NIU Shengjie, WU Cheng, et al. An Improvement on Estimating Covariance Matrix during Cluster Analysis Using Mahalanobis Distance[J]. Application of Statistics and Managerment,2011,30(2):240-245.

[4] 邵峰晶,于忠清,王金龍,等.數(shù)據(jù)挖掘原理與算法[M].北京:科學(xué)出版社,2009.

SHAO Fengjing, YU Zhongqing, WANG Jinlong, et al. Principle and Algorithm of Data Mining[M]. Science Press,2009.

[5] 羅森林,馬駿,潘麗敏.數(shù)據(jù)挖掘理論與技術(shù)[M].北京:電子工業(yè)出版社,2013.

LUO Senglin, MA Jun, PAN Limin. Theory And Technology of Data Mining[M]. Beijing: Electronics Industry Press,2013.

[6] 吳帆,李石君.一種高效的層次聚類分析算法[J].計(jì)算機(jī)工程,2004,30(9):70-71.

WU Fan, LI Shijun. An Efficient Hierarchical Clustering Algorithm[J]. Computer Engineering,2004,30(9):70-71.

[7] 向培素.聚類算法綜述[J].西南名族大學(xué)學(xué)報(bào)·自然科學(xué)版,2011,37(專輯):112-114.

XIANG Peisu. Survey of Clustering Algorithm[J]. Journal of Southwest University for Nationalities·Natural Science,2011,37(special):112-114.

[8] 方媛,車啟鳳.數(shù)據(jù)挖掘之聚類算法綜述[J].河西學(xué)院學(xué)報(bào),2012,28(5):72-76.

FANG Yuan, CHE Qifeng. Summary of Data Mining Clustering Algorithm[J]. Journal of Hexi University,2012,28(5):72-76.

[9] 賀玲,吳玲達(dá),蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計(jì)算機(jī)應(yīng)用,2007:10-13.

HE Ling, WU Lingda, CAI Yichao. Survey of Clustering Algorithms in Data Mining[J]. Application Research of Computers,2007:10-13.

[10] 劉瑞元.加權(quán)歐氏距離及其應(yīng)用[J].數(shù)理統(tǒng)計(jì)與管理,2002,21(5):17-19.

LIU Ruiyuan. Euclid distance with weight and its applications[J]. Application of Statistics and Managerment,2002,21(5):17-19.

[11] 宋宇辰,張玉英,孟海東.一種基于加權(quán)歐氏距離聚類方法的研究[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(4):179-180.

SONG Yuchen, ZHANG Yuying, MENG Haidong. Research based on euclid distance with weights of clustering method[J]. Computer Engineering and Applications,2007,43(4):179-180.

[12] 陳治平.基于復(fù)雜對(duì)象分解的相似性計(jì)算方法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(34):149-162.

CHEN Zhiping. Similarity measurement based on decomposition of complex object[J]. Computer Engineering and Applications,2008,44(34):149-162.

中圖分類號(hào)TP391.41

DOI:10.3969/j.issn.1672-9722.2016.03.009

作者簡(jiǎn)介:朱俚治,男,工程師,研究方向:計(jì)算機(jī)技術(shù)、信息安全。

收稿日期:2015年9月3日,修回日期:2015年10月19日