李 婧

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 400047)

一種改進(jìn)的最近鄰聚類算法*

李 婧

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 400047)

傳統(tǒng)的最近鄰聚類算法一般采用歐式距離的計算準(zhǔn)則，當(dāng)各個分量的分布不一樣時，采用歐式距離有著明顯的缺點； 針對以上問題，采用標(biāo)準(zhǔn)化歐式距離的計算準(zhǔn)則，將熵值法引入到算法中，提出了基于熵值法和標(biāo)準(zhǔn)化歐式距離的改進(jìn)的最近鄰聚類算法； 熵值法用來修訂算法的標(biāo)準(zhǔn)化歐式距離計算公式，以提高算法的聚類精確程度.

聚類；最近鄰算法；標(biāo)準(zhǔn)化歐式距離；信息熵

聚類[1]分析研究有很長的歷史，幾十年來，其重要性及與其他研究方向的交叉特性得到人們的肯定. 聚類是數(shù)據(jù)挖掘、模式識別等研究方向的重要研究內(nèi)容之一，在識別數(shù)據(jù)內(nèi)在結(jié)構(gòu)方面具有極其重要的作用. 聚類就是將數(shù)據(jù)對象分成類或簇的過程，使同簇的對象之間具有很高的相似度，而不同簇的對象高度相異. 聚類分析的典型應(yīng)用包括物種的分類和分子生物學(xué)中的基因分類，商業(yè)中對消費客戶的分類，城市規(guī)劃中的地理數(shù)據(jù)分析等等.目前存在大量的聚類算法，由于劃分標(biāo)準(zhǔn)不明確，所以很難對聚類算法提出一個明確的分類. 根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則以及應(yīng)用這些規(guī)則的方法，聚類算法有多種分類方法，本文將聚類算法大體劃分為劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法等[1].

最近鄰聚類算法是聚類算法中最基本的算法之一， 熵是熱力學(xué)中的基本概念，文獻(xiàn)[2]利用信息熵對數(shù)據(jù)對象的屬性進(jìn)行賦權(quán)，并利用權(quán)值來修改距離計算公式. 文獻(xiàn)[3]研究了熵權(quán)法在股票市場上的應(yīng)用. 文獻(xiàn)[4]是基于熵的概念對其權(quán)重給予確定的一種新方法，對融合網(wǎng)絡(luò)服務(wù)質(zhì)量效率保障研究. 最近鄰聚類法是聚類算法中最基本的算法，它普遍采用歐氏距離的計算準(zhǔn)則. 由于歐式距離存在明顯的缺點. 簡單的來說，主要有兩個缺點：一是在實際問題中對象包含許多種不同量綱的屬性；二是沒有考慮各個分量的分布(期望、方差等)可能不同. 鑒于此，本文提出了一種基于熵值法確定數(shù)據(jù)屬性的權(quán)值，采用賦權(quán)的標(biāo)準(zhǔn)化歐式距離作為相似度測量依據(jù)的最近鄰聚類算法，該算法較于傳統(tǒng)的歐式距離算法在一定程度上提高了聚類的精確度和穩(wěn)定性.

1 熵值法確定權(quán)值

1.1 相關(guān)定義

設(shè)待聚類的數(shù)據(jù)對象集為A={x1，x2，…，xn}，且向量xi=(xi1，xi2，…，xim)，xik是xi的第k(k=1，2，…，g)維屬性，m為對象屬性的維數(shù)，有如下定義：

定義1[7](歐式距離)設(shè)兩個向量xi=(xi1，xi2，…，xim)和xj=(xj1，xj2，…，xjm)分別表示兩個數(shù)據(jù)對象，則數(shù)據(jù)對象xi和xj之間的歐式距離：

定義2(標(biāo)準(zhǔn)化歐式距離) 數(shù)據(jù)對象xi和xj之間的標(biāo)準(zhǔn)化歐式距離計算公式：

其中sk為第k個分量的標(biāo)準(zhǔn)差.

1.2 熵值法改進(jìn)距離計算公式

熵是熱力學(xué)中的概念，最早由申農(nóng)引入到信息論，主要用于測量系統(tǒng)的無序程度. 熵權(quán)法是一種可以用于多對象、多指標(biāo)的綜合評價方法.目前已經(jīng)在工程技術(shù)、管理科學(xué)乃至社會經(jīng)濟(jì)等領(lǐng)域得到廣泛應(yīng)用[3].本文使用信息熵的概念度量屬性權(quán)值的大小，得出賦權(quán)的標(biāo)準(zhǔn)化歐式距離計算公式.

使用熵值法確定權(quán)值的步驟如下：

1) 設(shè)有n個待聚類的數(shù)據(jù)對象，所有的數(shù)據(jù)對象包含m維屬性，則屬性值矩陣：

其中xij表示對象xi的第j維屬性的度量.

2) 計算第j維屬性對應(yīng)的第i個數(shù)據(jù)對象的屬性值比重：

其中rij為對象xi的第j維屬性的屬性值比重.

3) 計算第j維屬性的熵值：

4) 第j維屬性的權(quán)值[4，5]：

利用標(biāo)準(zhǔn)化的歐式距離及信息熵計算屬性權(quán)值，將數(shù)據(jù)對象xi和xj之間的歐式距離計算公式修改為下式：

利用改進(jìn)的距離計算公式可以更為精確的計算出各個數(shù)據(jù)之間的差距，在一定程度上提高了聚類精確程度.

2 基于熵值法的改進(jìn)的最近鄰聚類算法

2.1 最近鄰聚類算法基本思想[6]

最近鄰聚類算法是以全部訓(xùn)練樣本作為代表點，計算測試樣本與這些代表點的距離，即所有樣本的距離，并以最近鄰者的類別作為決策. 也就是說有n個待分類的模式樣本{x1，x2，…，xn}，要求按閾值T分類到以z1，z2，…，為聚類中心的模式類中.

2.2 改進(jìn)的最近鄰聚類算法算法描述

輸入：需要聚類的數(shù)據(jù)對象集A和閾值T；輸出：以z1，z2，…，為聚類中心的聚類。任取一個模式樣本xi作為第一個聚類中心的初始值，例如令x1=Z1；計算模式樣本x2到x1的加權(quán)的標(biāo)準(zhǔn)化歐式距離D21=‖x2-x1‖若D21>T，定義一個新的聚類中心Z2=x2，否則x2∈以Z1為中心的聚類.假設(shè)已有聚類中心Z1，Z2，計算D31=‖x3-Z1‖和D32=‖x3-Z2‖若D31>T且D32>T，則建立第三個聚類中心Z3=x3，否則x3∈離Z1和Z2中最近者，即最近鄰的聚類中心.依次類推，按照這種最近鄰規(guī)則，直到將所有的n個模式樣本全部分類.

3 結(jié)束語

本文結(jié)合熵值法和加權(quán)的標(biāo)準(zhǔn)化歐式距離提出了一種改進(jìn)的最近鄰聚類算法，熵值法用來計算對數(shù)據(jù)對象的各個屬性的權(quán)值，用改進(jìn)的權(quán)值修正加權(quán)的標(biāo)準(zhǔn)化歐式距離計算公式，以提高了聚類的精確度. 相比較與傳統(tǒng)的最近鄰聚類算法，改進(jìn)的算法較之于傳統(tǒng)的最近鄰算法在算法的計算效率上有所提高，聚類的精確度明確增強.

[1] HAN J W，MICHELINE K. Data mining concepts andtechniques [M].Beijing： China Machine Press，2001

[2] 原福永，張曉彩，羅思標(biāo).基于信息熵的精確屬性賦權(quán)K-means聚類算法[J].計算機應(yīng)用，2011，31(6)：1675-1677

[3] 陳孝新.熵權(quán)法在股票市場的應(yīng)用[J].商業(yè)研究，2004，(16)：139

[4] 陳雷，王延章.熵權(quán)法對融合網(wǎng)絡(luò)服務(wù)質(zhì)量效率保障研究[J].計算機工程與應(yīng)用，2005，41(23)：1-3

[5] 高孝偉.熵權(quán)法在教學(xué)評優(yōu)中的應(yīng)用研究[J].中國地質(zhì)教育，2008，17(4)：100-104

[6] 鐘珞，潘昊等.模式識別[M].武漢：武漢大學(xué)出版社，2009，9

[7] 仝雪嬌，孟凡榮，王志曉.對K-means初始聚類中心的優(yōu)化[J].計算機工程與設(shè)計，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-)，女，重慶巫山人，碩士研究生，從事智能計算及應(yīng)用研究.

TP273

A

責(zé)任編輯：代小紅