基于矩陣加權(quán)關(guān)聯(lián)規(guī)則的空間粒度聚類算法

摘要:提出了一種基于矩陣加權(quán)關(guān)聯(lián)規(guī)則的空間粒度聚類算法。該算法核心思想是根據(jù)文檔特征向量矩陣提取文檔的相似度，再在該關(guān)聯(lián)規(guī)則算法上進(jìn)行聚類來尋找相似關(guān)系的頻繁項(xiàng)集。在粒度空間中采用相似度閥值進(jìn)行調(diào)整粒度的粗細(xì)問題。通過矩陣加權(quán)關(guān)聯(lián)規(guī)則算法進(jìn)行聚類。通過實(shí)驗(yàn)表明，在處理中小型文檔時(shí)，該算法的精確度優(yōu)于傳統(tǒng)Apriori算法和K-mean算法;在處理大型文檔時(shí)，該算法的時(shí)間復(fù)雜度小于傳統(tǒng)的K-mean算法。

關(guān)鍵詞:關(guān)聯(lián)規(guī)則;粒度;聚類算法;頻繁項(xiàng)集

中圖分類號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)02-259-03

The Cluster Algorithm of Spatial Grain Based on Matrix Weighting Association Rules

LI Ze-jun

(hunan Institute of Technology， Hengyang 421002， China)

Abstract: A cluster algorithm of spatial grain based on association rules of Matrix weighting is proposed.This algorithm utilizes eigenvector matrices of the document to extract its similarity degree，and then clusters to search for the frequent items of similar relation on the basis of above-mentioned association rules.Thereafter threshold value of similarity degree will be employed to adjust the area of granularity in spatial grain.Subsequently the results of the Matrix Weighting algorithm will be clustered.Experiments suggest that the precision of this algorithm excels the Apriori and the K-mean while processing documents of middle and small size. As for large-scale documents，the Time Complexity of this algorithm is lower than that of K-mean.

Key words: association rules; granularity; cluster algorithm; frequent items

目前大多數(shù)網(wǎng)絡(luò)信息是以文檔或文本的形式存儲(chǔ)，人們都期待從這些信息中提取自己感興趣的知識(shí)。傳統(tǒng)的信息檢索技術(shù)已不適應(yīng)日益增加的大量文本數(shù)據(jù)處理的需要，典型的是，大量文檔中只有很少一部分與用戶有關(guān)，而不清楚文檔的內(nèi)容，就很難形成有效的查詢和從信息數(shù)據(jù)中分析和提取有用的信息。這樣我們就需要有關(guān)的工具來完成不同文檔的比較，對(duì)文檔信息進(jìn)行聚類分析等[1]。數(shù)據(jù)挖掘研究主要是針對(duì)結(jié)構(gòu)數(shù)據(jù)的，如關(guān)系的，事務(wù)的和數(shù)據(jù)庫的數(shù)據(jù)。而文檔數(shù)據(jù)庫中存儲(chǔ)最多的是半結(jié)構(gòu)甚至是無結(jié)構(gòu)信息數(shù)據(jù)，因此，對(duì)半結(jié)構(gòu)或無結(jié)構(gòu)數(shù)據(jù)的建模和實(shí)現(xiàn)就成為了文檔數(shù)據(jù)挖掘的一個(gè)重要組成部分。目前的文檔聚類主要有基于概率的方法和基于距離兩種方法。基于概率的方法是以貝葉斯概率為理論基礎(chǔ)，用概率的分布方式描述聚類結(jié)果，可處理類間相互重疊的情況，缺點(diǎn)是當(dāng)特征空間的維數(shù)較高或特征值之間出現(xiàn)較強(qiáng)的相關(guān)性時(shí)，聚類的精度和效率均不能令人滿意。基于距離的方法，典型的有k-模糊均值算法等，它們都以特征向量表示文檔，再將文檔看成向量空間中的一個(gè)點(diǎn)，通過計(jì)算點(diǎn)之間的距離來進(jìn)行聚類，比較形象直觀，缺點(diǎn)是當(dāng)文檔維數(shù)較高時(shí)聚類的質(zhì)量和算法的效率都明顯地下降。

在本文的研究中，我們用主題表示文檔，將文檔和主題間的關(guān)系描述成事務(wù)的形式，根據(jù)臻于成熟的關(guān)聯(lián)規(guī)則挖掘算法初步劃分文檔類。然后依照類間耦合度和類的內(nèi)聚性進(jìn)行聚類確認(rèn)。算法的基本思想是:首先利用向量空間模型對(duì)文檔進(jìn)行結(jié)構(gòu)化處理，用文檔主題特征向量形成文檔主題事務(wù)矩陣。然后運(yùn)用空間粒度分析的方法對(duì)樣本事務(wù)矩陣實(shí)現(xiàn)最優(yōu)聚類即關(guān)聯(lián)規(guī)則的空間粒度聚類算法，并與經(jīng)典的k-均值模糊算法進(jìn)行比較，關(guān)聯(lián)規(guī)則的空間粒度聚類算法的精度比k-均值模糊算法提高了很多，并用實(shí)驗(yàn)證明了其有效性和可行性。

1 文檔結(jié)構(gòu)矩陣加權(quán)關(guān)聯(lián)規(guī)則

在向量空間模型中我們?cè)O(shè)T=(t1，t2，…，tn)是一個(gè)文檔數(shù)據(jù)庫，tj表示文檔數(shù)據(jù)庫中的第j個(gè)記錄 I={i1，i2， …，in}表示文檔數(shù)據(jù)庫的特征詞項(xiàng)集，Wp=[W[tj][ip]]j×p用于表示特征詞項(xiàng)ip在文檔數(shù)據(jù)庫中的矩陣權(quán)值[2-3]。其中(1≤j≤n，1≤p≤m)，若ip不在tj中，則W[tj][ip]=0。我們令X?奐I，Y?奐I，且X∩Y=?覫，則有特征詞項(xiàng)集(X，Y)的矩陣加權(quán)關(guān)聯(lián)規(guī)則可以表示為X→Y[4]。設(shè)某數(shù)據(jù)庫中有2個(gè)文檔，第一個(gè)文檔表示為Wij，第二個(gè)文檔表示為Wij'，用UIJ表示文檔Wij詞語對(duì)文檔Wij'的關(guān)聯(lián)度，則Uij可以用矩陣表示為:

1.1 矩陣加權(quán)關(guān)聯(lián)規(guī)則支持度和可信度

支持度表示規(guī)則的頻度。若文檔數(shù)據(jù)集T中包含項(xiàng)目集K的事務(wù)數(shù)稱為項(xiàng)目集K的支持?jǐn)?shù)，可用公式表示為:

其中，k為項(xiàng)集{X∪Y}的項(xiàng)目數(shù)，n為數(shù)據(jù)庫的記錄數(shù)。

可信度表示規(guī)則的強(qiáng)度，我們定義矩陣加權(quán)關(guān)聯(lián)規(guī)則可信度為:

用minsupport表示最小矩陣加權(quán)支持度閾值，則有support(x，y)≥minsupport。同理用minconf表示最小矩陣加權(quán)可信度閾值，則有conf(x，y)≥minconf。令I(lǐng)l?奐I是q-項(xiàng)集。Il項(xiàng)集在文檔數(shù)據(jù)庫中的出現(xiàn)次數(shù)為SC(Il)，若包含q-項(xiàng)集Il的k-項(xiàng)集是頻繁的，那么包含項(xiàng)集Il的k-項(xiàng)集最大權(quán)值之和為max w(Il，k)可表示為:

由公式(3)和(4)可以推導(dǎo)出包含q-項(xiàng)集Il的k-項(xiàng)集權(quán)值閾值我們用kiwt(Il，k)表示即可以得出以下公式:

若q-項(xiàng)集Il的k-項(xiàng)集權(quán)值之和大于等于k-項(xiàng)集權(quán)值閾值，則包含Il的k-項(xiàng)集很有可能是頻繁項(xiàng)集。對(duì)于矩陣加權(quán)k-項(xiàng)集的任何子集，只要至少存在一個(gè)子集的權(quán)值之和小于其k-權(quán)值閾值，則該k-項(xiàng)集一定是非頻繁項(xiàng)集。

1.2 矩陣加權(quán)關(guān)聯(lián)算法

矩陣加權(quán)關(guān)聯(lián)算法思想為根據(jù)包含(k-1)-項(xiàng)集的k-權(quán)值閾值找出可能生成頻繁k-項(xiàng)集的(k-1)-項(xiàng)集組成新的項(xiàng)集C(k-1)并進(jìn)行剪枝候選項(xiàng)集。經(jīng)過剪枝后的矩陣候選項(xiàng)集將大幅度減少。再由C(k-1)產(chǎn)生矩陣加權(quán)頻繁k-項(xiàng)集L(k-1) 并進(jìn)行剪枝候選項(xiàng)集。重復(fù)運(yùn)用k-權(quán)值閾值逐層迭代。直到矩陣加權(quán)候選項(xiàng)集集合為空時(shí)結(jié)束。最后根據(jù)矩陣加權(quán)可信度由矩陣加權(quán)頻繁項(xiàng)集生成文檔詞語之間的相關(guān)度(相似度)。其算法描述如下:

1) 掃描文檔數(shù)據(jù)庫T，找出可能的最大項(xiàng)目集的項(xiàng)目個(gè)數(shù)(Item_Maxsize)、項(xiàng)目總數(shù)(Item_count)和事務(wù)記錄總數(shù)(record_count)。

2) 掃描文檔數(shù)據(jù)庫T，累加各個(gè)1-項(xiàng)集的權(quán)值(SumWeight(C1)和支持?jǐn)?shù)(SC(C1))，找出各1-項(xiàng)集的最大權(quán)值(MaxWeight[C1])以及計(jì)算包含l-項(xiàng)集的2-權(quán)值閾值(Kiwt(C1，2))，最后產(chǎn)生C1，C1，L1。

3) 根據(jù)Apriori連接相似算法，由Ck-1連接生成Ck。累加候選項(xiàng)集Ck在數(shù)據(jù)庫T中出現(xiàn)的頻度。

4) 統(tǒng)計(jì)Ck中所有候選項(xiàng)集的權(quán)值之和SumWeight(Ck)和包含Ck的(k-1)-權(quán)值閾值(Kiwt(Ck，k+1))，進(jìn)行剪枝。

5) 生成頻繁項(xiàng)目集，并入庫。

6) 輸出繁項(xiàng)目集，產(chǎn)生文檔詞語之間的相關(guān)度(相似度)。

相似度得出后，根據(jù)計(jì)算結(jié)果就可以執(zhí)行聚類空間粒度聚類算法。

2 基于空間粒度的聚類算法

2.1 空間粒度分析理論及粒度分析

在文檔的歸類的問題上將所研究的問題用一個(gè)三元組(X，F(xiàn)，T)進(jìn)行描述[6]，其中X表示主題的論域，即考慮基本元素的集合。若F為屬性函數(shù)，則可以定義為F:X→Y，其中Y表述基本元素的屬性集合。T表示論域的結(jié)構(gòu)，我們把它定義為論域中各個(gè)基本元素之間的關(guān)系。從一個(gè)較“粗”的角度看問題，實(shí)際上是對(duì)X進(jìn)行簡化，把性質(zhì)相近的元素看成是等價(jià)的，把它們歸入一類，整體作為一個(gè)新元素，這樣就形成一個(gè)粒度較大的論域 ，從而把原問題(X，F(xiàn)，T)可以轉(zhuǎn)化成新層次上的問題([X]，[Y]，[T])。可以單獨(dú)進(jìn)行處理關(guān)系。

聚類算法是一種有效的數(shù)據(jù)分析方法，從劃分角度來看，聚類算法事實(shí)上每一種聚類結(jié)果都是對(duì)應(yīng)該數(shù)據(jù)集上的一種劃分，而一個(gè)等價(jià)關(guān)系就定義了數(shù)據(jù)集合的一個(gè)劃分。在不同的聚類閾值處得出不同的聚類結(jié)果。即使在某一次具體的聚類過程中簇內(nèi)部的粒度是相同的，但簇間的粒度可能很相似。本文所需要的結(jié)果應(yīng)該是劃分后的各個(gè)簇，其粒度差別大于一定的閾值，即簇間的粒度差異明顯，而簇內(nèi)的粒度相同。此時(shí)的關(guān)鍵就是選擇合適的簇間相似度，這是粒度基本思想在簇間的表現(xiàn)。

本文采用粒度分析方法即一個(gè)不斷分析比較的動(dòng)態(tài)過程，合并和分解法選擇來調(diào)整粒度。對(duì)于給定的相似度函數(shù)，取不同的閾值，必然得到一聚類，這些聚類一般是不同的。當(dāng)采用較大的閾值時(shí)，展現(xiàn)在我們面前的是樣本點(diǎn)集比較“粗 ’的輪廓，一些細(xì)枝末節(jié)被忽略掉了;而采用較小的閾值時(shí)，就能夠比較精細(xì)地刻畫樣本點(diǎn)之間一些細(xì)微差別。當(dāng)閾值R>R1時(shí)，所有樣本被聚一類，稱粗粒度聚類，而 R

因此在進(jìn)行聚類分析時(shí)，以“最優(yōu)”相似度函數(shù)為基礎(chǔ)，在所有可能的粒度中，尋找出一個(gè)“最優(yōu)”合適粒度。

2.2 基于關(guān)聯(lián)規(guī)則的空間粒度聚類算法

根據(jù)矩陣加權(quán)關(guān)聯(lián)算法的計(jì)算結(jié)果，把空間粒度原理應(yīng)用到聚類中，就可以設(shè)計(jì)出相應(yīng)的聚類算法:

1) 求所有文檔樣本的重心，并以離該重心最近的樣本作為中心點(diǎn)。

2) 求出其它未聚類的所有樣本與中心點(diǎn)的平均距離D。

3) 以平均距離為初始聚類，求出球形圓環(huán)。

4) 求當(dāng)前球形的重心，獲得新的球形，直到球形的樣本數(shù)不再增加為止。

5) 找離當(dāng)前球形的重最遠(yuǎn)的點(diǎn)作為下一步球形的圓心。

6) 重復(fù)2)～5)直到球形包含所有的樣本為程序結(jié)束條件。

7) 采用粒度分析法對(duì)得到的聚類結(jié)果進(jìn)行分析。根據(jù)矩陣加權(quán)關(guān)聯(lián)算法得出的相似度、人對(duì)文檔感興趣情況及結(jié)合實(shí)際情況判斷聚類結(jié)果。若粒度偏大即平均距離偏大，重新選擇新的D，返回(3);若粒度偏小轉(zhuǎn)步驟(8)，若粒度合適，則轉(zhuǎn)到步驟(4)。

8) 求出聚類結(jié)果中簇與簇兩兩之間的相似度，并對(duì)所有相似度值中求出最大的相似度值MAXSIM。

9) 初始化一個(gè)相似度閾值S。如果最大相似度MAXSIM

10)根據(jù)矩陣加權(quán)關(guān)聯(lián)算法得出的相似度、人對(duì)文檔感興趣情況及結(jié)合實(shí)際情況調(diào)整確定合適的粒度，再次對(duì)聚類結(jié)果進(jìn)行分析并適當(dāng)調(diào)整相似度閾值S，得到最后的聚類結(jié)果。該文的聚類算法在矩陣的初始構(gòu)造和關(guān)聯(lián)算法計(jì)算機(jī)相似的結(jié)果上都應(yīng)用到。再用粒度的粗細(xì)閥值進(jìn)行空間粒度聚類，進(jìn)一步對(duì)文檔的精確度進(jìn)行提高。

4 實(shí)驗(yàn)和結(jié)論

在實(shí)驗(yàn)中我們采用聚類準(zhǔn)確率來表示聚類精確度，即在一個(gè)類別中的正確分類與算法在該類上的所有分類的百分比。準(zhǔn)確率越高表明聚類算法在該類上出錯(cuò)的概率越小。則聚類精確度可定義為:

(6)

其中fpi是錯(cuò)分到簇Ci且屬于其他簇的文檔數(shù)。tpi是正確分到簇Ci中的文檔數(shù)。

為了對(duì)本文提出的算法進(jìn)行分析、評(píng)價(jià)，我們將它和K-Means算法及Apriori算法進(jìn)行比較。實(shí)驗(yàn)中采用文檔集從Internet上搜索得到的。整個(gè)實(shí)驗(yàn)在Windows 2003 server上進(jìn)行，計(jì)算機(jī)CPU為Inte3.5GHZ。從Internet上搜索的文檔由歷史、地理、數(shù)學(xué)、科技、文物、計(jì)算機(jī)、體育、生物、藝術(shù)、文化等10個(gè)大類，每類30篇文章。通過加權(quán)矩陣關(guān)聯(lián)規(guī)則來構(gòu)造文檔的空間矩陣，并根據(jù)式(3)計(jì)算詞頻及文檔矢量矩陣中各個(gè)元素的權(quán)值，我們以3個(gè)特征詞項(xiàng)為例(對(duì)多個(gè)特征詞項(xiàng)也一樣構(gòu)造)，然后利用式(1)和式(2)計(jì)算支持度support和可信度conf，得到表1的關(guān)聯(lián)規(guī)則表。其中support1表示特征詞項(xiàng)1對(duì)特征詞項(xiàng)2的支持度，support2表示特征詞項(xiàng)2對(duì)特征詞項(xiàng)3的支持度，同理conf1示特征詞項(xiàng)1對(duì)特征詞項(xiàng)2的可信度，conf2示特征詞項(xiàng)2對(duì)特征詞項(xiàng)3的可信度。

其中特征詞項(xiàng)的“中國”，“人們”，“共產(chǎn)黨”的平均支持度為Avgsupport為0.3146，可信度為:0.6058。然后根據(jù)矩陣加權(quán)關(guān)聯(lián)算法進(jìn)行相似度計(jì)算。根據(jù)計(jì)算結(jié)果可以得到聚類數(shù)目及聚類精確度，如表2所示。

從表2可以看出矩陣關(guān)聯(lián)規(guī)則的空間粒度算法的執(zhí)行時(shí)間比Apriori及K-均值算法的時(shí)間都要略長，影響時(shí)間的主要因數(shù)是迭代的次數(shù)增加及增加了矩陣關(guān)聯(lián)規(guī)則算法。但我們從表(2)的結(jié)果上發(fā)現(xiàn)矩陣關(guān)聯(lián)規(guī)則的空間粒度算法的正確率大大地提高，比Apriori提高了11.6%，比K-均值提高了9.1%，主要是因?yàn)檫M(jìn)行了對(duì)矩陣的初始化進(jìn)行聚類，然后利用了矩陣關(guān)聯(lián)規(guī)則算法進(jìn)行進(jìn)一步分析，得到結(jié)果后再次根據(jù)計(jì)算結(jié)果的相似度進(jìn)行聚類。使得正確率大大的提高。

以上是針對(duì)小文檔進(jìn)行的關(guān)聯(lián)聚類分析，接著我們分析針對(duì)大型文檔數(shù)據(jù)庫的文檔數(shù)隨時(shí)間的變化，由圖1可以看出矩陣關(guān)聯(lián)規(guī)則的空間粒度算法和K-均值算法在500-800之間的程序執(zhí)行時(shí)間比較接近。但在900以上矩陣關(guān)聯(lián)規(guī)則的空間粒度算法的時(shí)間明顯比K-均值算法的時(shí)間要少很多，這主要由于新算法在執(zhí)行剪枝后矩陣的元數(shù)變小的原因。實(shí)驗(yàn)表明該算法對(duì)于大文檔的時(shí)間復(fù)雜度比較理想。

5 結(jié)束語

該文在原有的關(guān)聯(lián)算法的基礎(chǔ)上，提出了一種矩陣加權(quán)關(guān)聯(lián)規(guī)則的空間粒度算法。該算法的核心是根據(jù)文檔的特征向量提取文檔的相似度，再在該關(guān)聯(lián)規(guī)則算法上進(jìn)行聚類來尋找相似關(guān)系的頻繁項(xiàng)目集。在粒度空間中采用相似度閥值進(jìn)行調(diào)整粒度的粗細(xì)問題。通過矩陣加權(quán)關(guān)聯(lián)規(guī)則算法進(jìn)行聚類，因此在精度上有較大的提高。該方法是一個(gè)新的思路，實(shí)驗(yàn)結(jié)果表明在解決多維數(shù)據(jù)有很好的效果。但在中小文檔中的時(shí)間復(fù)雜度比以往的算法略高點(diǎn)，但在對(duì)混合數(shù)據(jù)的處理能力上有一定的欠缺，下階段將繼續(xù)進(jìn)行算法的改進(jìn)以期望能對(duì)混合數(shù)據(jù)進(jìn)行處理。

參考文獻(xiàn):

[1] HUANG M X，YAN X W，ZHANG S C.Review and perspective of query expansion techniques.Computer Applications and Software，2007，24(11):1-4(in Chinese with English abstract).

[2] KURAMOCHI M.Karypis G Frequent Subgraph Discovery//Pro-caedings of the 2001 IEEE International Conference on Data Mining.San Jose，California，USA，2001:313-320.

[3] BEBEL B，KROLIKOWSLD Z，WREMBL R.Formal Approach to Modeling a Multiversion Data Warehouse[J].Bulletin of the Polish Academy of Sciences，2006，54(1):51-62.

[4] AGRAWAL R，IMIELINSKI T，SWAMI A.Mining Association Rules between Sets of Items in Large Database[C]//Proceedings of the ACM SIGM OD Conference on Management of Data.Washington，USA:ACM Press，1993.

[5] MEIDLDI W，NIEDERREITER H.Counting functions and expected values for the k-error linear complexity[J].Finite Fields Appl，2002，8:142-154.

[6] MEIDLDI W，NIEDERREITER H.Linear complexity k-error linear complexity，and the discrete fourier transform[J].Complexity，2002，18:87-103.

[7] MULLER K，MIKA S，RATSCH G.An Introduction to Kernel-based Learning Algorithms[J].IEEE Trans.on Neural Networks，2001，12(2):181-201.

[8] 王倫文.聚類的粒度分析[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(5):29-31，65.

[9] 卜東坡，白碩，李國杰.聚類、分類中的粒度原理[J].計(jì)算機(jī)學(xué)報(bào)，2002，25(8):810-816.

[10] 李杰，徐勇，朱昭賢.模糊C均值算法參數(shù)仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2008，20(2):509-513.