一種加權歐氏距離聚類算法的改進*

朱俚治

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

?

一種加權歐氏距離聚類算法的改進*

朱俚治

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

摘要聚類算法是一種無監督學習的算法,能夠將相似度強的數據聚類到一個族內,并且能夠將屬性相異的數據劃分到不同的族里。當今聚類算法可分為傳統的聚類算法和非傳統的聚類算法。傳統的聚算法有:基于劃分聚類算法、基于層次聚類算法等算法。人們在使用劃分法和層次法進行聚類時,是通過計算聚類對象之間屬性的距離來實現聚類,因此歐氏距離公式和加權歐氏距離公式在這兩種聚類算法中常用的算法。加權歐氏距離計算公式在聚類時著重聚類對象屬性權重的選擇,所以此文從聚類對象的相似度和對象屬性對應的權重,這兩個方面來考慮聚類成功的概率。論文作者提出的算法思想是,如果某個聚類對象具有若干的屬性,那么首先計算該聚類對象屬性的相似度,再根據該屬性對應的權重是否為關鍵權重,如果是此屬性對應的權重是關鍵權重,那么該對象聚類的成功率較高。

關鍵詞加權歐氏距離; 相似度; 權重; 屬性; 聚類

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引言

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

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

2聚類的算法簡介

1) 聚類分析的定義

聚類是將數據劃分成群組的過程,研究如何在沒有訓練的條件下把對象劃分為若干類。通過確定數據之間在預先制定的屬性上的相似性來完成聚類任務,這樣最相似的數據就聚集成族[7~9]。

2) 聚類算法

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

3) 聚類算法的規則

在聚類算法中劃分方法,層次方法和基于網格的聚類算法都是通過計算對象屬性之間的距離來判斷屬性的相似性[7~9]。應用于聚類算法中的對象屬性的距離計算的公式有:歐氏距離聚類公式、加權歐氏距離聚類公式、馬氏距離聚類公式。因此距離計算公式在聚類算法中有相當重要的作用。

3加權歐氏距離簡介

在傳統的聚類算法中常用的聚類方法是通過對象的距離來完成聚類[2~3]。在很多的聚類算法中都采用歐氏距離公式作為聚類時的依據。在歐氏距離聚類方法中有兩種歐氏距離公式:非加權歐氏距離和加權歐氏距離,本文將采用加權歐氏距離作為研究的對象。

1) 非加權歐氏距離計算公式[2]:

------------------------------2) 加權歐氏距離計算法公式[2]:

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

4加權歐氏距離公式中聚類對象屬性的比較

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

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

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

3) 根據以上的討論和分析有以下的結論:

如果對象A′某些屬性十分接近于對象A的某些屬性時:

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

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

5聚類對象屬性相似度的計算

5.1聚類對象的屬性偏離概率估量

根據上一節的研究有以下的分析和討論:

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

如果A′與A屬于惡意軟件,當對象A′的屬性與對象A的屬性偏離程度達到了100%時,這時它們的屬性完全沒有相同之處。但是當對象A′的屬性與對象A的屬性相似程度達到了100%時,這時它們的屬性完全相同,相似程度非常強。

如果A′與A屬于非惡意軟件,當對象A′的屬性與對象A的屬性偏離程度達到了100%時,這時它們的屬性完全沒有相同之處。但是當對象A′的屬性與對象A的屬性相似程度達到了100%時,這時它們的屬性完全相同,相似程度非常強。

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

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

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

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

3) 在聚類過程中,如果需對象A′的屬性小于已知對象A的屬性時,那么A′/A的比值將小于1。當A′/A的比值越小時,這時對象A′的屬性值小于或遠小于已知對象A的屬性值時,則A′的屬性偏離A的概率就越大。

5.2聚類對象屬性相似度的估計

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

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

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

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

6聚類對象的屬于與權重

1) 聚類對象的屬性

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

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

2) 聚類對象的屬性與其權重

(1)A′的屬性Xip與A的屬性Xjp相對應

權重Wi1與Xi1-Xj1對應,權重Wi2與Xi2-Xj2對應,…,權重Wip與Xip-Xjp對應。

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

7結語

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

參 考 文 獻

[1] 孟海東,張玉英,宋飛燕.一種基于加權歐氏距離聚類方法的研究[J].計算機應用,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] 董旭,魏振軍.一種加權歐氏距離聚類方法[J],信息工程大學學報,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] 吳香華,牛生杰,吳誠,等.馬氏距離聚類分析中協方差矩陣估算的改進[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] 邵峰晶,于忠清,王金龍,等.數據挖掘原理與算法[M].北京:科學出版社,2009.

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

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

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

[6] 吳帆,李石君.一種高效的層次聚類分析算法[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].西南名族大學學報·自然科學版,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] 方媛,車啟鳳.數據挖掘之聚類算法綜述[J].河西學院學報,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] 賀玲,吳玲達,蔡益朝.數據挖掘中的聚類算法綜述[J].計算機應用,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] 劉瑞元.加權歐氏距離及其應用[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] 宋宇辰,張玉英,孟海東.一種基于加權歐氏距離聚類方法的研究[J].計算機工程與應用,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] 陳治平.基于復雜對象分解的相似性計算方法[J].計算機工程與應用,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.

中圖分類號TP391.41

DOI:10.3969/j.issn.1672-9722.2016.03.009

作者簡介:朱俚治,男,工程師,研究方向:計算機技術、信息安全。

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