基于粗糙集的WEB文本特征約簡

摘要:為了得到用戶滿意的文本特征約簡，在粗集理論屬性約簡技術的基礎上，提出文本特征選擇的新方法RSUA。RSUA方法采用用于關聯規則挖掘的Apriori算法的思想進行決策表的約簡。實驗驗證了RSUA方法的有效性。

關鍵詞:RSUA;粗糙集;Web

中圖分類號:TP301文獻標識碼:A文章編號:1009-3044(2009)32-9052-02

Selece Eigenvectors Form Documents Based on Rough Set Reduction Algorithm

LI Hong-xia， YI Li-ping

(School of Computer， Jiangxi Aviation Vocational Technical College， Nanchang 330024， China)

Abstract: The paper discuss a new method(RSUA) for selece eigenvectors form documents based on rough Set Reduction. It put forward a mining model of association rules with decision attributes based on Apriori.

Key words: RSUA; Rough Set; Web

網絡的快速發展給人們帶來大量信息，網頁中最主要的信息資源是文本，WEB挖掘就是針對網上大量文本信息進行知識發現、知識表示的研究領域。由于構成文本的原始詞匯量往往非常巨大，一般為幾萬甚至幾十萬，所以文本的原始特征項空間也非常巨大，這樣大的特征空間對許多分類算法來說是很難處理的，在實際應用中系統運行速度也對特征空間的壓縮提出了要求。對文本原始特征空間的壓縮一般使用特征選擇或特征提取方法。

文本挖掘的一個重要問題就是高維的特征空間，這些特征空間是由文本中的詞或詞組構成的，許多傳統算法難處理。

1 算法的設計思想

關聯規則是關聯分析中的一種常見的技術，是尋找在同一個事件中出現的不同項的相關性。挖掘關聯規則問題就是產生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關聯規則。在利用粗糙集的決策表進行數據分析，決策屬性的選取很重要，對一個問題當有多個影響因素時，通過關聯規則得到一些符合最小支持度和最小可信度的一些規則，從中可以發現一些規則，這樣可以根據決策規則的條件，作為粗糙集決策表的決策屬性，利用粗糙集進行運算，得到這一決策屬性的相關因素。

而利用粗糙集進行分析時，可以約簡冗余屬性，縮小考慮范圍，同時驗證或從另一角度對同一問題進行分析。另外，粗糙集可以處理含有不一致、噪聲、不完備的數據，比關聯規則具有更廣的使用范圍。粗糙集的約簡中，將關聯規則挖掘和粗糙集理論結合起來，引入關聯規則中的支持度概念，并重新定義了這個概念。

在決策表DT中，t為條件屬性，s為決策屬性，規則t=>s的基數card(t=>s)稱作規則t=>s的支持度，記為sup(t=>s);屬性t的基數card(t)稱作屬性t的支持度，記為sup(t)。

假如一條規則t=>s的sup(t=>s)=sup(t)，則稱該規則是確定性規則;假如一條確定規則的支持度大于用戶指定的最小支持度，稱這條規則為強確定性規則。

這里主要討論決策表中的強確定性規則，提出算法RSUR，該算法采用用于關聯規則挖掘的Apriori算法的思想進行決策表的約簡，即“頻繁項集的所有非空子集都必須也是頻繁的”，也就是:假如規則t=>s不是強的，則它的擴展tΛp=>s也不是強的。算法根據用戶指定的最小支持度，利用Apriori性質刪除低于最小支持度的規則，得到強確定的規則表。

2 算法的描述

算法RSUA的算法描述如下:

輸入:決策表DT，最小支持度minup;

輸出:所產生的規則集。

步驟一:對決策表進行屬性約簡;

步驟二:K賦值為1;

步驟三:計算候選集CK中每個屬性的屬性支持度和規則支持度;

步驟四:若規則支持度小于最小支持度，則將其從CK中刪除;若該規則的屬性支持度等于規則支持度，則將該規則移入規則集Pk;

步驟五:將CK擴展為CK+1，首先掃描CK，將CK中的每兩項合成具有K+1個屬性的候選項，插入CK+1中。接著檢查CK+1中的每一項C，若C的K子集中有不在CK中的項，則將C刪除;若C是不相容的，將C刪除。最后得到CK+1，將K賦值為K+1;

步驟六:循環調用三至五步，直到CK為空;

步驟七:結束。

3 實驗結果

為了驗證RSUA算法的有效性，使用實驗數據集測試RSUA算法。首先與傳統決策表算法-最小值約簡算法進行實驗對比。表1的最左列是數據集的名稱，第2，3欄分別是該數據集的實例個數和屬性個數。

為進一步驗證RSUA算法的有效性，與傳統的基于區分距陣的約簡算法進行實驗對比。采用UCI機器學習數據庫中的數據集舉行測試。對該數據集中的11個決策表舉行屬性約簡，結果如表2所示。

4 結束語

從表1和表2的約簡結果中可以看出:

1) 算法RSUA數據集的規則約簡率和數據約簡率大于傳統算法的學習結果。

2) 算法RSUA的運行時間一般大于傳統算法的學習結果，在實例數據和屬性較多的情況下，要花費更多的時間。這是由于算法RSUA采用了多次迭代的方法，并且所設計的數據結構較為復雜的緣故。

3) 采用不同的數據集進行同樣的算法對比實驗是，結果相差較大。說明文檔的規范程度、文本分詞算法的選擇、文本結構化描述都會影響算法的執行結果。

4) 本算法在約簡過程中保留了所有對用戶有用的規則，它并不特別注重約簡率的大小，而主要是面向實用系統的，因此約簡率并非是最好的衡量算法的標準。

參考文獻:

[1] 常犁云.一種基于Rough Set理論的屬性約簡及規則提取方法[J].軟件學報，1999，10(11):1206-1211.

[2] Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases[C].Proceedings of the ACM SIGMOD Conference on Management of data，1993:207-216.

[3] Kryszkiewice M.Strong rules in large database[Z].

[4] Lin T Y. Rough set theory in very large database[C].In Procedding os CESA'96，Lille，1996，2，936-941.

[5] 朱雪龍.應用信息論基礎[M].北京:清華大學出版社，2001.

[6] 史忠植.知識發現[M].清華大學出版，2002.

[7] 郭萌，王鈺.數據挖掘與數據庫知識發現:綜述[J].模式識別與人工智能，1998，11(3).

[8] 陳棟.KDD研究現狀及發展[J].計算機科學，1996，23(6).

[9] 張文修，吳偉志，梁吉業，等.粗糙集理論與方法[M].北京:科技出版社，2001.

[10] Pawlak Z.Rough sets:Theoretical aspects of Reasoning about Data[M].Dordrecht:Kluwer Acasemic Publishers，1991.

[11] Pawlak Z.Vagueness and uncertainty-Rough Set Prospective[J]，Computational Intelligence，1995，11(2):227-232.

[12] 曾黃麟.粗糙集理論及應用_關于數據推理的新方法[M].重慶:重慶大學出版社，1996:61-82.

[13] 李水平.數據采掘技術回顧[J].小型微型計算機系統，1998，19(4).

[14] 鐵治欣，陳奇，俞瑞釗.關聯規則采掘綜述[J].計算機應用研究，2000(1):1-5.