李 婧
(重慶師范大學 數(shù)學學院,重慶 400047)
一種改進的最近鄰聚類算法*
李 婧
(重慶師范大學 數(shù)學學院,重慶 400047)
傳統(tǒng)的最近鄰聚類算法一般采用歐式距離的計算準則,當各個分量的分布不一樣時,采用歐式距離有著明顯的缺點; 針對以上問題,采用標準化歐式距離的計算準則,將熵值法引入到算法中,提出了基于熵值法和標準化歐式距離的改進的最近鄰聚類算法; 熵值法用來修訂算法的標準化歐式距離計算公式,以提高算法的聚類精確程度.
聚類;最近鄰算法;標準化歐式距離;信息熵
聚類[1]分析研究有很長的歷史,幾十年來,其重要性及與其他研究方向的交叉特性得到人們的肯定. 聚類是數(shù)據(jù)挖掘、模式識別等研究方向的重要研究內容之一,在識別數(shù)據(jù)內在結構方面具有極其重要的作用. 聚類就是將數(shù)據(jù)對象分成類或簇的過程,使同簇的對象之間具有很高的相似度,而不同簇的對象高度相異. 聚類分析的典型應用包括物種的分類和分子生物學中的基因分類,商業(yè)中對消費客戶的分類,城市規(guī)劃中的地理數(shù)據(jù)分析等等.目前存在大量的聚類算法,由于劃分標準不明確,所以很難對聚類算法提出一個明確的分類. 根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則以及應用這些規(guī)則的方法,聚類算法有多種分類方法,本文將聚類算法大體劃分為劃分方法、層次方法、基于密度的方法、基于網格的方法等[1].
最近鄰聚類算法是聚類算法中最基本的算法之一, 熵是熱力學中的基本概念,文獻[2]利用信息熵對數(shù)據(jù)對象的屬性進行賦權,并利用權值來修改距離計算公式. 文獻[3]研究了熵權法在股票市場上的應用. 文獻[4]是基于熵的概念對其權重給予確定的一種新方法,對融合網絡服務質量效率保障研究. 最近鄰聚類法是聚類算法中最基本的算法,它普遍采用歐氏距離的計算準則. 由于歐式距離存在明顯的缺點. 簡單的來說,主要有兩個缺點:一是在實際問題中對象包含許多種不同量綱的屬性;二是沒有考慮各個分量的分布(期望、方差等)可能不同. 鑒于此,本文提出了一種基于熵值法確定數(shù)據(jù)屬性的權值,采用賦權的標準化歐式距離作為相似度測量依據(jù)的最近鄰聚類算法,該算法較于傳統(tǒng)的歐式距離算法在一定程度上提高了聚類的精確度和穩(wěn)定性.
設待聚類的數(shù)據(jù)對象集為A={x1,x2,…,xn},且向量xi=(xi1,xi2,…,xim),xik是xi的第k(k=1,2,…,g)維屬性,m為對象屬性的維數(shù),有如下定義:
定義1[7](歐式距離)設兩個向量xi=(xi1,xi2,…,xim)和xj=(xj1,xj2,…,xjm)分別表示兩個數(shù)據(jù)對象,則數(shù)據(jù)對象xi和xj之間的歐式距離:
定義2(標準化歐式距離) 數(shù)據(jù)對象xi和xj之間的標準化歐式距離計算公式:
其中sk為第k個分量的標準差.
熵是熱力學中的概念,最早由申農引入到信息論,主要用于測量系統(tǒng)的無序程度. 熵權法是一種可以用于多對象、多指標的綜合評價方法.目前已經在工程技術、管理科學乃至社會經濟等領域得到廣泛應用[3].本文使用信息熵的概念度量屬性權值的大小,得出賦權的標準化歐式距離計算公式.
使用熵值法確定權值的步驟如下:
1) 設有n個待聚類的數(shù)據(jù)對象,所有的數(shù)據(jù)對象包含m維屬性,則屬性值矩陣:
其中xij表示對象xi的第j維屬性的度量.
2) 計算第j維屬性對應的第i個數(shù)據(jù)對象的屬性值比重:
其中rij為對象xi的第j維屬性的屬性值比重.
3) 計算第j維屬性的熵值:
4) 第j維屬性的權值[4,5]:
利用標準化的歐式距離及信息熵計算屬性權值,將數(shù)據(jù)對象xi和xj之間的歐式距離計算公式修改為下式:
利用改進的距離計算公式可以更為精確的計算出各個數(shù)據(jù)之間的差距,在一定程度上提高了聚類精確程度.
最近鄰聚類算法是以全部訓練樣本作為代表點,計算測試樣本與這些代表點的距離,即所有樣本的距離,并以最近鄰者的類別作為決策. 也就是說有n個待分類的模式樣本{x1,x2,…,xn},要求按閾值T分類到以z1,z2,…,為聚類中心的模式類中.
輸入:需要聚類的數(shù)據(jù)對象集A和閾值T;輸出:以z1,z2,…,為聚類中心的聚類。任取一個模式樣本xi作為第一個聚類中心的初始值,例如令x1=Z1;計算模式樣本x2到x1的加權的標準化歐式距離D21=‖x2-x1‖若D21>T,定義一個新的聚類中心Z2=x2,否則x2∈以Z1為中心的聚類.假設已有聚類中心Z1,Z2,計算D31=‖x3-Z1‖和D32=‖x3-Z2‖若D31>T且D32>T,則建立第三個聚類中心Z3=x3,否則x3∈離Z1和Z2中最近者,即最近鄰的聚類中心.依次類推,按照這種最近鄰規(guī)則,直到將所有的n個模式樣本全部分類.
本文結合熵值法和加權的標準化歐式距離提出了一種改進的最近鄰聚類算法,熵值法用來計算對數(shù)據(jù)對象的各個屬性的權值,用改進的權值修正加權的標準化歐式距離計算公式,以提高了聚類的精確度. 相比較與傳統(tǒng)的最近鄰聚類算法,改進的算法較之于傳統(tǒng)的最近鄰算法在算法的計算效率上有所提高,聚類的精確度明確增強.
[1] HAN J W,MICHELINE K. Data mining concepts andtechniques [M].Beijing: China Machine Press,2001
[2] 原福永,張曉彩,羅思標.基于信息熵的精確屬性賦權K-means聚類算法[J].計算機應用,2011,31(6):1675-1677
[3] 陳孝新.熵權法在股票市場的應用[J].商業(yè)研究,2004,(16):139
[4] 陳雷,王延章.熵權法對融合網絡服務質量效率保障研究[J].計算機工程與應用,2005,41(23):1-3
[5] 高孝偉.熵權法在教學評優(yōu)中的應用研究[J].中國地質教育,2008,17(4):100-104
[6] 鐘珞,潘昊等.模式識別[M].武漢:武漢大學出版社,2009,9
[7] 仝雪嬌,孟凡榮,王志曉.對K-means初始聚類中心的優(yōu)化[J].計算機工程與設計,2011(8):2721-2723
Keywords:clustering;nearest neighbor algorithm;standardized Euclidean distance;information entropy
A Kind of Improved Nearest Neighbor Clustering Algorithm
LIJing
(School of Mathematics, Chongqing Normal University, Chongqing 400047, China)
The traditional nearest neighbor clustering algorithm commonly used Euclidean distance calculation rules, when the various components of the distribution are not the same, the using of Euclidean distance has obvious shortcomings.According to this problem, this paper uses standardized Euclidean distance calculation formula, by introducing entropy method to the algorithm, proposes the improved nearest neighbor clustering algorithm based on entropy method and standardized Euclidean distance. The entropy method is used to amend the standardized Euclidean distance calculation formula of the algorithm to improve clustering accuracy of the algorithm.
1672-058X(2013)10-0061-03
2013-03-13;
2013-04-20.
李婧(1988-),女,重慶巫山人,碩士研究生,從事智能計算及應用研究.
TP273
A
責任編輯:代小紅