李 婧

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

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

李 婧

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

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

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

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

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

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

1.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

本文結(jié)合熵值法和加權(quán)的標(biāo)準(zhǔn)化歐式距離提出了一種改進(jìn)的最近鄰聚類算法，熵值法用來(lái)計(jì)算對(duì)數(shù)據(jù)對(duì)象的各個(gè)屬性的權(quán)值，用改進(jìn)的權(quán)值修正加權(quán)的標(biāo)準(zhǔn)化歐式距離計(jì)算公式，以提高了聚類的精確度. 相比較與傳統(tǒng)的最近鄰聚類算法，改進(jìn)的算法較之于傳統(tǒng)的最近鄰算法在算法的計(jì)算效率上有所提高，聚類的精確度明確增強(qiá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].計(jì)算機(jī)應(yīng)用，2011，31(6)：1675-1677

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

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

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

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

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

TP273

A

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