馮少榮，潘煒煒，林子雨

(廈門大學信息科學與技術學院，福建廈門361005)

1 概述

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

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

2 XML文檔相似度計算

XML文檔的結構是一個樹狀的模型，XML中既包含結構信息，也包含語義內容信息，以往的研究主要圍繞這2個方面展開。但文獻［8］證明語義內容信息在XML文檔相似性度量中作用不大，并且由于不斷查詢WordNet詞典，導致算法計算開銷增加。因此，本文主要基于結構來度量XML文檔相似性。

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

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

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

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

定義2路徑相似度

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

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

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

輸入 2棵文檔樹Doc1，Doc2

輸出 2個文檔的相似度Sim

計算2個文檔的相似度的計算量，復雜度由以下關鍵處理過程決定:

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

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

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

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

3 XML文檔聚類的有效性指標

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

其中，Q值越小，則其聚類質量越好。

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

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

基于模糊等價關系的聚類方法，能夠簡單地通過對模糊相似矩陣的λ截運算，快速地產生一個聚類結果。本文利用XML文檔聚類必須先得出相似度矩陣的這一必要過程，通過模糊等價矩陣的方法，快速得到不同λ閾值下的聚類個數(shù)，最終用聚類有效性指標作為評估函數(shù)，確定最佳的聚類個數(shù)。

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

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

因此，可以得到基于模糊等價關系確定聚類個數(shù)的算法如下:

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

輸出 最佳聚類個數(shù)k

確定聚類個數(shù)的計算量，復雜度由以下關鍵處理過程決定:

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

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

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

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

(5)利用評價指標函數(shù)，計算每次聚類結果的評價值，并記錄評價值最高的聚類結果的聚類個數(shù)。

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

5 k-medoids最佳初始聚類中心點的確定

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

5．1 遺傳算法的操作過程

5．1．1 編碼策略

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

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

5．1．2 種群的初始化

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

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

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

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

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

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

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

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

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

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

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

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

(2)通過群體的收斂程度來判斷，通過計算種群中基因的多樣性測度來進行控制;

(3)根據(jù)每代的最佳個體的適應值變化情況來進行判定。

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

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

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

6 基于GA與k-medoids的XML文檔聚類

經過上文討論與分析，整個XML文檔聚類的處理過程如下:

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

(2)通過基于模糊等價關系的聚類方法對相似度矩陣進行操作，得到最佳聚類個數(shù)。

(3)根據(jù)得到的聚類個數(shù)對個體進行編碼，并初始化種群，每個個體編碼對應一組隨機選擇的初始聚類中心點。

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

(5)在每次的遺傳操作中，通過對個體的染色體基因進行處理，形成一組聚類中心點作為 kmedoids算法的初始中心點，并執(zhí)行k-medoids算法進行迭代，直到算法結束，輸出聚類結果。以聚類有效性指標作為適應度函數(shù)對聚類結果進行評價，其評價值就是該個體的適應度值。

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

7 實驗與結果分析

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

表1 實驗數(shù)據(jù)集

7．1 聚類個數(shù)的確定

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

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

表2 聚類個數(shù)實驗結果

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

為了驗證遺傳算法與k-medoids結合的新算法對聚類的有效性，本文用準確率(precision)、召回率(recall)和F度量(F-measure)進行評估，另外，還加入有效性指標Q作為評判標準。通過上述4個指標可以綜合評估聚類結果的好壞。

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

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

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

表3 群體規(guī)模實驗結果

對每一代種群中的個體的均值方差定義為:

其中，xi表示每個個體的聚類評價值;ˉx為每一代種群中所有個體聚類評價值的平均值;n表示種群數(shù)量。

由實驗結果可以得到3次實驗遺傳算法的收斂性折線圖，如圖1所示。

圖1 算法收斂性折線圖

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

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

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

表4 交叉概率和變異概率實驗結果

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

7．3 與標準k-medoids算法的比較

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

表5 不同算法的實驗結果對比

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

如果就時間性能上來分析，標準的k-medoids算法在效率上要明顯優(yōu)于本文提出的遺傳算法。因為在本文算法中，每一次的個體適應度的計算都是要運行一次k-medoids算法。加入遺傳算法是以時間換聚類質量，通過底層不斷地搜索更優(yōu)的聚類中心點，并用k-medoids進行聚類，利用遺傳算法的全局搜索能力最后得到最優(yōu)解。

8 結束語

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

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

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

［2］ 孟小峰．XML數(shù)據(jù)管理:概念與技術［M］．北京:清華大學出版社，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文檔結構相似度計算方法［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］ 李敏強，寇紀淞，林 丹，等．遺傳算法的基本理論與應用［M］．北京:科學出版社，2002．