基于改進(jìn)k-medoids算法的XML文檔聚類(lèi)

馮少榮，潘煒煒，林子雨

(廈門(mén)大學(xué)信息科學(xué)與技術(shù)學(xué)院，福建廈門(mén)361005)

1 概述

XML由于其具有通用性、可擴(kuò)展性、易用性、自描述性、異構(gòu)性和開(kāi)發(fā)性等特點(diǎn)［1-2］，已成為Web上通用的數(shù)據(jù)表示和交換格式。隨著XML文檔數(shù)量呈現(xiàn)出爆炸式的增長(zhǎng)，人們迫切地需要從這些文檔中獲取相應(yīng)的信息知識(shí)。XML文檔的自動(dòng)聚類(lèi)，不僅可以增強(qiáng)網(wǎng)絡(luò)中XML文檔的組織性，同時(shí)還能從海量的XML文檔中發(fā)現(xiàn)未知、隱含的知識(shí)和文檔間的聯(lián)系［3-5］，具有重要的研究意義。由于XML文檔除了一些文本內(nèi)容之外，還具有元素父親節(jié)點(diǎn)、子孫節(jié)點(diǎn)嵌套等結(jié)構(gòu)特征，因此傳統(tǒng)文檔聚類(lèi)算法并不適合于XML文檔的聚類(lèi)。目前對(duì)XML文檔的聚類(lèi)，主要有 k-means(均值)［6］和 k-medoids(中心點(diǎn))［7］2種基于劃分的方法。由于XML文檔數(shù)據(jù)集包含一個(gè)個(gè)離散的對(duì)象，而k-means的均值并不能真正反映整個(gè)簇的實(shí)際情況，也沒(méi)有實(shí)際的意義。同時(shí)k-means算法對(duì)孤立點(diǎn)十分敏感，相比之下，kmedoids采用某一個(gè)具體對(duì)象作為聚類(lèi)中心，很好地解決了k-means對(duì)孤立點(diǎn)敏感這一問(wèn)題。同時(shí)，k-medoids算法具有劃分簡(jiǎn)單、執(zhí)行時(shí)間快的特點(diǎn)，其操作也適合于XML文檔聚類(lèi)。因此，k-medoids在XML文檔聚類(lèi)中得到了廣泛的應(yīng)用。

在基于劃分的文檔聚類(lèi)中，一個(gè)最基本的問(wèn)題是要確定聚類(lèi)的個(gè)數(shù)k。這樣對(duì)算法的使用造成了很大的不便，且無(wú)法通過(guò)樣本的特征自動(dòng)地確定聚類(lèi)個(gè)數(shù)。此外，基于劃分的聚類(lèi)、初始中心點(diǎn)或者質(zhì)心的選擇，對(duì)整個(gè)聚類(lèi)過(guò)程和聚類(lèi)結(jié)果也有較大的影響，不合理的初始中心點(diǎn)選擇容易使得算法得出局部最優(yōu)解。針對(duì)以上2個(gè)問(wèn)題，本文運(yùn)用模糊聚類(lèi)和遺傳算法(Genetic Algorithm，GA)來(lái)確定聚類(lèi)個(gè)數(shù)和最佳初始聚類(lèi)中心，并在此基礎(chǔ)上結(jié)合k-medoids算法實(shí)現(xiàn)對(duì)XML文檔的聚類(lèi)。

2 XML文檔相似度計(jì)算

XML文檔的結(jié)構(gòu)是一個(gè)樹(shù)狀的模型，XML中既包含結(jié)構(gòu)信息，也包含語(yǔ)義內(nèi)容信息，以往的研究主要圍繞這2個(gè)方面展開(kāi)。但文獻(xiàn)［8］證明語(yǔ)義內(nèi)容信息在XML文檔相似性度量中作用不大，并且由于不斷查詢WordNet詞典，導(dǎo)致算法計(jì)算開(kāi)銷(xiāo)增加。因此，本文主要基于結(jié)構(gòu)來(lái)度量XML文檔相似性。

多數(shù)對(duì)XML文檔的操作都是映射成XML文檔樹(shù)再進(jìn)行相關(guān)運(yùn)算。文獻(xiàn)［9-11］提出了基于編輯距離的方法計(jì)算文檔的相似度。這種方法的缺點(diǎn)是復(fù)雜度過(guò)高，不利于實(shí)際的應(yīng)用。文獻(xiàn)［12］提出了基于樹(shù)-路徑的模型，相對(duì)于編輯距離的方法復(fù)雜度較小。但是這種方法在匹配2棵文檔樹(shù)路徑時(shí)用的是路徑全匹配的策略，這樣的結(jié)果會(huì)丟失一部分的相似信息，導(dǎo)致相似度的計(jì)算有所偏差。本文基于文獻(xiàn)［13］公共子路徑相似度的計(jì)算方法，實(shí)現(xiàn)文檔相似度的計(jì)算。

定義1子序列及公共子序列

稱(chēng)序列 ＜ai1，ai2，…，aik＞ 為另一個(gè)序列 ＜a1，a2，…，an＞的子序列，當(dāng)且僅當(dāng)1≤i1＜i2＜… ＜ik≤n;稱(chēng)序列 ＜ a1，a2，…，an＞ 和 ＜ b1，b2，…，bm＞ 的公共子序列為 ＜c1，c2，…，ck＞，當(dāng)且僅當(dāng) ＜c1，c2，…，ck＞既是 ＜a1，a2，…，an＞ 的子序列，又是 ＜ b1，b2，…，bm＞的子序列。

在計(jì)算路徑相似度時(shí)，本文引入位置權(quán)重向量w=(w(1)，w(2)，…，w(n))，其中，1，2，…，n 為公共子序列的下標(biāo)。加入位置權(quán)重的意義在于，一個(gè)相同的節(jié)點(diǎn)位置越靠前，其貢獻(xiàn)的信息量越大，越是重要，所以位置權(quán)重向量滿足:當(dāng)i＞j，w(i)＞w(j)。

定義2路徑相似度

設(shè)通過(guò)路徑 P1=(f1，x1，x2，…，xn)和 P2=(f2，y1，y2，…，ym)求得的最長(zhǎng)公共子序列為 P=(a1，a2，…，ak)，其中，k 為 P1和 P2最長(zhǎng)公共子序列的長(zhǎng)度。記P中節(jié)點(diǎn)在P1中的位置下標(biāo)為(l1，l2，…，lk)，記P中節(jié)點(diǎn)在 P2中的位置下標(biāo)為(h1，h2，…，hk)。由此可得P1和P2的路徑相似度S計(jì)算公式為:

根據(jù)路徑相似度可以得出文檔相似度的計(jì)算方法。設(shè)2個(gè)文檔D1和D2，通過(guò)計(jì)算2個(gè)文檔之間的每條路徑所能達(dá)到的最大的相似度值S，得到文檔相似度Sim的計(jì)算公式為:

根據(jù)所得到的文檔相似度公式，計(jì)算2個(gè)文檔的相似度的算法偽代碼如下:

輸入 2棵文檔樹(shù)Doc1，Doc2

輸出 2個(gè)文檔的相似度Sim

計(jì)算2個(gè)文檔的相似度的計(jì)算量，復(fù)雜度由以下關(guān)鍵處理過(guò)程決定:

(1)2個(gè)文檔各自所包含的路徑數(shù)量乘積決定了獲得最長(zhǎng)公共子序列和式(1)的執(zhí)行次數(shù);

(2)2個(gè)文檔各自所包含的路徑數(shù)量決定了式(2)的計(jì)算量和復(fù)雜度。

因此，計(jì)算2個(gè)文檔的相似度的復(fù)雜度為:O(|pathdoc1|×|pathdoc2|×tLSC+tPathSimilarity)。其中，|pathdoc1|，|pathdoc2|為文檔1、文檔2所包含的路徑數(shù)量;tLSC為獲得2條路徑的最長(zhǎng)公共子序列所花費(fèi)的搜索時(shí)間;tPathSimilarity為根據(jù)式(2)計(jì)算文檔相似度所花費(fèi)的時(shí)間。

該算法具有2個(gè)顯著特點(diǎn):(1)采用最長(zhǎng)公共子序列來(lái)匹配2條路徑，使得路徑的相似信息的獲取更完備;(2)在路徑相似度的計(jì)算中引入了位置權(quán)重，使得相似度計(jì)算更合理，接近實(shí)際。

3 XML文檔聚類(lèi)的有效性指標(biāo)

一個(gè)緊致的、良性劃分的聚類(lèi)應(yīng)當(dāng)使聚類(lèi)中心的間距盡可能大，而XML文檔樣本與其中心間距盡可能小假設(shè)對(duì)于數(shù)據(jù)集 D={x1，x2，…，xn}，最終聚類(lèi)個(gè)數(shù)為 k，則聚類(lèi)結(jié)果可表示為(D1，D2，…，Dk)，聚類(lèi)的中心點(diǎn)表示為(p1，p2，…，pk)。這種劃分的結(jié)果可以表示為一個(gè) k×n階矩陣 U=(uij)k×n，uij∈［0，1］，對(duì)任意的。對(duì)任意的因此，可以根據(jù)這個(gè)特征定義XML文檔聚類(lèi)的有效性指標(biāo)Q如下:

其中，Q值越小，則其聚類(lèi)質(zhì)量越好。

4 k-medoids算法聚類(lèi)個(gè)數(shù)的確定

利用k-medoids算法進(jìn)行XML文檔聚類(lèi)，聚類(lèi)個(gè)數(shù)的確定是一個(gè)關(guān)鍵的問(wèn)題。確定聚類(lèi)個(gè)數(shù)過(guò)程的性能最終取決于所應(yīng)用的聚類(lèi)算法。另一方面，由于一般文檔聚類(lèi)方法并不能很好地適應(yīng)XML文檔聚類(lèi)。本文基于這兩點(diǎn)，提出了一種快速有效的基于模糊聚類(lèi)的方法，能夠很好地確定聚類(lèi)個(gè)數(shù)。

基于模糊等價(jià)關(guān)系的聚類(lèi)方法，能夠簡(jiǎn)單地通過(guò)對(duì)模糊相似矩陣的λ截運(yùn)算，快速地產(chǎn)生一個(gè)聚類(lèi)結(jié)果。本文利用XML文檔聚類(lèi)必須先得出相似度矩陣的這一必要過(guò)程，通過(guò)模糊等價(jià)矩陣的方法，快速得到不同λ閾值下的聚類(lèi)個(gè)數(shù)，最終用聚類(lèi)有效性指標(biāo)作為評(píng)估函數(shù)，確定最佳的聚類(lèi)個(gè)數(shù)。

由于相似度取值在［0，1］內(nèi)，顯而易見(jiàn)，λ也落在這個(gè)區(qū)間中?？梢员闅v［0，1］區(qū)間來(lái)獲取不同的λ值，進(jìn)行基于模糊等價(jià)關(guān)系的聚類(lèi)。但需要確定λ在［0，1］之間如何取值。本文根據(jù)相似矩陣內(nèi)部不同取值之間的差值大小，動(dòng)態(tài)決定λ值大小。

定義3 設(shè)d為λ在［0，1］間取值的間隔值，且(s1，s2，…，sn)為相似度矩陣中的相似度值從小到大的排列序列，即滿足s1≤s2≤…≤sn，由此得到d的計(jì)算公式為:

因此，可以得到基于模糊等價(jià)關(guān)系確定聚類(lèi)個(gè)數(shù)的算法如下:

輸入 XML文檔數(shù)據(jù)集的相似度矩陣Rsim

輸出 最佳聚類(lèi)個(gè)數(shù)k

確定聚類(lèi)個(gè)數(shù)的計(jì)算量，復(fù)雜度由以下關(guān)鍵處理過(guò)程決定:

(1)獲得樣本集的模糊相似度矩陣;

(2)通過(guò)“平方法”把模糊相似矩陣改造成模糊等價(jià)矩陣;

(3)根據(jù)式(4)計(jì)算出閾值d;

(4)根據(jù)計(jì)算得到的閾值d，利用不同的λ取值下的截矩陣，進(jìn)行模糊等價(jià)關(guān)系的聚類(lèi);

(5)利用評(píng)價(jià)指標(biāo)函數(shù)，計(jì)算每次聚類(lèi)結(jié)果的評(píng)價(jià)值，并記錄評(píng)價(jià)值最高的聚類(lèi)結(jié)果的聚類(lèi)個(gè)數(shù)。

因此，確定聚類(lèi)個(gè)數(shù)的計(jì)算復(fù)雜度為O(tequal_sim+n×tvalue)，其中，tequal_sim為獲得模糊等價(jià)矩陣及計(jì)算閾值所花費(fèi)的時(shí)間;n為根據(jù)閾值劃分［0，1］區(qū)間的個(gè)數(shù);tvalue為根據(jù)聚類(lèi)有效性指標(biāo)計(jì)算聚類(lèi)評(píng)價(jià)值所花費(fèi)的時(shí)間。

5 k-medoids最佳初始聚類(lèi)中心點(diǎn)的確定

對(duì)于初始中心點(diǎn)的選擇問(wèn)題，本文引入了遺傳算法，通過(guò)遺傳算法所具有的全局最優(yōu)解的搜索能力，改善確定最佳初始中心點(diǎn)這一步驟，使得在遺傳算法的個(gè)體迭代過(guò)程中，逐步把聚類(lèi)的中心點(diǎn)向?qū)嶋H的聚類(lèi)中心點(diǎn)靠攏，最后達(dá)到獲得最優(yōu)解的目的。遺傳算法與k-medoids結(jié)合的算法已有研究者提出類(lèi)似的想法［14-15］，雖然其算法對(duì)一般的聚類(lèi)問(wèn)題具有普遍適應(yīng)性，但是針對(duì)XML文檔的聚類(lèi)會(huì)存在一些問(wèn)題。為此，本文提出了針對(duì)XML文檔聚類(lèi)的相關(guān)特征的適合XMIL文檔聚類(lèi)的遺傳算法。

5．1 遺傳算法的操作過(guò)程

5．1．1 編碼策略

本文所采用的編碼方式是實(shí)數(shù)編碼，結(jié)合XML文檔聚類(lèi)的特點(diǎn)以及結(jié)合k-medoids算法，提出了以初始聚類(lèi)中心為基因位而形成的編碼方式。

設(shè)數(shù)據(jù)樣本集D中XML文檔的個(gè)數(shù)為N，染色體基因位a的取值范圍為［1，N］。這樣設(shè)定的好處在于，每個(gè)基因位既可以對(duì)應(yīng)樣本集D中位置，同時(shí)也和相似度矩陣中該對(duì)象的行列坐標(biāo)一一對(duì)應(yīng)，使得之后的其他遺傳算子操作十分方便。假定聚類(lèi)個(gè)數(shù)為 k，隨機(jī)初始化的聚類(lèi)中心點(diǎn)為(a1，a2，…，ak)，其中，當(dāng) i＜j，ai＜aj;當(dāng) i≠j，ai≠aj。于是一個(gè)具有 k 長(zhǎng)度的個(gè)體的染色體可形式化為［a1a2…ak］。從編碼方式來(lái)看，一條染色體代表的含義是以這些基因位為聚類(lèi)中心點(diǎn)的一次聚類(lèi)結(jié)果。在運(yùn)用k-medoids算法的過(guò)程中，相同的初始化中心點(diǎn)，最后所得到的聚類(lèi)結(jié)果是唯一的。因此，一條染色體編碼和一次聚類(lèi)結(jié)果是唯一確定的關(guān)系。

5．1．2 種群的初始化

本文希望初始化的解能在樣本解空間中均勻采樣，所以，在N個(gè)樣本數(shù)據(jù)集的聚類(lèi)中，隨機(jī)生成2N個(gè)初始個(gè)體，然后選擇較優(yōu)的N個(gè)個(gè)體作為初始種群。

5．1．3 遺傳操作算子的實(shí)現(xiàn)

本文采用的選擇算子通過(guò)適應(yīng)值比例選擇，其中每個(gè)個(gè)體被選擇的期望值為其適應(yīng)值和群體的平均適應(yīng)值的比值，該選擇算子使用輪盤(pán)賭方式實(shí)現(xiàn)。采用的交叉方式是一致交叉。至于變異算子，由于變異概率的取值都很小，因此染色體有時(shí)候根本就不發(fā)生變異，這樣導(dǎo)致浪費(fèi)大量的計(jì)算資源。針對(duì)這種情況，一般采取如下變通的方法:

(1)計(jì)算個(gè)體發(fā)生變異的概率

以原始的變異概率pm為基礎(chǔ)，可以計(jì)算出群體中個(gè)體發(fā)生變異的概率:

給定均勻隨機(jī)變量 x∈［0，1］，如果 x≤pm(aj)，則對(duì)個(gè)體進(jìn)行變異;否則不發(fā)生變異。

(2)計(jì)算發(fā)生變異的個(gè)體上基因變異的概率

由于發(fā)生變異的操作方式發(fā)生了改變，被選擇變異的個(gè)體上的基因發(fā)生變異的概率也應(yīng)該相應(yīng)的進(jìn)行改變，以保證整個(gè)群體上基因發(fā)生變異的期望次數(shù)相同。傳統(tǒng)變異方式下整個(gè)群體基因變異的期望次數(shù)為n×k×pm。設(shè)基因變異的概率為下整個(gè)種群發(fā)生變異的期望次數(shù)為(n×pm(aj))×(k×)，且要求兩者相等，于是滿足:n×k×pm=(n×pm(aj))×(k×)，經(jīng)過(guò)變換可得出的計(jì)算公式為:

由于編碼方式采取實(shí)數(shù)編碼，染色體中的每一位基因代表的是一個(gè)聚類(lèi)中心點(diǎn)，因此當(dāng)某一位變異時(shí)，其實(shí)際操作是在整個(gè)樣本對(duì)象集合里面，通過(guò)隨機(jī)得到一個(gè)對(duì)象，替代原來(lái)聚類(lèi)中心點(diǎn)，從而形成新的變異后的染色體。例如，若染色體［1 12 23 34］的第2個(gè)基因位發(fā)生變異，而在規(guī)模為100的樣本集里面隨機(jī)獲得的數(shù)據(jù)對(duì)象是60，則變異后得到的新染色體為［1 60 23 34］。

5．1．4 終止循環(huán)條件

終止循環(huán)的方法一般有如下3種:

(1)設(shè)置最大的遺傳代數(shù)，該方法簡(jiǎn)單易行，但不準(zhǔn)確;

(2)通過(guò)群體的收斂程度來(lái)判斷，通過(guò)計(jì)算種群中基因的多樣性測(cè)度來(lái)進(jìn)行控制;

(3)根據(jù)每代的最佳個(gè)體的適應(yīng)值變化情況來(lái)進(jìn)行判定。

本文采取的方法是設(shè)置最大遺傳代數(shù)的同時(shí)，也觀察每一代中最佳個(gè)體的適應(yīng)值情況，如果經(jīng)過(guò)多次迭代后最佳個(gè)體的適應(yīng)值基本不發(fā)生變化，則認(rèn)為遺傳算法已經(jīng)收斂。

5．1．5 參數(shù)控制

在遺傳算法的運(yùn)行過(guò)程中存在著對(duì)其性能產(chǎn)生很大影響的一組參數(shù)，這組參數(shù)在算法的初始階段就應(yīng)該被合理地設(shè)定和選擇，使得遺傳算法的搜索軌跡能達(dá)到最優(yōu)解。針對(duì)XML文檔聚類(lèi)問(wèn)題，主要影響參數(shù)包括:群體規(guī)模n，交叉概率pc，變異概率pm。對(duì)這幾個(gè)參數(shù)的具體選擇將在實(shí)驗(yàn)部分展開(kāi)討論。

6 基于GA與k-medoids的XML文檔聚類(lèi)

經(jīng)過(guò)上文討論與分析，整個(gè)XML文檔聚類(lèi)的處理過(guò)程如下:

(1)輸入XML文檔樣本數(shù)據(jù)集，計(jì)算得到相似度矩陣。

(2)通過(guò)基于模糊等價(jià)關(guān)系的聚類(lèi)方法對(duì)相似度矩陣進(jìn)行操作，得到最佳聚類(lèi)個(gè)數(shù)。

(3)根據(jù)得到的聚類(lèi)個(gè)數(shù)對(duì)個(gè)體進(jìn)行編碼，并初始化種群，每個(gè)個(gè)體編碼對(duì)應(yīng)一組隨機(jī)選擇的初始聚類(lèi)中心點(diǎn)。

(4)對(duì)種群進(jìn)行選擇、交叉、變異操作，直到滿足終止條件。

(5)在每次的遺傳操作中，通過(guò)對(duì)個(gè)體的染色體基因進(jìn)行處理，形成一組聚類(lèi)中心點(diǎn)作為 kmedoids算法的初始中心點(diǎn)，并執(zhí)行k-medoids算法進(jìn)行迭代，直到算法結(jié)束，輸出聚類(lèi)結(jié)果。以聚類(lèi)有效性指標(biāo)作為適應(yīng)度函數(shù)對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)，其評(píng)價(jià)值就是該個(gè)體的適應(yīng)度值。

(6)遺傳迭代結(jié)束后，輸出最優(yōu)的個(gè)體，即最佳的聚類(lèi)結(jié)果。

7 實(shí)驗(yàn)與結(jié)果分析

本文的XML文檔實(shí)驗(yàn)數(shù)據(jù)來(lái)自于Niagara(http://www．cs．wisc．edu/niagara/data)和 sigmod(http://www．sigmod．org/record)中的任意抽取的10 個(gè)類(lèi)別，包括了 bin，CUSTERM，actor，bib，movies，NATION，PART，personal，sigrecord 和SigmodRecord共計(jì)500個(gè)XML文檔。為了測(cè)試本文算法的有效性，從這些數(shù)據(jù)集中隨意抽取不同個(gè)數(shù)和類(lèi)別的XML文檔組成多個(gè)實(shí)驗(yàn)數(shù)據(jù)集合，進(jìn)行相應(yīng)的實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)使用DOM(Document Object Model)解析 XML文件，編程語(yǔ)言選用Java，并在Eclipse上實(shí)現(xiàn)。實(shí)驗(yàn)的平臺(tái)是2．30 GHz i5-4200U處理器Windows 7操作系統(tǒng)。實(shí)驗(yàn)具體數(shù)據(jù)集如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

7．1 聚類(lèi)個(gè)數(shù)的確定

本文對(duì)XML文檔聚類(lèi)過(guò)程中的聚類(lèi)個(gè)數(shù)的確定，采取了基于模糊等價(jià)矩陣的模糊聚類(lèi)方法。為了測(cè)試算法的有效性，從整個(gè)數(shù)據(jù)集合中抽取多個(gè)類(lèi)別的不同數(shù)量的XML文檔進(jìn)行多次實(shí)驗(yàn)，并同時(shí)記錄了其時(shí)間效率，結(jié)果如表2所示。從表中可以看出，運(yùn)用基于模糊等價(jià)矩陣的聚類(lèi)方法所得出的聚類(lèi)個(gè)數(shù)都與實(shí)際的聚類(lèi)個(gè)數(shù)相同，證明此方法在確定XML聚類(lèi)個(gè)數(shù)方面有效準(zhǔn)確。此外，本文在D4和D5中還特別加入了孤立點(diǎn)數(shù)據(jù)，以驗(yàn)證孤立點(diǎn)對(duì)本算法在最后聚類(lèi)個(gè)數(shù)的影響，結(jié)果表明此方法對(duì)孤立點(diǎn)不敏感。

關(guān)于算法的時(shí)間性能，分別選取了30個(gè)數(shù)據(jù)、80個(gè)數(shù)據(jù)、120個(gè)數(shù)據(jù)、200個(gè)數(shù)據(jù)和300個(gè)數(shù)據(jù)規(guī)模的樣本進(jìn)行實(shí)驗(yàn)，從表2中可以看出，算法的執(zhí)行時(shí)間是線性增長(zhǎng)的。最后，利用當(dāng)前得到的數(shù)據(jù)，進(jìn)行簡(jiǎn)單的線性回歸，得到當(dāng)數(shù)據(jù)量是3 000規(guī)模時(shí)，所需要的時(shí)間是3 422 ms，即3．4 s。綜上可以得到，本文所提出的利用基于模糊等價(jià)矩陣的方法進(jìn)行聚類(lèi)個(gè)數(shù)的確定，不僅能得到與實(shí)際情況相符的聚類(lèi)數(shù)目，而且在大規(guī)模數(shù)據(jù)集的應(yīng)用上，算法的執(zhí)行效率也是可接受的。

表2 聚類(lèi)個(gè)數(shù)實(shí)驗(yàn)結(jié)果

7．2 遺傳算法的參數(shù)控制

為了驗(yàn)證遺傳算法與k-medoids結(jié)合的新算法對(duì)聚類(lèi)的有效性，本文用準(zhǔn)確率(precision)、召回率(recall)和F度量(F-measure)進(jìn)行評(píng)估，另外，還加入有效性指標(biāo)Q作為評(píng)判標(biāo)準(zhǔn)。通過(guò)上述4個(gè)指標(biāo)可以綜合評(píng)估聚類(lèi)結(jié)果的好壞。

在遺傳算法的運(yùn)行過(guò)程中，存在著對(duì)算法性能產(chǎn)生影響的一組重要參數(shù)，包括:染色體位串長(zhǎng)度L，群體規(guī)模N，交叉概率pc，變異概率對(duì)于本文，位串長(zhǎng)度L已經(jīng)由聚類(lèi)個(gè)數(shù)決定，所以，只討論群體規(guī)模N、交叉概率pc和變異概率pm。本文使用控制變量法分別對(duì)這3個(gè)參數(shù)進(jìn)行實(shí)驗(yàn)。

(1)群體規(guī)模N

假設(shè)樣本集合的個(gè)數(shù)為m，分別設(shè)置群體規(guī)模N為m，2m，3m對(duì)算法聚類(lèi)結(jié)果和收斂性進(jìn)行評(píng)估和分析。本次實(shí)驗(yàn)選擇的測(cè)試數(shù)據(jù)集為D3。實(shí)驗(yàn)結(jié)果如表3所示，表中數(shù)據(jù)皆為多次運(yùn)行結(jié)果的平均值。

表3 群體規(guī)模實(shí)驗(yàn)結(jié)果

對(duì)每一代種群中的個(gè)體的均值方差定義為:

其中，xi表示每個(gè)個(gè)體的聚類(lèi)評(píng)價(jià)值;ˉx為每一代種群中所有個(gè)體聚類(lèi)評(píng)價(jià)值的平均值;n表示種群數(shù)量。

由實(shí)驗(yàn)結(jié)果可以得到3次實(shí)驗(yàn)遺傳算法的收斂性折線圖，如圖1所示。

圖1 算法收斂性折線圖

分析折線圖可以發(fā)現(xiàn)，種群數(shù)量越大，整個(gè)遺傳算法的收斂速度越慢，從而可以有效防止成熟前收斂。當(dāng)群體規(guī)模為m時(shí)，其收斂代數(shù)大致在第8代;規(guī)模為2m時(shí)，收斂在第11代;而當(dāng)規(guī)模為3m時(shí)，在第13代收斂。從遺傳算法的特性來(lái)看，越晚收斂，越能保持種群的多樣性，進(jìn)而增加了遺傳算法搜索全局最優(yōu)解的概率。同時(shí)，本文結(jié)合3次實(shí)驗(yàn)的準(zhǔn)確率、召回率、F度量以及聚類(lèi)有效性指標(biāo)進(jìn)行分析，當(dāng)群體規(guī)模為2m和3m時(shí)，不管是準(zhǔn)確率、召回率、F度量還是聚類(lèi)有效性指標(biāo)都要優(yōu)于群體規(guī)模為m時(shí)的情況。而群體規(guī)模為2m和3m則相差不大，雖然3m的群體規(guī)模的聚類(lèi)質(zhì)量稍略優(yōu)于2m，但是當(dāng)規(guī)模為3m時(shí)，它的計(jì)算量明顯要高出很多。所以綜合考慮，本文采取的選擇種群規(guī)模N=2m，是一個(gè)合理有效的選擇指標(biāo)。

(2)交叉概率pc和變異概率pm

交叉概率pc控制著遺傳算法中交叉算子的運(yùn)行頻率，而每一代的規(guī)模為n的群體中，有pc×n個(gè)染色體進(jìn)行交叉操作，交叉概率越大，種群中的不同個(gè)體的染色體基因結(jié)構(gòu)交換越頻繁，容易形成新的個(gè)體，但是已經(jīng)獲得的優(yōu)良基因丟失的概率也可能增大。變異算子對(duì)群體保持多樣性起到了很大的作用。對(duì)于長(zhǎng)度為k的染色體，每一代的種群中發(fā)生變異的次數(shù)為pm×k×n。同樣的，變異概率的選擇也很重要，如果變異概率過(guò)大，則會(huì)使得整個(gè)遺傳算法轉(zhuǎn)變?yōu)殡S機(jī)搜索;相反，變異概率太小，又無(wú)法發(fā)揮變異算子的作用，不能有效保持種群的多樣性。從一些經(jīng)驗(yàn)分析來(lái)看，交叉概率的取值一般是pc=0．6 ～1．0，變異概率的取值為 pm=0．01 ～0．10［16］。本文根據(jù)實(shí)際情況，利用實(shí)驗(yàn)數(shù)據(jù)D4，選取了一些交叉概率和變異概率的取值組合來(lái)進(jìn)行實(shí)驗(yàn)。為了讓數(shù)據(jù)更加接近實(shí)際情況，筆者進(jìn)行多次實(shí)驗(yàn)并計(jì)算所有數(shù)據(jù)的平均值，結(jié)果如表4所示。

表4 交叉概率和變異概率實(shí)驗(yàn)結(jié)果

分別對(duì)非常多組合的不同的交叉概率和變異概率的取值進(jìn)行實(shí)驗(yàn)，這里只列出了效果比較好的3個(gè)取值組合，最終取交叉概率pc=0．95以及變異概率pm=0．07。事實(shí)上，在遺傳算法中，交叉概率和變異概率針對(duì)不同的應(yīng)用和解決不同的問(wèn)題并沒(méi)有一致的取值，它們應(yīng)該根據(jù)實(shí)際問(wèn)題來(lái)進(jìn)行決定。從實(shí)驗(yàn)結(jié)果來(lái)看，這3組交叉概率和變異概率的選擇，聚類(lèi)結(jié)果基本相同，但是在聚類(lèi)質(zhì)量指標(biāo)上有一定的差異。這種聚類(lèi)質(zhì)量的差異對(duì)聚類(lèi)結(jié)果的影響將隨著數(shù)據(jù)規(guī)模的增大而增大。

7．3 與標(biāo)準(zhǔn)k-medoids算法的比較

根據(jù)以上的實(shí)驗(yàn)確定的遺傳算法的控制參數(shù)，選取數(shù)據(jù)規(guī)模2m、交叉概率pc=0．95以及變異概率pm=0．07作為本文實(shí)驗(yàn)的參數(shù)。另外，為了驗(yàn)證本文算法的有效性，把結(jié)合了遺傳算法的k-medoids和標(biāo)準(zhǔn)的k-medoids算法進(jìn)行了比較。同時(shí)，針對(duì)相同的實(shí)驗(yàn)數(shù)據(jù)，筆者把標(biāo)準(zhǔn)的 k-medoids算法運(yùn)行100次，并取其最好的結(jié)果來(lái)進(jìn)行比較分析。實(shí)驗(yàn)結(jié)果如表5所示。

表5 不同算法的實(shí)驗(yàn)結(jié)果對(duì)比

從2次實(shí)驗(yàn)數(shù)據(jù)D3和D5的驗(yàn)證中可以得出，本文的遺傳算法在與k-medoids聚類(lèi)算法的結(jié)合中，確實(shí)發(fā)揮了其優(yōu)化算法的作用，也在一定程度起到了搜索全局最優(yōu)解的能力。

如果就時(shí)間性能上來(lái)分析，標(biāo)準(zhǔn)的k-medoids算法在效率上要明顯優(yōu)于本文提出的遺傳算法。因?yàn)樵诒疚乃惴ㄖ?，每一次的個(gè)體適應(yīng)度的計(jì)算都是要運(yùn)行一次k-medoids算法。加入遺傳算法是以時(shí)間換聚類(lèi)質(zhì)量，通過(guò)底層不斷地搜索更優(yōu)的聚類(lèi)中心點(diǎn)，并用k-medoids進(jìn)行聚類(lèi)，利用遺傳算法的全局搜索能力最后得到最優(yōu)解。

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

在XML聚類(lèi)中較常用的是基于劃分的聚類(lèi)算法，但是基于劃分的聚類(lèi)算法面臨著2個(gè)問(wèn)題:(1)聚類(lèi)個(gè)數(shù)要作為輸入?yún)?shù)，算法并不能夠自動(dòng)確定;(2)初始聚類(lèi)中心點(diǎn)的選擇。針對(duì)這2個(gè)問(wèn)題，本文分別提出了解決的方案。首先，對(duì)于聚類(lèi)個(gè)數(shù)的確定問(wèn)題，利用XML文檔數(shù)據(jù)集的相似度，在不同的閾值下通過(guò)基于模糊等價(jià)關(guān)系矩陣的方法進(jìn)行聚類(lèi)，并且每次聚類(lèi)結(jié)果用預(yù)先定義的聚類(lèi)評(píng)價(jià)函數(shù)進(jìn)行評(píng)估，最后把聚類(lèi)評(píng)估值最高的聚類(lèi)結(jié)果對(duì)應(yīng)的聚類(lèi)個(gè)數(shù)作為所需確定的聚類(lèi)個(gè)數(shù)。實(shí)驗(yàn)結(jié)果證明了該方法的準(zhǔn)確性和快速性。對(duì)于初始聚類(lèi)中心點(diǎn)問(wèn)題，由于k-medoids算法的初始聚類(lèi)中心點(diǎn)是隨機(jī)選擇的，無(wú)法保證其是最佳的聚類(lèi)中心點(diǎn)，因此本文采用了遺傳算法和k-medoids相結(jié)合的算法，利用遺傳算法具有搜索全局最優(yōu)解的能力，對(duì)隨機(jī)的初始聚類(lèi)中心點(diǎn)進(jìn)行優(yōu)化，最后根據(jù)算法收斂，輸出最佳聚類(lèi)結(jié)果。針對(duì)這個(gè)過(guò)程，本文通過(guò)不同的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行多次驗(yàn)證，表明了算法的有效性。同時(shí)對(duì)影響遺傳算法性能的一些重要參數(shù)進(jìn)行了相關(guān)的實(shí)驗(yàn)，以確定合適的參數(shù)，保證聚類(lèi)結(jié)果的質(zhì)量。

雖然遺傳算法與k-medoids算法的結(jié)合在XML文檔聚類(lèi)中能取得不錯(cuò)聚類(lèi)效果，但是遺傳算法本身由于計(jì)算量大，時(shí)間花費(fèi)上較其他算法要更多。因此，下一步工作是在保證聚類(lèi)質(zhì)量的前提下，減少遺傳算法的計(jì)算量，提高XML文檔聚類(lèi)效率。

［1］ Abiteboul S，Buneman P，Suciu D．Data on the Web［M］．San Francisco，USA:Morgan Kaufmann，2000．

［2］ 孟小峰．XML數(shù)據(jù)管理:概念與技術(shù)［M］．北京:清華大學(xué)出版社，2009．

［3］ Mazuran M，Quintarelli E，Tanca L．Data Mining for XML Query-answering Support［J］．IEEE Transactions on KnowledgeandDataEngineering，2012，24(8):1393-1407．

［4］ Han Jiawei，Chang K C．Data Mining for Web Intelligence［J］．Computer，2002，35(11):64-70．

［5］ Wang Lian，Mamoulis N，Cheung D W，et al．Indexing Useful Structural Patterns for XML Query Processing［J］．IEEE Transactions on Knowledge and Data Engineering，2005，17(7):997-1009．

［6］ Lloyd S P．Least Squares Quantization in PCM［J］．IEEE Transactions on Information Theory，1982，28(2):129-137．

［7］ Kaufman L，Rousseeuw P J．Finding Groups in Data:An Introduction to Cluster Analysis［EB/OL］．(2008-05-27)．http://as． wiley． com/WileyCDA/WileyTitle/productCd-0471735787．html．

［8］ Nayak R．Investigating Semantic Measures in XML Clustering［C］//Proceedings of2006 IEEE/WIC/ACM InternationalConference on Web Intelligence．Washington D．C．，USA:IEEE Press，2006:1042-1045．

［9］ Shasha D，Wang J T L，Zhang Kaizhong，et al．Exact and Approximate Algorithms for Unordered Tree Matching［J］．IEEE Transactions on Systems，Man and Cybernetics，1994，24(4):668-678．

［10］ Zhang Kaizhong，Statman R，Shasha D．On the Editing Distance Between Unordered Labeled Trees［J］．Information Processing Letters，1992，42(3):133-139．

［11］ Choi I，Moon B，Kim H J．A Clustering Method Based on Path Similarities of XML Data［J］．Data ＆ Knowledge Engineering，2007，60(2):361-376．

［12］ Joshi S，Agrawal N，Krishnapuram R，et al．A Bag of Paths ModelforMeasuring StructuralSimilarity in Web Documents［C］//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and DataMining．NewYork，USA:ACM Press，2003:577-582．

［13］ 樸 勇，王秀坤．一種 XML文檔結(jié)構(gòu)相似度計(jì)算方法［J］．控制與決策，2010，25(4):497-501．

［14］ Sheng Weiguo，Liu Xiaohui． A Genetic k-medoids Clustering Algorithm［J］．Journal of Heuristics，2006，12(6):447-466．

［15］ Wu Jianan，Zhou Chunguang，Li Zhangxu，et al．A Novel Algorithm for Generating Simulated Genetic Data Based on k-medoids［C］//Proceedings of the 2nd International Conference on Cloud Computing and Intelligent Systems．Washington D．C．，USA:IEEE Press，2012:25-28．

［16］ 李敏強(qiáng)，寇紀(jì)淞，林 丹，等．遺傳算法的基本理論與應(yīng)用［M］．北京:科學(xué)出版社，2002．