基于量子遺傳譜聚算法的聚類蔣勇1，譚懷亮2(1．湖南化工職業(yè)技術(shù)學(xué)院信息系，湖南,株洲，412004；2.湖南大學(xué)計(jì)算機(jī)與通信學(xué)院,湖南,長沙，410082）(hunanlaojiang@163.com)摘要：主要核方法研究XML聚類，提出了一種改進(jìn)的XML文檔核聚類方法。該方法先對(duì)XML文檔約簡(jiǎn)，以頻繁標(biāo)簽序列建立向量空間核的核矩陣，用高斯核函數(shù)求解初始聚類和聚類中心，然后用初始聚類中心構(gòu)造量子遺傳算法的初始種群，通過量子遺傳算法與核聚算法相結(jié)合求得全局最優(yōu)解的聚類。為了驗(yàn)證本文提出的算法，實(shí)驗(yàn)結(jié)果顯示，使用該算法的聚類比改進(jìn)的核聚算法、K—means等單一方法具有良好的收斂性、穩(wěn)定性和更高的全局最優(yōu)。關(guān)鍵詞：XML文檔；高斯核函數(shù)；核聚類算法；量子遺傳算法；XML聚類中圖法分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：AClusteringBasedonQuantumGeneticSpectralClusteringAlgorithmJIANGYong1,TANHui-liang2（1.DepartmentofInformationandCollegeofHunanChemical,ZhuzhouHunan412004,C2.SchoolofComputerandCommunication,HunanUniversity,ChangshaHunan,410082,China)Abstract：ThispapermainlytargetsonXMLClusteringwithkernelmethodsforpatternanalysisandthequantumgeneticalgorithm,Anewmethodbasedonthequantumgeneticalgorithmandclusteringalgorithmwasderived.TotheXMLdocumentseliminated,thevectorspacekernel’skernelmatrixweregeneratedwithfrequent-tagsequence,firstsolvestheinitialclusteringandclusteringcenterwiththeGaussiankernelfunctions,thenthequantumgeneticalgorithm'sinitialpopulationswereconstructedbytheinitialclusteringcenterstructure,clusteringofthegloballyoptimalsolutionswereobtainedthroughitandkernelclusteringalgorithm.Inordertoconfirmthealgorithmwhichthisarticleproposed,theexperimentalresultshowedthatitismoresuperiortotheimprovementofkernelclusteringalgorithm,K-meansinthegoodastringency,thestabilityandahigheroveralloptimalsolutions.KeyWords:XMLdocument;guassiankernelfunction;kernelclusteringalgorithm;quantumgeneticalgorithm;XMLclustering1概述聚類是數(shù)據(jù)挖潛、人工智能、模式識(shí)別中重要的分析手段，迄今為止，專家們進(jìn)行了大量的研究，并提出了很多算法。其中有以CURE[1]和ChenLF[2]為代表的層次聚類，也有以BerndFischer和MartinEster[3,4]為代表的密度聚類，有基于密度敏感的半監(jiān)督譜聚類[5]和基于免疫譜聚類[6]及基于魯棒路徑的譜聚類[7,8]等聚類方法。CURE算法和ChenLF等人的算法將層次算法與劃分算法結(jié)合在一起來克服球形簇的缺陷，在計(jì)算簇間的距離時(shí)，用一組點(diǎn)代表聚類中心；BerndFischer以“核連接”的方法連接路徑距離，用來發(fā)現(xiàn)具有細(xì)長結(jié)構(gòu)的圖形的聚類；MartinEster等人提出的算法用來挖掘任意形狀聚類及處理噪聲數(shù)據(jù)具有優(yōu)勢(shì)；WANGLing等人的提出的密度敏感的半監(jiān)督譜聚類算法，挖潛無類屬數(shù)據(jù)中的空間一致性信息，利用用戶提供的成對(duì)限制先驗(yàn)信息直接修改距離測(cè)度，使用挖潛得到空間一致性信息來自動(dòng)調(diào)節(jié)數(shù)據(jù)間距離，這樣避免用戶所提供的信息含量少的限制所造成的聚類偏移，該算法在聚類性能上效果顯著；ZhangXR等人的基于免疫譜聚類的圖像分割算法是利用譜聚類的維數(shù)縮減獲得在映射空間的分布，利用免疫克隆算法在映射空間中對(duì)樣本進(jìn)行聚類，該聚類算法具有快速收斂到全局最優(yōu)的特性；BerndFischer與HongChang等人的基于魯棒路徑的聚類算法在解決具有細(xì)長結(jié)構(gòu)的圖形數(shù)據(jù)聚類的過程中，對(duì)其中的噪聲的處理很有優(yōu)勢(shì)，前者采用bagging(bootstrapaggregating)方法，對(duì)數(shù)據(jù)的進(jìn)行重新采樣，減少數(shù)據(jù)的方差，達(dá)到對(duì)噪聲不太敏感的結(jié)果，后者是通過魯棒的M-預(yù)估技術(shù)來解決該問題。此外，K-均值聚類作為一種最簡(jiǎn)單、使用最普遍的基于中心的聚類算法，在緊湊的超球形分布的數(shù)據(jù)集合上有很好的性能，但當(dāng)數(shù)據(jù)結(jié)構(gòu)是非凸時(shí)，算法因數(shù)據(jù)重疊而失效，而且對(duì)初始聚類中心的選擇也非常敏感，因此在尋找最優(yōu)解時(shí)，只能保證局部最優(yōu)，不能保證收斂到全局最優(yōu)；譜聚類算法[9,10]克服K-均值聚類算法的缺點(diǎn)，具有識(shí)別非凸分布聚類的能力，但算法的時(shí)間復(fù)雜度達(dá)到O(n3)，當(dāng)數(shù)據(jù)集的規(guī)模較大時(shí)，求解特征值因數(shù)據(jù)量太大有可能超出計(jì)算機(jī)的內(nèi)存，所以對(duì)求大規(guī)模的數(shù)據(jù)聚類也存在不足；量子遺傳算法[11,12]是量子計(jì)算和遺傳算法相結(jié)合的產(chǎn)物，它建立在量子態(tài)矢量表示的基礎(chǔ)上，用量子比特編碼來表示染色體，以量子旋轉(zhuǎn)門實(shí)現(xiàn)染色體基因的調(diào)整，實(shí)現(xiàn)染色體的多個(gè)量子態(tài)的疊加，具有對(duì)目標(biāo)問題更優(yōu)的全局求解和較快的收斂速度，所以量子遺傳聚類算法適合于大數(shù)據(jù)集的聚類分析而具有很好的前景。本文利用譜圖劃分理論，把數(shù)據(jù)集看成是一個(gè)圖的集合，其中每個(gè)數(shù)據(jù)點(diǎn)是圖的一個(gè)頂點(diǎn)，圖的邊是頂點(diǎn)之間的連線，它表示數(shù)據(jù)之間的相似程度，按照兩個(gè)頂點(diǎn)組成的邊的相似度構(gòu)造相似度矩陣和Laplacian矩陣，在求解矩陣的特征值和特征向量時(shí)，為了緩解算法的計(jì)算復(fù)雜度，將大矩陣的特征值分解問題變換成等價(jià)的奇異值分解（SVDsingularvaluedecomposition）問題，隨后計(jì)算小規(guī)模矩陣的特征值和特征向量，間接得到原始大矩陣的特征向量，然后把求得的最大特征向量歸一化并映射成矩陣Y，再通過量子遺傳聚類尋找該新樣本集的最優(yōu)聚類中心，最后將每一個(gè)樣本判別到離它最近的聚類中心所在的類別中去，從而完成整個(gè)聚類過程。在實(shí)際中，通過實(shí)驗(yàn)驗(yàn)證：選用UCI和人工合成數(shù)據(jù)并與Fowlkes等人提出的Nystr?m逼近方法[13]來求解進(jìn)行比較，該方法取得滿意的結(jié)果。2相關(guān)工作2.1譜聚類算法 譜聚類算法是基于譜圖劃分理論的一種高性能計(jì)算方法，它將聚類問題看成是一個(gè)無向圖的多路劃分問題。設(shè)有n個(gè)樣本點(diǎn),其中，樣本點(diǎn)看成是一個(gè)無向圖G（V，E）的頂點(diǎn)V，邊的集合E={Wij}表示基于某一相似度計(jì)算的兩點(diǎn)間的相似度，用W表示待聚類樣本點(diǎn)間相似度矩陣，將其看作是該無向圖的鄰接矩陣，它包含了聚類所需的所有信息，然后定義同一類的點(diǎn)具有較高的相似性，而不同類之間的點(diǎn)具有較低的相似性的原則劃分聚類。由于求解圖的最優(yōu)劃分是一個(gè)NP難問題，一個(gè)有效地求解該問題的方法是將原問題轉(zhuǎn)換成求解矩陣的特征值和特征向量的問題，因而將這類算法統(tǒng)稱為譜聚類算法。 譜聚類算法可以遞歸地使用2-way劃分方法來實(shí)現(xiàn)聚類，其算法的一般框架如下：Step1:基于數(shù)據(jù)點(diǎn)間的相似性度量，構(gòu)造數(shù)據(jù)點(diǎn)集的相似性矩陣W；Step2：使用非正則化（unnormalized）拉普拉斯矩陣L、正則化（unnormalized）拉普拉斯矩陣Lsym、圖上的隨機(jī)游動(dòng)所對(duì)應(yīng)的轉(zhuǎn)移概率矩陣（transitionmatrix）P等矩陣中一種計(jì)算W的前k個(gè)最大特征值和特征向量； =1\*GB3①2-way:將原始樣本數(shù)據(jù)映射到一維空間（k=1）； =2\*GB3②k-way：將原始樣本數(shù)據(jù)映射到有k個(gè)正交向量的K維空間X；Step3:將K維子空間X的行作為樣本的新的數(shù)據(jù)表示，劃分?jǐn)?shù)據(jù)點(diǎn)到兩類或多類中； =1\*GB3①2-way:在一維空間上根據(jù)目標(biāo)函數(shù)的最優(yōu)劃分，在劃分好的兩個(gè)子圖上進(jìn)行迭代劃分； =2\*GB3②k-way：利用K-mean算法或其它算法在K維空間上進(jìn)行聚類。 在實(shí)際應(yīng)用中，參數(shù)K也很難預(yù)先確定，根據(jù)Tian等人[14]使用矩陣擾動(dòng)理論對(duì)權(quán)矩陣進(jìn)行了分析，得出權(quán)矩陣的特征向量和簇之間的關(guān)系，在理想情況下，存在K個(gè)理想的彼此分離的聚類的有限數(shù)據(jù)集，其矩陣的前K個(gè)最大特征值為1，而第K+1個(gè)特征值則嚴(yán)格小于1，二者之間的差距取決于這K個(gè)聚類的分布情況。K個(gè)理想的彼此分離簇的數(shù)據(jù)樣本體現(xiàn)在相似性矩陣上，就是該矩陣對(duì)角線上分布K個(gè)全1分塊矩陣，其余位置都為0。但在實(shí)際情況中，相似性矩陣對(duì)角線上的分塊元素不全為1，準(zhǔn)確的是全1加上一個(gè)負(fù)的擾動(dòng)量，對(duì)角線上分塊矩陣外的元素也不全為0，而是一個(gè)正的擾動(dòng)量。也即可以而且隨著數(shù)據(jù)規(guī)模的增大，求解矩陣的特征值分解其計(jì)算量也及其高昂，于是將大矩陣的特征值分解問題變換成等價(jià)的奇異值分解問題，隨后計(jì)算小規(guī)模矩陣的特征值和特征向量，間接得到原始大矩陣的特征向量，然后把求得的最大特征向量歸一化并映射成矩陣Y，2.2轉(zhuǎn)移概率矩陣的2.2量子遺傳聚類算法 設(shè)由n個(gè)XML文檔看成數(shù)據(jù)點(diǎn)組成的無向圖G=(V,E，W)，選用高斯徑向基核作為兩文檔的相似度的連接權(quán)重，即Wi,j=exp(-d(di,dj)2/2≡(i,j)，是連接核，它的值越小，說明兩文檔的相似度越大。并假設(shè)p是圖中所有路徑P中長度為|p|的一條路徑，路徑上各邊表示為（di,dj），1k<|l|，則路徑p是連接點(diǎn)i、j所有路徑的基于路徑的相似度的最大值：（1） 按據(jù)（1）式的定義，若頂點(diǎn)i、j屬于同一聚類，則它們的相似度大；若屬于不同的聚類，則它們的相似度??；若在兩類之間的存在孤立點(diǎn)，因孤立點(diǎn)敏感而造成錯(cuò)誤的聚類，所以采用文獻(xiàn)[11]的“魯棒的基于路徑的相似性度量”和“魯棒M-預(yù)估技術(shù)”的方法解決此問題，即將（1）式轉(zhuǎn)化為（2）其中，，基于條件路徑的點(diǎn)就是一個(gè)聚類。一個(gè)有n個(gè)節(jié)點(diǎn)無向連通圖，最多可以劃分成k條不同的路徑（k<n），則所有k條路徑表示為（p1,p2,…,pk），這些路徑的點(diǎn)聚集就組成K個(gè)聚類。若采用圖的劃分求解路徑是NP問題，需要計(jì)算的數(shù)據(jù)量非常大。為了減少計(jì)算代價(jià)，本文采用基于路徑最優(yōu)的聚類算法求解每個(gè)聚類、結(jié)合量子遺傳算法求解全局K個(gè)聚類，從而達(dá)到XML文檔聚類的目的。2.3基于路徑的聚類算法 基于路徑的聚類算法，主要用于量子遺傳算法每次獲得二進(jìn)制解后的調(diào)用，實(shí)現(xiàn)每條路徑聚類最優(yōu)。其目標(biāo)函數(shù)表示如下：=（2）其算法的主要思想是：首先求任意聚類中心的數(shù)據(jù)對(duì)象之間的交集，若它們屬于兩個(gè)或多個(gè)分類的元素，則取出公共的數(shù)據(jù)對(duì)象，根據(jù)計(jì)算其到公共聚類中心的內(nèi)積和目標(biāo)函數(shù)值，選取值最大的兩類合并成一類；其次對(duì)任意聚類中心的數(shù)據(jù)對(duì)象之間不存在交集的分類，采用的方法是：計(jì)算(x)到聚類中心、的目標(biāo)函數(shù)的值F(x,vi)、F（x,vj），如果F(x,vi)>dij，則該分類的數(shù)據(jù)對(duì)象就是單獨(dú)的一個(gè)聚類；如果F(x,vi)<dij且F(x,vj)<dij，則分類和分類合并成一類；如果F(x,vi)<dij且F(x,vj)>dij，則以vj為聚類中心的一類、或單獨(dú)是一類、低或與其它分類合并成一個(gè)新類；最后孤立點(diǎn)的分類，計(jì)算它與新的聚類中心的內(nèi)積，若內(nèi)積大于聚類中任意一個(gè)數(shù)據(jù)對(duì)象到中心的距離，則孤立點(diǎn)仍然是孤立點(diǎn)，否則，把它加入新的聚類中。2.3量子遺傳算法與基于路徑的聚類算法的混合聚類量子遺傳算法是量子計(jì)算與遺傳算法結(jié)合的產(chǎn)物。它建立在量子態(tài)矢量表示的基礎(chǔ)上，用量子比特編碼來表示染色體，以量子旋轉(zhuǎn)門實(shí)現(xiàn)染色體基因的調(diào)整。量子遺傳算法中一個(gè)染色體可以表達(dá)多個(gè)態(tài)的疊加，而傳統(tǒng)的編碼方式只能表示一個(gè)具體的狀態(tài)，所以QGA算法比傳統(tǒng)的遺傳算法更容易保持種群的多樣性，具有對(duì)目標(biāo)問題更優(yōu)化的求解[10-11]。2.3.1傳統(tǒng)QGA與基于路徑的聚類算法的量子染色體編碼的異同 傳統(tǒng)量子遺傳算法中染色體編碼是：一個(gè)量子比特可以為一個(gè)“0”態(tài)或“1”態(tài)，或它們的任意疊加態(tài)。即一個(gè)量子比特可能處于|0>、|1>，或兩者之間的中間態(tài)。因此可表示為：，其中是2個(gè)復(fù)數(shù)，滿足，和分別是|0>和|1>狀態(tài)的概率，其量子比特用概率幅表示為。在QGA中，若第t代的量子種群表示為，其中，n為種群規(guī)模，為第t代種群中第j個(gè)量子染色體。而在QGA與基于路徑的聚類算法的量子染色體的編碼中，對(duì)有m個(gè)體的種群p={}，其中為種群中的第i個(gè)個(gè)體第j個(gè)量子比特，則每個(gè)量子染色體用一個(gè)聚類中心表示，所有的聚類中心集合組成一個(gè)初始種群，其中為一個(gè)聚類中心，k為聚類數(shù)。2.3.2適應(yīng)度函數(shù) 適應(yīng)度函數(shù)是判斷個(gè)體好壞的尺度。定義如下：f(v)=1/(F(x,v)+1)，其中是核聚函數(shù)，它的值越小，表明其適應(yīng)度就越高，聚類效果越好。2.4量子旋轉(zhuǎn)門 量子旋轉(zhuǎn)門是實(shí)現(xiàn)演化操作的執(zhí)行機(jī)構(gòu)，其操作如下：（8）其中為更新前染色體中的第i（）個(gè)量子比特，為更新后染色體的第i個(gè)量子比特，為旋轉(zhuǎn)角，其大小和方向根據(jù)一定的調(diào)整策略確定。在QGA與基于路徑的聚類算法相結(jié)合的算法中采用量子旋轉(zhuǎn)門更新策略，即使用進(jìn)化方程自動(dòng)進(jìn)行調(diào)整，其進(jìn)化方程用數(shù)學(xué)表達(dá)式來表示，其中是當(dāng)前染色體測(cè)量值的第i位，是個(gè)體歷史最佳狀態(tài)量子位的值，p為種群全局歷史最佳狀態(tài)量子位的值，它指明搜索方向，是某區(qū)域內(nèi)個(gè)體最佳狀態(tài)量子位的值，它實(shí)現(xiàn)局部精化，為影響因子。因此與傳統(tǒng)的量子遺傳算法查表帶來的繁瑣相比，使用此表達(dá)式作為量子旋轉(zhuǎn)門的調(diào)整角度，算法的結(jié)構(gòu)簡(jiǎn)單，收斂速度快，既能避免局部局限出現(xiàn)又能快速達(dá)到全局最優(yōu)。2.5QGA和基于路徑的聚類算法的混合聚類 采用量子遺傳算法與基于路徑的聚類算法相結(jié)合求解XML聚類，在求得初始聚類中心和K個(gè)類別后，采用QGA算法進(jìn)行全局搜索求得近似解，采用基于路徑的聚類算法在局部求得每條路徑的聚類最優(yōu)解，這樣將兩者結(jié)合，進(jìn)一步在全局范圍內(nèi)求得全局最優(yōu)解。算法具體步驟描述輸入：已初始的XML文檔聚類結(jié)果，初始聚類中心和聚類個(gè)數(shù)K輸出：處理后的最終XML聚類結(jié)果和聚類中心1）初始化種群，t=0，每個(gè)聚類中心表示成一個(gè)量子染色體，所有的聚類中心組成一個(gè)初始種群，即種群個(gè)體為m，量子比特位數(shù)為k的種群表示為p(t)={}。初始化時(shí)全部染色體的基因的概率幅均為。2）對(duì)種群中個(gè)體實(shí)施初次觀察，得到一個(gè)二進(jìn)制解q(t)，并對(duì)得到的二進(jìn)制解解碼，得到聚類中心；3）調(diào)用核聚類算法進(jìn)行聚類，同時(shí)根據(jù)核聚函數(shù)，計(jì)算每個(gè)量子染色體的適應(yīng)度值，每個(gè)量子染色體的適應(yīng)度值按計(jì)算。4）對(duì)每個(gè)量子染色體進(jìn)行適應(yīng)度評(píng)價(jià)，保存最佳個(gè)體的適應(yīng)度值及其量子位狀態(tài)值，把個(gè)體的最佳適應(yīng)度值及其量子位狀態(tài)值作為初始個(gè)體歷史最佳狀態(tài)適應(yīng)度的值和初始的最佳量子位狀態(tài)值；把全局最佳個(gè)體的適應(yīng)度值及其量子位狀態(tài)值作為全局歷史最佳狀態(tài)適應(yīng)度的值和全局歷史最佳狀態(tài)值；把某區(qū)域內(nèi)個(gè)體最佳適應(yīng)度值及其量子位狀態(tài)值作為區(qū)域內(nèi)個(gè)體最佳適應(yīng)度值和其量子位最佳狀態(tài)值，這些值作為下一步演化的目標(biāo)值；5）while(不滿足終止條件)=1\*GB3①t=t+1； =2\*GB3②對(duì)種群p(t)中所有個(gè)體實(shí)施一次觀察，得到一個(gè)二進(jìn)制解q(t)，對(duì)其二進(jìn)制解解碼，調(diào)用核聚算法進(jìn)行聚類，并利用核聚函數(shù)求得每個(gè)個(gè)體的適應(yīng)度的值，對(duì)每個(gè)量子染色體選擇最大的適應(yīng)度值；=3\*GB3③以量子旋轉(zhuǎn)門更新種群得到下一代p(t+1)；=4\*GB3④對(duì)更新狀態(tài)后的種群個(gè)體進(jìn)行解碼并求得每個(gè)個(gè)體的適應(yīng)度的值，判斷聚類中心的變化，調(diào)用聚類算法調(diào)整聚類；=5\*GB3⑤對(duì)更新狀態(tài)后的種群個(gè)體與當(dāng)前目標(biāo)值的適應(yīng)度進(jìn)行比較，如果個(gè)體適應(yīng)度優(yōu)于個(gè)體歷史最佳狀態(tài)適應(yīng)度，則用此個(gè)體適應(yīng)度作為個(gè)體歷史最佳適應(yīng)度，用此個(gè)體量子位狀態(tài)作為個(gè)體歷史最佳狀態(tài)；如果某區(qū)域內(nèi)個(gè)體適應(yīng)度優(yōu)于區(qū)域內(nèi)個(gè)體最佳適應(yīng)度，則用此個(gè)體適應(yīng)度作為個(gè)體區(qū)域內(nèi)最佳適應(yīng)度，用此個(gè)體量子位狀態(tài)作為個(gè)體區(qū)域內(nèi)最佳狀態(tài)；如果全局最佳適應(yīng)度優(yōu)于全局歷史最佳適應(yīng)度，則用此全局最佳適應(yīng)度作為全局歷史最佳適應(yīng)度，用此全局最佳量子位狀態(tài)作為全局歷史最佳狀態(tài)；如果不滿足，則保持當(dāng)前目標(biāo)值不變；=6\*GB3⑥根據(jù)聚類中心的變化，調(diào)用聚類算法調(diào)整聚類；=7\*GB3⑦量子變異及災(zāi)變：根據(jù)變異概率，對(duì)染色體的量子比特的概率幅取反，當(dāng)全局最佳適應(yīng)度值在一定代數(shù)內(nèi)沒有變化時(shí)，說明變異后的新的染色體適應(yīng)度值優(yōu)于原來的，則用其取代原個(gè)體最佳適應(yīng)度，并更新染色體的狀態(tài)，根據(jù)聚類中心的變化，調(diào)用聚類算法調(diào)整聚類。End6) 輸出文檔的聚類及聚類中心。3實(shí)驗(yàn)結(jié)果與分析3.1實(shí)驗(yàn)設(shè)計(jì)實(shí)驗(yàn)使用intelp42.4GBHzCPU、2G主存的個(gè)人計(jì)算機(jī)，在windows2003Server操作系統(tǒng)上，以Visual.NET作為開發(fā)環(huán)境。選用/record的sigmod中1999、2007、2008、2009四個(gè)年度XML數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析，每個(gè)數(shù)據(jù)集由數(shù)千篇不同XML格式的ACMSIGMOD論文組成。共選用1181個(gè)XML文檔由表1所示。這四個(gè)數(shù)據(jù)集都有分類信息，在ACMSIGMOD文檔中，每個(gè)文檔通常屬于多個(gè)分類，而屬于同一個(gè)分類的XML文檔具有較強(qiáng)的相似性，所以把它劃分成一類。在實(shí)驗(yàn)中，首先約簡(jiǎn)XML文檔，建立頻繁標(biāo)簽序列，再依次計(jì)算XML文檔的向量矩陣及向量空間核的核矩陣。表1實(shí)驗(yàn)中使用的數(shù)據(jù)子集1999200720082009volume28363738number2444IndexTermsPage920000OrdinaryIssuePage51454545ProceedingPage17161616SigmodRecord1333表2XML文檔集聚類實(shí)驗(yàn)結(jié)果算法檢測(cè)數(shù)據(jù)時(shí)間（秒）聚類分組及每組數(shù)準(zhǔn)確率（%）k-means1759107.4297910，178，63，997.182%改進(jìn)的核聚算法173295.7739915，180，64，897.437%量子遺傳算法與核聚算法167995.2853920，182，65，1098.634%為了評(píng)價(jià)本文提出的方法，通過隨機(jī)選擇樣本進(jìn)行測(cè)試，通過觀察它們的變化來評(píng)估其性能，設(shè)準(zhǔn)確率=實(shí)際聚類的文檔數(shù)/聚類的文檔的劃分?jǐn)?shù)。3.2實(shí)驗(yàn)結(jié)果分析從表2中聚類實(shí)驗(yàn)結(jié)果可以看出，三種聚類法在大多數(shù)XML文檔類別中，其聚類準(zhǔn)確率都很高，而且聚類的波動(dòng)性較小，后兩種方法的準(zhǔn)確性比前者提高1%左右。同時(shí)，測(cè)試樣本的多少，對(duì)它的性能影響也較小。從表2看出，三種聚類方法，其聚類時(shí)間只有本文提出的優(yōu)于其它兩種，并且隨著抽樣數(shù)據(jù)的增多，本文提出的要比其它兩種的時(shí)間要少，而且收斂程度也較好。4結(jié)語本文提出的量子遺傳算法與核聚算法相結(jié)合的XML聚類思想，是在進(jìn)行量子遺傳算法過程中進(jìn)行XML文檔聚類，在獲得全局最優(yōu)解的同時(shí)又保證了較高的穩(wěn)定性和快速的收斂性，而且時(shí)間效率也比k-means和改進(jìn)的核聚算法要高。特別是對(duì)復(fù)雜的XML文檔，通過對(duì)XML文檔進(jìn)行約簡(jiǎn)，消除了XML文檔中的重復(fù)、嵌套出現(xiàn)的標(biāo)簽，降低計(jì)算XML樹相似度的時(shí)間開銷和保證聚類結(jié)果的質(zhì)量，所以該算法行之有效。參考文獻(xiàn)：[1]GUHAS,RASTOGIR,SHIMK.CRUE:anefficientclusteringalgorithmforlargedatabases[C]//procofACMSIGMODInternationalConferenceonManagementofData.NewYorkACMPress1998:73-84.[2]CHENLF,JIANGQS，WANGSR.AHierarchicalMethodforDeterminingtheNumberofClusters[J].JournalofSoftware,Vol.19,No.1,January2008,pp:62-72.[3]BerndFischer,VolkerRoth,JoachimM.Buhmann.ClusteringwiththeConnectivityKernel[C].ProceedingsoftheNIPS.Cambridge,MA,USA:MITPress,2004.[4]MartinEster,Hans-PeterKriegel,JorgSander,XiaoweiXU.ADensity-BasedAlgorithmforDiscoveringClustersinLargeSpatialDatabaseswithNoise.Proceedingsof2ndInternationalConferenceonKnowledgeDiscoveryandDataMining,1996.[5]WANGLing,BOLie-Feng,JIAOLi-Cheng.Density-SensitiveSemi-SupervisedSpectralClustering[J].ChineseJournalofComputers,Vol.32No.10,Oct.2009.[6]ZhangXR,QianXX,JiaoLC.Immunespectralclusteringalgorithmforimagesegmentation[J].JournalofSoftware,Vol.21,No.9,September2010,pp:2196-2205.[7]B.Fisher,J.Buhmann.Baggin