摘 要： 對(duì)Web文檔進(jìn)行分類(lèi)可以較好地解決網(wǎng)上信息雜亂的現(xiàn)象，介紹了Web文檔分類(lèi)的相關(guān)知識(shí)以及關(guān)鍵技術(shù)，并對(duì)目前的分類(lèi)方法進(jìn)行了總結(jié)，對(duì)Web文檔分類(lèi)中關(guān)聯(lián)規(guī)則挖掘研究現(xiàn)狀和主要技術(shù)進(jìn)行了論述，指出了負(fù)關(guān)聯(lián)規(guī)則在Web文檔分類(lèi)中的發(fā)展趨勢(shì)。
??? 關(guān)鍵詞： 數(shù)據(jù)挖掘；Web文檔分類(lèi)技術(shù)；負(fù)關(guān)聯(lián)規(guī)則
?
隨著科學(xué)技術(shù)的發(fā)展，Internet正在以令人難以置信的速度迅速發(fā)展，使得萬(wàn)維網(wǎng)成為一個(gè)擁有大量資源的數(shù)據(jù)庫(kù)。這個(gè)蘊(yùn)含著豐富資源的信息空間為數(shù)據(jù)挖掘研究提出了新的挑戰(zhàn)，存放的這些信息絕大多數(shù)都是以文本的形式存在的，如何在浩瀚的文本信息中挖掘到潛在的知識(shí)是一個(gè)有待解決的問(wèn)題。為了幫助人們有效地組織和管理海量的Web信息，Web文檔分類(lèi)技術(shù)應(yīng)運(yùn)而生。
1 Web文檔分類(lèi)的概念及分類(lèi)方法
1.1 Web文檔分類(lèi)的概念
??? Web挖掘[1]是指從大量Web文檔的集合C中發(fā)現(xiàn)隱含的模式P。如果將C看作輸入，將P看作輸出，那么Web挖掘的過(guò)程就是從輸入到輸出的一個(gè)映射ζ：C→P。一般地，Web挖掘可以簡(jiǎn)單的分為三類(lèi)[2]：Web內(nèi)容挖掘(Web content mining)，Web結(jié)構(gòu)挖掘(Web structure mining)和Web使用記錄的挖掘(Web usage mining)。
??? 文檔分類(lèi)是Web內(nèi)容挖掘中一項(xiàng)非常重要的任務(wù)，它是根據(jù)頁(yè)面的不同特征，將其劃分為事先建立起來(lái)的不同類(lèi)，屬于有指導(dǎo)的機(jī)器學(xué)習(xí)問(wèn)題。其目的是讓機(jī)器學(xué)會(huì)一個(gè)分類(lèi)函數(shù)或分類(lèi)模型，該模型能把Web文本映射到已存在的多個(gè)類(lèi)別中的某一類(lèi)，使檢索或查詢(xún)的速度更快，準(zhǔn)確率更高。這樣，用戶(hù)在瀏覽Web文檔時(shí)，就不會(huì)因?yàn)榭v橫交錯(cuò)的超級(jí)鏈接而“迷路”。
??? Web文本分類(lèi)是一個(gè)典型的有教師的機(jī)器學(xué)習(xí)問(wèn)題，一般的可分為數(shù)據(jù)預(yù)處理、構(gòu)選分類(lèi)器和文檔分類(lèi)3個(gè)階段。數(shù)據(jù)挖掘主要是針對(duì)結(jié)構(gòu)數(shù)據(jù)庫(kù)，如數(shù)據(jù)倉(cāng)庫(kù)中的數(shù)據(jù)，然而，在網(wǎng)絡(luò)中大部分的信息是存儲(chǔ)在文本數(shù)據(jù)庫(kù)當(dāng)中，即所謂的半結(jié)構(gòu)化數(shù)據(jù)(semi-structure data)，它既不是完全無(wú)結(jié)構(gòu)的，也不是完全結(jié)構(gòu)的，因此需要對(duì)文本進(jìn)行預(yù)處理，抽取代表其特征的元數(shù)據(jù)，這些特征可以用結(jié)構(gòu)化的形式保存。
??? 訓(xùn)練算法的工作是對(duì)訓(xùn)練文檔集合中每篇文本對(duì)應(yīng)的詞表進(jìn)行統(tǒng)計(jì)，計(jì)算出類(lèi)別向量矩陣，同時(shí)進(jìn)行歸一化，最后保存訓(xùn)練得到的向量表，即得到了分類(lèi)知識(shí)庫(kù)。分類(lèi)算法(也可稱(chēng)為識(shí)別算法)則依據(jù)訓(xùn)練得到的分類(lèi)知識(shí)庫(kù)，并用一定的算法對(duì)待分類(lèi)文本進(jìn)行分類(lèi)。Web文檔分類(lèi)的步驟如圖1所示。
?
1.2 Web文檔分類(lèi)方法
目前關(guān)于Web文檔分類(lèi)的研究已經(jīng)取得了很大的進(jìn)展，并提出了一系列的分類(lèi)法。常見(jiàn)的文檔分類(lèi)方法可以分為三類(lèi)[3]：一類(lèi)是基于TFIDF方法，包括TFIDF算法、K近鄰算法等；另一類(lèi)則是基于統(tǒng)計(jì)學(xué)分類(lèi)方法，如貝葉斯算法、最大熵算法等；第三類(lèi)是基于知識(shí)學(xué)習(xí)的方法，如決策樹(shù)(Decision Tree)C4．5等算法。
近年來(lái)，Web文檔分類(lèi)已成為眾多領(lǐng)域研究者的熱門(mén)研究課題，研究者們從不同的角度把越來(lái)越多的知識(shí)引入該領(lǐng)域。
向量空間模型VSM(Vector Space Model)將所有文本都表示成具有某種相同結(jié)構(gòu)的數(shù)據(jù)，它是Salton等人于上世紀(jì)60年代末首先提出的，最早應(yīng)用于信息檢索領(lǐng)域。而Joachims最早將SVM方法用于文本分類(lèi)[4]。饒文碧等人[5]提出了一種擴(kuò)展的基于VSM的Web文本分類(lèi)，在傳統(tǒng)的訓(xùn)練和分類(lèi)算法的基礎(chǔ)上，加入了一個(gè)反饋判定的算法，這種方式更加貼近真正意義上的機(jī)器學(xué)習(xí)，使得該算法具有一定程度上的認(rèn)知自主性和不斷學(xué)習(xí)的能力。由于Web文檔往往具有不確定的特征，使得利用模糊集合理論對(duì)信息檢索過(guò)程的不確定性建立模型成為可能，雷景生在參考文獻(xiàn)[6]中提出了一種基于模糊相關(guān)技術(shù)的Web文檔分類(lèi)方法。張志強(qiáng)、鄭家恒提出基于加權(quán)類(lèi)軸的方法[7]，利用了Web文本的標(biāo)記信息在文檔中的重要程度不同，使用了Web標(biāo)記的三級(jí)加權(quán)處理，使向量的維數(shù)有所下降。胡和平、易高翔提出了基于容錯(cuò)粗糙集的方法[8]，利用容錯(cuò)關(guān)系來(lái)表示文檔，利用特征詞協(xié)同出現(xiàn)的價(jià)值，豐富特征詞對(duì)Web文檔的描述。
2 關(guān)聯(lián)規(guī)則在Web文檔分類(lèi)中的研究
2.1 文本預(yù)處理
由于Web上的內(nèi)容大都是半結(jié)構(gòu)化的，通常要進(jìn)行結(jié)構(gòu)化的表示。表示方法為：一篇文檔有類(lèi)標(biāo)簽C，詞條為T(mén)(T={t1，t2，…，tm})，用事務(wù)D={C，t1，t2，…，tm}來(lái)表示該文檔模型，則Web文檔集可表示成事務(wù)集，其項(xiàng)集由文檔詞條和文檔所屬類(lèi)別組成。
在數(shù)據(jù)清理階段，采用移除停用詞和計(jì)算TF/IDF的方式對(duì)文本文檔進(jìn)行清理。需要移除對(duì)構(gòu)造關(guān)聯(lián)分類(lèi)器價(jià)值不大的詞條，形成清潔文檔，包括一些副詞、連詞、某些代詞等對(duì)分類(lèi)意義不大的詞。其中TF/IDF的公式如下：
其中，TF(Wi，Doc)指單字Wi在文檔Doc中出現(xiàn)頻度，D為文檔總數(shù)，DF(Wi)為單字Wi在其中出現(xiàn)至少一次的文檔數(shù)目。
2.2 關(guān)聯(lián)規(guī)則的產(chǎn)生
經(jīng)過(guò)文本預(yù)處理后，就要尋找頻繁項(xiàng)集，借鑒了傳統(tǒng)的Apriori算法，找到了一種很適合處理文本文檔事務(wù)集的方法：對(duì)每個(gè)候選項(xiàng)集定義一個(gè)tidlist的結(jié)構(gòu)，項(xiàng)集Ii的tidlist由包含事務(wù)的tid組成。1-itemset通過(guò)搜索文檔事務(wù)集D得到，候選k項(xiàng)集的tidlist可由該候選k項(xiàng)集的那2個(gè)(k-1)項(xiàng)集的tidlist求交集產(chǎn)生。
在文檔分類(lèi)中產(chǎn)生的關(guān)聯(lián)規(guī)則數(shù)量可能是巨大的，為了減少噪音信息和分類(lèi)時(shí)間，所以要對(duì)文本關(guān)聯(lián)規(guī)則進(jìn)行剪枝，馬光志等人定義了正負(fù)相關(guān)的定義：
定義 規(guī)則
(T為詞條項(xiàng)集，C為類(lèi)標(biāo)簽)的作用度(lift)定義為可信度對(duì)期望可信度的比值，即I(
)=P(C|T)/P(C)。如果，I(
)的值大于1，則說(shuō)T和C正相關(guān)，表明每一個(gè)的出現(xiàn)都蘊(yùn)涵另一個(gè)的出現(xiàn)；如果結(jié)果值等于1，則它們相互獨(dú)立，無(wú)相關(guān)性；如果小于1，表明它們負(fù)相關(guān)。
所以在剪枝的時(shí)候就根據(jù)定義選擇正相關(guān)的規(guī)則，去掉獨(dú)立和負(fù)相關(guān)的規(guī)則。然后剔除那些特殊并且置信度較低的規(guī)則，最后應(yīng)用數(shù)據(jù)庫(kù)候選覆蓋來(lái)選取最顯著規(guī)則子集。
2.3 利用文本關(guān)聯(lián)規(guī)則進(jìn)行文本分類(lèi)
??? 常見(jiàn)的方法是將新文檔分配到與之規(guī)則匹配最多的類(lèi)或是分配給與第一個(gè)規(guī)則匹配的類(lèi)別。參考文獻(xiàn)[9]提出了一種折中方法，綜合考慮匹配規(guī)則數(shù)和置信度的影響。將規(guī)則表按類(lèi)標(biāo)簽分組，設(shè)定一個(gè)置信度閾值，將低于該閾值的匹配規(guī)則從分組中剔除，接著將分組按置信度的和排序。
在進(jìn)行類(lèi)識(shí)別時(shí)，遵循以下兩條規(guī)則：(1)優(yōu)先選擇置信度和最大分組的標(biāo)簽作為該文檔的類(lèi)標(biāo)簽；(2)在置信度和相等的情況下，選擇匹配規(guī)則最多組的標(biāo)簽作為該文檔的類(lèi)標(biāo)簽。
3 負(fù)關(guān)聯(lián)規(guī)則的研究現(xiàn)狀及主要技術(shù)
關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要的、高度活躍的領(lǐng)域。傳統(tǒng)的關(guān)聯(lián)規(guī)則AR(association rule)是
的形式，用于挖掘顧客事務(wù)數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)關(guān)系，最初由R.Agrawal等人于1993年首先在參考文獻(xiàn)[11]中提出，以后諸多研究人員對(duì)此進(jìn)行了大量研究，其工作主要是對(duì)原有的算法進(jìn)行改進(jìn)，以提高算法挖掘規(guī)則的效率。關(guān)聯(lián)規(guī)則挖掘?qū)嵸|(zhì)上就是在滿(mǎn)足用戶(hù)給定的最小支持度的頻繁項(xiàng)集中，找出所有滿(mǎn)足最小置信度的關(guān)聯(lián)規(guī)則，具體分為兩步：(1)找出所有的頻繁項(xiàng)集；(2)用頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。
Zhu等人在參考文獻(xiàn)[14]中提出了一種快速有效的基于FP-tree的負(fù)關(guān)聯(lián)規(guī)則挖掘算法MNARA，該算法不但可以發(fā)現(xiàn)所有的負(fù)關(guān)聯(lián)規(guī)則，而且由于整個(gè)過(guò)程只需掃描事務(wù)數(shù)據(jù)庫(kù)兩次，算法是有效和可行的。
? Dong等人提出了一種PNARC模型[15]，利用了支持度-置信度框架，采用相關(guān)性檢驗(yàn)方法，不僅能夠同時(shí)挖掘出頻繁項(xiàng)集中的正、負(fù)關(guān)聯(lián)規(guī)則，而且能夠檢測(cè)并刪除相互矛盾的規(guī)則；隨后又給出一種基于多置信度和
檢驗(yàn)的挖掘正負(fù)關(guān)聯(lián)規(guī)則的方法，并且提出了一種PNARMC算法[16]，該算法不僅能夠正確地產(chǎn)生正負(fù)關(guān)聯(lián)規(guī)則，而且能靈活地控制關(guān)聯(lián)規(guī)則的數(shù)量。在PNARC模型中給出了正、負(fù)關(guān)聯(lián)規(guī)則的定義。
4 負(fù)關(guān)聯(lián)在Web文檔分類(lèi)中的發(fā)展趨勢(shì)
負(fù)關(guān)聯(lián)規(guī)則的研究為傳統(tǒng)關(guān)聯(lián)規(guī)則開(kāi)辟了一個(gè)嶄新的領(lǐng)域。研究表明，負(fù)關(guān)聯(lián)規(guī)則同樣起著非常重要的作用，一方面可以進(jìn)一步完善項(xiàng)集間的關(guān)聯(lián)規(guī)則分析，另一方面可以為決策支持提供更多有用的信息。
在進(jìn)行Web文檔分類(lèi)的時(shí)候，文檔集產(chǎn)生的關(guān)聯(lián)規(guī)則數(shù)往往是巨大的，所以就需要進(jìn)行剪枝處理，目前在剪枝的時(shí)候直接把負(fù)相關(guān)的規(guī)則剪掉，但是在負(fù)相關(guān)中也包含著有用的信息，所以本文提出了基于負(fù)關(guān)聯(lián)規(guī)則的Web文檔分類(lèi)技術(shù)。
基于負(fù)關(guān)聯(lián)規(guī)則的Web文檔分類(lèi)策略，是在基于關(guān)聯(lián)規(guī)則分類(lèi)的基礎(chǔ)上，為了更有效地體現(xiàn)現(xiàn)實(shí)事件直接的關(guān)聯(lián)而采取的分類(lèi)策略，這種分類(lèi)方法和正關(guān)聯(lián)規(guī)則分類(lèi)相結(jié)合能夠更加有效和準(zhǔn)確地進(jìn)行分類(lèi)，可以更加全面地分析各種因素之間隱藏的內(nèi)在聯(lián)系。運(yùn)用負(fù)關(guān)聯(lián)的研究方法來(lái)完善文檔集產(chǎn)生關(guān)聯(lián)規(guī)則的正確度，從而提高Web文檔分類(lèi)的精確度。
現(xiàn)有的WEB文檔的分類(lèi)方法中，基于負(fù)關(guān)聯(lián)的Web文檔分類(lèi)研究的比較少，在以后的研究中應(yīng)該結(jié)合負(fù)關(guān)聯(lián)規(guī)則將支持度和置信度結(jié)合起來(lái)考慮，這將是一個(gè)新的研究趨勢(shì)。
參考文獻(xiàn)
[1] QUEK C Y. Classification of World Wide Web documents Senior Honors dissertation. School of Computer Science Camegie Mellon University， 1997.
[2] MADRIA S K. Research Issues in Web Data Miming[C]. Proc. of Data Ware housing and Knowledge Discovery， First Inte1.Conf.DaWak 99.1999：303-312.
[3] 符發(fā).中文文本分類(lèi)中特征選擇方法的比較[J].現(xiàn)代計(jì)算機(jī)，2008(6)：43-45.
[4] JOACHIMS T. Text categorization with support vector machines: learning with many relevant features. In: Proceedings of 10th European Conference on Machine Learning(ECML-98)， Chemnitz， DE.1998：137-142.
[5] 饒文碧，柯慧燕，張麗.一種擴(kuò)展的基于VSM的Web文本分類(lèi)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2006，23(10)．
[6] 雷景生.基于模糊相關(guān)的Web文檔分類(lèi)方法[J].計(jì)算機(jī)工程，2005，31(24).
[7] 張志強(qiáng)，鄭家恒.基于加權(quán)類(lèi)軸的Web文本分類(lèi)方法研究[J].計(jì)算機(jī)應(yīng)用，2004，24(2).
[8] 胡和平，易高翔.一種基于容錯(cuò)粗糙集的Web文檔分類(lèi)方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27(2).
[9] 馬光志，張生庭.基于關(guān)聯(lián)規(guī)則的Web文檔分類(lèi)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2005(9).
[10] AOKI P M. Generalizing search in generalized search trees. In Proc.1998 Int .Conf. Data Engineering(ICDE’98)，April 1998.
[11] AGRAWAL R， IMIELINSKI T，SWAMI A. Mining association rules between sets of items in large database[A].Proceeding of the 1993 ACM SIGMOD International Conference on Management of Data[C]. New York： ACM Press， 1993：207-216.
[12] WU Xin Dong， ZHANG Cheng Qi， ZHANG Shi Chao. Mining both positive and negative association rules[A]. Proceedings of the 19th International Conference on Machine Learning (ICML-2002)[C]. San Francisco： Morgan Kaufmann Publishers， 2002： 658-665.
[13] ZHANG W X， ZHANG C， ZHANG S. Efficient Mining of both Positive and Negative Association Rules， ACM Transactions on Information Systems[J]. 2004，22：381-405.
[14] ZHU Y， SUN L， YANG H. Algorithm for Mining Negative Association Rules Based on Frequent Pattern Tree[J]. Computer Engineering，Vol.32， No.22.
[15] WANG D X， SONG S H. Study of Negative Association Rules[J]. Beijing Institute of Technology Journal，2004，24(11)： 978-981.
[16] DONG X， SUN F， HAN X， et al. Study of Positive and Negative Association Rules Based on Multi-confidence and Chi-Squared Test[J]. LNAI 4093， Springer-Verlag Berlin Heidelberg， 2006：100-109.