基于粗糙集與貝葉斯決策的不良網(wǎng)頁過濾研究

孫 艷，周學(xué)廣

（海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢430033）

1 引言

隨著網(wǎng)絡(luò)的普及，人們每天接觸的信息與日俱增，信息的迅速膨脹產(chǎn)生了“信息過載”和“信息迷航”，同時(shí)也加大了網(wǎng)絡(luò)不良信息（包括垃圾信息、反動信息、虛假信息、惡意信息等）的傳播，帶來了各種信息安全問題和社會問題，因此不良信息過濾問題日益被人們重視。

1982年，Denning在計(jì)算機(jī)協(xié)會通信（CACM）上首次提出信息過濾的概念［1］。1987年，Malone等人在CACM上提出了兩種信息過濾行為方式：認(rèn)知過濾和社會過濾［2］。認(rèn)知過濾即基于內(nèi)容的過濾［2］。Nanas將信息過濾分為基于內(nèi)容的過濾和協(xié)同過濾［3］?；趦?nèi)容的過濾是解決當(dāng)前網(wǎng)絡(luò)不良信息泛濫問題的主流技術(shù)。從內(nèi)容上看，不良信息過濾問題可以看作是一個(gè)“兩類”分類問題。因此，各種分類算法可以應(yīng)用于不良信息過濾中，如貝葉斯算法［4］、支 持 向 量 機(jī)［5］、粗 糙 集 理 論［6］、決 策 樹 算法［7］等。Pang等人曾用貝葉斯方法、最大熵法和支持向量機(jī)法對電影評論做分類效果評比，發(fā)現(xiàn)支持向量機(jī)的分類效果最好［8］。雖然SVM的分類效果優(yōu)于其他分類方法，但是其計(jì)算開銷大的缺點(diǎn)促使研究人員尋找更加完美的分類器。

貝葉斯算法是以貝葉斯定理為理論基礎(chǔ)的一種在已知先驗(yàn)概率與條件概率情況下得到后驗(yàn)概率的文本分類算法。貝葉斯分類算法原理簡單，健壯性強(qiáng)。粗糙集理論能夠獲得分類所需的最小特征屬性集，在不影響分類精度的條件下降低特征向量的維數(shù)，得到最簡的顯式表達(dá)的分類規(guī)則。采用貝葉斯和粗糙集理論相結(jié)合的方法進(jìn)行不良網(wǎng)頁過濾，可以優(yōu)化分類系統(tǒng)的總體性能。

在本文中，我們利用粗糙集中區(qū)分矩陣和邏輯運(yùn)算對網(wǎng)頁特性現(xiàn)象進(jìn)行知識約簡，剔除判斷網(wǎng)頁類別的冗余屬性，對約簡后的網(wǎng)頁特征現(xiàn)象進(jìn)行網(wǎng)頁類別的初步分類，建立網(wǎng)頁類別決策初表，然后進(jìn)行網(wǎng)頁分類，通過網(wǎng)頁歸類，建立網(wǎng)頁類別決策復(fù)表，最后通過貝葉斯決策過程來判別網(wǎng)頁類別以及決定是否過濾。

2 粗糙集理論

粗糙集理論是一種新的處理模糊和不確定性知識的數(shù)學(xué)工具。其主要思想就是在保持分類能力不變的前提下，通過知識約簡，導(dǎo)出問題的決策或者分類的規(guī)則。知識約簡是粗糙集理論的核心內(nèi)容之一。眾所周知，知識庫中知識（屬性）并不是同等重要的，甚至其中某些知識是冗余的。所謂知識約簡就是在保持知識庫分類能力不變的條件下，刪除其中不相關(guān)或不重要的知識，并得到知識的最小表達(dá)。本文提出利用區(qū)分矩陣和區(qū)分函數(shù)［9］來表達(dá)知識，它能夠很容易地計(jì)算約簡和核。

設(shè)K＝（U，P，AT，V，ρ）為一概率知識表示系統(tǒng)，即U是論域，P是U的子集全體構(gòu)成的σ代數(shù)上的概率測度，AT＝｛a1，a2，…，an｝是有限個(gè)屬性構(gòu)成的集合，V＝V1×V2×…×Vn，Vi是屬性ai的值域，ρ：U→V是信息函數(shù)，對于U 中的每個(gè)對象x，ρ（x）稱為x的描述，具有相同描述的對象是不可分辨的，記與x具有相同描述的對象全體為［x］。設(shè)Ω＝｛ω1，ω2，…，ωs｝是具有有限個(gè)特征狀態(tài)的集合，每個(gè)具有狀態(tài)ωi的對象是U的子集，常稱為概念，A＝｛r1，r2，…，rm｝是 m 由個(gè)可能決策行為構(gòu)建的集合，P（ωj｜［x］）表示一個(gè)對象在描述［x］下處于狀態(tài)ωj的概率，一般假定P（ωj｜［x］）為已知的。令λ（ri｜ωj）表示狀態(tài)ωj時(shí)采用決策ri的風(fēng)險(xiǎn)損失。

3 粗糙集與貝葉斯決策的網(wǎng)頁過濾方法

本文提出一種采用粗糙集與貝葉斯決策相結(jié)合的不良網(wǎng)頁過濾方法，在相應(yīng)的網(wǎng)頁特征現(xiàn)象對應(yīng)的各個(gè)網(wǎng)頁類別下，利用粗糙集中區(qū)分矩陣和邏輯運(yùn)算對網(wǎng)頁特性現(xiàn)象進(jìn)行知識約簡，剔除判斷網(wǎng)頁類別的冗余屬性，對約簡后的網(wǎng)頁特征現(xiàn)象進(jìn)行網(wǎng)頁類別的初步分類，建立網(wǎng)頁類別決策初表，然后進(jìn)行網(wǎng)頁分類，通過網(wǎng)頁歸類，建立網(wǎng)頁類別決策復(fù)表，最后通過貝葉斯決策過程來確定頁面類別以及是否進(jìn)行過濾。

粗糙集對網(wǎng)頁特征現(xiàn)象信息的約簡方法如下：設(shè)決策表系統(tǒng)為S＝（U，A，V，f），S為知識表達(dá)系統(tǒng)，它對應(yīng)網(wǎng)頁分類決策系統(tǒng)；A＝P∪D是屬性集合，子集P＝｛a［j］｜i＝1，…，k｝和D＝｛d｝分別稱為條件屬性集和決策屬性集，在網(wǎng)頁分類中分別對應(yīng)網(wǎng)頁特征現(xiàn)象集和網(wǎng)頁類型集；U＝｛x1，x2，…，xn｝為論域，對應(yīng)網(wǎng)頁分類中的被分類的單個(gè)網(wǎng)頁對象集；a［i］（xj）是被分類頁面xj在特征現(xiàn)象a［i］上的取值。區(qū)分矩陣C（i，j）表示區(qū)分矩陣中第i行和第j列交點(diǎn)處的元素，則區(qū)分矩陣CD定義為：

其中｛m［k］｜m［k］∈P∧m［k］（xi）≠m［k］（xj）｝。利用區(qū)分矩陣進(jìn)行屬性約簡的算法如下：

貝葉斯決策過程在不良網(wǎng)頁過濾中簡述如下：假定一個(gè)對象的描述為［x］，對于這個(gè)對象實(shí)施了決策ri，由于P（ωj｜［x］）是在給定描述［x］下的處于ωj的概率，因此對象在給定描述［x］下采用決策ri的期望損失（常稱為風(fēng)險(xiǎn)條件）可由全概率公式得到：

對于給定描述［x］，記τ（x）為一個(gè)決策規(guī)則，即τ（x）∈A，則τ是描述空間到A 的一個(gè)函數(shù)。令R是在給定一個(gè)總體決策規(guī)則下的期望總體風(fēng)險(xiǎn)。由于R（τ（x）｜［x］）是在描述［x］下決策τ（x）的條件風(fēng)險(xiǎn)率，因此總體風(fēng)險(xiǎn)其中的和是對整個(gè)知識表示系統(tǒng)而言。顯然，如果決策規(guī)則τ（x）使得對每個(gè)［x］而言條件風(fēng)險(xiǎn)率R（τ（x）｜［x］）盡可能的小，那么總體風(fēng)險(xiǎn)就能達(dá)到最小值。對于每個(gè)對象x∈U，計(jì)算由式（2）給出的風(fēng)險(xiǎn)R（τ（x）｜［x］），i＝1，2，…，m，如果有兩個(gè)或兩個(gè)以上的決策使條件風(fēng)險(xiǎn)達(dá)到最小則根據(jù)實(shí)際情況取其中之一。設(shè)U是一系列不良的網(wǎng)頁，設(shè)ω是某種不良類型的信息（如暴力、色情等），則ω把U 分成兩部分，含某種類型的不良網(wǎng)頁（記為ω）和不含此類型的網(wǎng)頁（記為～ω），記pos（ω）和neg（ω）為ω的正域（存在不良信息需要進(jìn)行過濾的網(wǎng)頁）和負(fù)域（存在不良信息不需要過濾的網(wǎng)頁）。

每一個(gè)網(wǎng)頁x在網(wǎng)頁特征現(xiàn)象［x］下面臨兩種可能的決策：

（Y）決策r1：x∈pos（ω），即r1＝［x］→pos（ω）；

（N）決策r2：x∈neg（ω），即r2＝［x］→neg（ω）。

這時(shí)，A＝｛r1，r2｝。令λ＝｛ri｜ω｝為含不良信息的網(wǎng)頁實(shí)際為不良頁面（對象實(shí)際屬于ω）而采取決策ri時(shí)的風(fēng)險(xiǎn)，λ＝｛ri｜～ω｝為含不良信息的網(wǎng)頁實(shí)際不為不良頁面而采取決策ri時(shí)的風(fēng)險(xiǎn)，p（ω｜［x］）為網(wǎng)頁在頁面特征現(xiàn)象［x］下有故障的概率，p（～ω｜［x］）為網(wǎng)頁在頁面特征現(xiàn)象［x］下沒有故障的概率。這樣，網(wǎng)頁在頁面特征現(xiàn)象［x］下采取決策ri的條件風(fēng)險(xiǎn)R（ri｜［x］）可由全概率公式得：

其中λi1＝λ（ri｜ω），λi2＝λ（ri｜～ω），i＝1，2。

由貝葉斯決策過程可得最小風(fēng)險(xiǎn)規(guī)則為：

（Y）r1：［x］→pos（ω），若

（N）r2：［x］→neg（ω），若

由于在實(shí)際情況中，對于存在不良信息的但還不能確定為哪類不良頁面的網(wǎng)頁來說，進(jìn)行網(wǎng)頁過濾的風(fēng)險(xiǎn)比不進(jìn)行頁面過濾處理的風(fēng)險(xiǎn)要?。欢鴮τ跊]有不良信息的網(wǎng)頁來說，進(jìn)行過濾的風(fēng)險(xiǎn)比不進(jìn)行過濾的風(fēng)險(xiǎn)要大，即滿足關(guān)系式：

將式（6）代入式（4）和式（5），并利用，p（ω｜［x］）＋p（～ω｜［x］）＝1經(jīng)計(jì)算可得最小風(fēng)險(xiǎn)決策規(guī)則重新表達(dá)為：

（Y）r1：［x］→pos（ω），若p（ω｜［x］）≥α，

（N）r2：［x］→neg（ω），若p（ω｜［x］）≤α，

其中

顯然，由式（6）可知0＜α＜1。這樣最終得到了概念ω關(guān)于α的近似（全體實(shí)際被過濾網(wǎng)頁）為：

即當(dāng)頁面特征現(xiàn)象表現(xiàn)為［x］的情況下，實(shí)際為某種不良網(wǎng)頁ω的概率大于和等于α的那些網(wǎng)頁肯定被過濾。

4 算法設(shè)計(jì)

4.1 風(fēng)險(xiǎn)系數(shù)

由于對網(wǎng)頁中不良頁面的確定并不一定通過存在不良信息的閾值百分之百的確定，所以算法在通過粗糙集確定不良類型頁面后，根據(jù)貝葉斯準(zhǔn)則，給予每種不良類型評定一個(gè)風(fēng)險(xiǎn)系數(shù)，用于進(jìn)一步進(jìn)行過濾決策，這樣可以提高網(wǎng)頁過濾的正確率和避免誤過濾而帶來的計(jì)算機(jī)開銷。

由第3節(jié)可知λ11＜λ21，且λ12＞λ22。對于網(wǎng)頁過濾來說，λ11＝λ22＝0表明不良網(wǎng)頁被正確過濾的風(fēng)險(xiǎn)為0。但是網(wǎng)頁被誤判時(shí)風(fēng)險(xiǎn)明顯提高，假設(shè)風(fēng)險(xiǎn)函數(shù)根據(jù)過濾網(wǎng)頁重要度成指數(shù)增長。網(wǎng)頁內(nèi)容越重要，錯誤過濾后的風(fēng)險(xiǎn)越大。把非不良頁面當(dāng)作不良網(wǎng)頁過濾的風(fēng)險(xiǎn)設(shè)為λ12＝eβ，其中β為頁面重要度，頁面重要度分為Ⅰ、Ⅱ、Ⅲ、Ⅳ四個(gè)等級，其中Ⅰ為重要度小的網(wǎng)頁（一般指普通的新聞、娛樂等網(wǎng)頁），Ⅱ?yàn)橹匾戎械鹊木W(wǎng)頁（一般指企業(yè)、公司、學(xué)校等網(wǎng)頁），Ⅲ為重要度較高的網(wǎng)頁（一般指涉及商業(yè)秘密、網(wǎng)絡(luò)交易等網(wǎng)頁），Ⅳ為重要度很高的網(wǎng)頁（一般指涉及國家機(jī)密、軍事機(jī)密等網(wǎng)頁）。重要度系數(shù)如表1所示。

表1 網(wǎng)頁重要度系數(shù)表

其中重要度系數(shù)在0≤β≤1，網(wǎng)頁為不良或存在不良信息時(shí)未被過濾而導(dǎo)致的風(fēng)險(xiǎn)為λ21＝eγ，其中γ為網(wǎng)頁的危害度。根據(jù)網(wǎng)頁的信息內(nèi)容，把頁面危害程度也分為Ⅰ、Ⅱ、Ⅲ、Ⅳ四個(gè)等級，危害程度為Ⅰ＜Ⅱ＜Ⅲ＜Ⅳ。網(wǎng)頁危害度系數(shù)如表2所示。

表2 網(wǎng)頁危害度系數(shù)表

由式（7）得到風(fēng)險(xiǎn)系數(shù)為

4.2 過濾算法

本文通過計(jì)算機(jī)和人工相結(jié)合地方式來提取網(wǎng)頁的特征信息，由于考慮到某些特征現(xiàn)象（如流媒體中裸露鏡頭的比例）機(jī)器很難進(jìn)行閾值判斷，是通過人工判斷來提取特征信息。例如，文本關(guān)鍵詞的閾值以及文本夾雜惡意字符等是采用TFIDF的方法進(jìn)行獲取特征現(xiàn)象。在獲取特征現(xiàn)象后，進(jìn)行網(wǎng)頁分類，根據(jù)粗糙集理論去除冗余的判別信息，只保留必要的特征信息；然后根據(jù)網(wǎng)頁的重要性和危害性進(jìn)行貝葉斯決策，從而達(dá)到利用最小的過濾代價(jià)來過濾最有危害性的不良網(wǎng)頁的目的。具體步驟如下：

Step1收集網(wǎng)頁特征信息，根據(jù)網(wǎng)頁特征信息進(jìn)行類別的初步分類，建立網(wǎng)頁類別樣本決策初表；

Step2根據(jù)粗糙集理論對網(wǎng)頁類別樣本決策初表建立相應(yīng)的區(qū)分矩陣CD，用式（1）對其進(jìn)行屬性約簡，選擇最優(yōu)的屬性組合，簡化網(wǎng)頁類別樣本決策初表，形成網(wǎng)頁類別決策復(fù)表；

Step3對于網(wǎng)頁特征信息不在類別決策復(fù)表中的根據(jù)收集的歷史特征信息以一定的先驗(yàn)概率確定為某種類別的網(wǎng)頁；

Step4對于網(wǎng)頁實(shí)時(shí)分類用網(wǎng)頁類別決策復(fù)表進(jìn)行決策，確定網(wǎng)頁為某種不良類別的后驗(yàn)概率為P（ω｜［x］）；

Step5由貝葉斯準(zhǔn)則，根據(jù)公式（9），確定過濾網(wǎng)頁的風(fēng)險(xiǎn)系數(shù)

Step6當(dāng)網(wǎng)頁為某種不良類別的后驗(yàn)概率為P（ω｜［x］）≥α?xí)r，確定為不良類別并進(jìn)行過濾，當(dāng)P（ω｜［x］）≤α?xí)r，定為非不良頁面并不予過濾，最后給出決策結(jié)果。

診斷算法流程圖如圖1所示。

圖1 診斷算法流程圖

5 算例與仿真結(jié)果

5.1 算法實(shí)例

假定在客戶端對網(wǎng)頁進(jìn)行過濾，由算法的Step1，建立表3和表4的網(wǎng)頁特征現(xiàn)象和網(wǎng)頁類別與相應(yīng)特征現(xiàn)象表。得到表5的網(wǎng)頁類別樣本決策初表。由算法Step2，建立區(qū)分矩陣CD，如式（10）所示，用粗糙集理論對CD進(jìn)行屬性約簡，得到表6的網(wǎng)頁類別決策復(fù)表，由算法Step3，得到網(wǎng)頁類別不確定表，如表7所示。由算法Step4～Step6，確定風(fēng)險(xiǎn)系數(shù)，由于考慮實(shí)際網(wǎng)頁為普通的不良頁面，根據(jù)表1和表2，風(fēng)險(xiǎn)系數(shù)中參數(shù)β定為Ⅰ級，γ定位Ⅲ級。所以0.425 6＝42.56%，風(fēng)險(xiǎn)系數(shù)概率超過α＝42.56%的都可以進(jìn)行網(wǎng)頁過濾，這樣可以最大程度的保護(hù)網(wǎng)頁的安全過濾。

表3 網(wǎng)頁特征現(xiàn)象與屬性值

表4 網(wǎng)頁類別及相應(yīng)特征現(xiàn)象

續(xù)表

表5 網(wǎng)頁類別樣本決策初表

表6 網(wǎng)頁類別決策復(fù)表

表7 網(wǎng)頁類別不確定表

表中D表示網(wǎng)頁類別的可能性，其分類概率為樣本訓(xùn)練后得到的先驗(yàn)概率。

5.2 仿真結(jié)果

對此算法實(shí)例進(jìn)行仿真，對仿真的417組不良網(wǎng)頁特征現(xiàn)象反饋數(shù)據(jù)進(jìn)行網(wǎng)頁分類，假設(shè)考慮環(huán)境人為影響和外界干擾，每組數(shù)據(jù)的可靠性為98.5%，網(wǎng)頁分類情況如圖2和表8所示。

圖2 不良網(wǎng)頁分類結(jié)果圖

表8 網(wǎng)頁分類結(jié)果表

圖中d1表示正常頁面，d2表示混合不良頁面，d3表示色情頁面，d4表示封建迷信頁面，d5表示宗教反動頁面。

從仿真結(jié)果來看，利用本算法進(jìn)行對不良網(wǎng)頁分類過濾效果明顯，并且能進(jìn)一步提高過濾正確率，在對傳統(tǒng)單用決策表進(jìn)行不良網(wǎng)頁分類過濾時(shí)，過濾正確率為88.6%（數(shù)據(jù)可靠性為98.5%）。與傳統(tǒng)單用決策表的方法相比，本論文采用的算法平均分類正確率為93.2%，過濾正確率92.2%，與傳統(tǒng)的算法相比有明顯提高。這是因?yàn)榫W(wǎng)頁分類過程實(shí)際上是一個(gè)搜索匹配過程。由于網(wǎng)頁的數(shù)據(jù)龐大，這使得傳統(tǒng)的搜索匹配過程冗余而效率低下。在本文所用的粗糙集理論對屬性進(jìn)行約簡后再次進(jìn)行匹配可以大大降低系統(tǒng)的冗余度，提高搜索匹配效率，也避免了大量冗余無用信息造成的誤過濾。而且對于模糊類別采用貝葉斯決策可以使得過濾風(fēng)險(xiǎn)性降為最小并得到最佳分類過濾。

6 結(jié)論

本文提出的基于粗糙集理論和貝葉斯決策的網(wǎng)頁過濾算法能夠快速準(zhǔn)確的解決不良網(wǎng)頁的分類和過濾決策。尤其在大量冗余信息和部分信息缺失的情況下，更能有效準(zhǔn)確的進(jìn)行網(wǎng)頁分類與過濾，提高了分類的效率和準(zhǔn)確率。并且本算法融入了貝葉斯決策理論，根據(jù)網(wǎng)頁重要度和危害度來定義風(fēng)險(xiǎn)函數(shù)，從而最小化了過濾頁面的風(fēng)險(xiǎn)性，達(dá)到不良頁面分類過濾的最優(yōu)化。

由于不良網(wǎng)頁獲取的困難性，本文只做了幾百組網(wǎng)頁的過濾實(shí)驗(yàn)，如果考慮到海量網(wǎng)頁的過濾，需要進(jìn)一步對網(wǎng)頁的特征提取方法進(jìn)行優(yōu)化，尤其是對于網(wǎng)頁中流媒體、視頻、圖片識別的快速判斷方法；另外還需要建立特征現(xiàn)象字典庫，并且進(jìn)行動態(tài)更新和添加以適應(yīng)不斷變化的互聯(lián)網(wǎng)信息。

［1］Denning P J.Electronic junk［J］.Communications of the ACM，1992，25（3）：163－165.

［2］Malone T，Grant K，Trubak F，et al.Intelligent information sharing system ［J］.Communication of the ACM，1987，5：390－402.

［3］Nanas N，Roeck A D，Vavalis M.What happened to content－based information filtering？［J］.ICTIR 2009，LNCS 5766，2009：249－256.

［4］張宇，劉挺，文勖.基于改進(jìn)貝葉斯模型的問題分類［J］.中文信息學(xué)報(bào)，2005，19（2）：100－105.

［5］Lee W，Lee S S，Chung S，et al.An harmful contents classification using the harmful word filtering and SVM［C］／／ICCS 2007，Part III，LNCS 4489：18－27.

［6］盧嬌麗，鄭家恒.基于粗糙集的文本分類方法研究［J］.中文信息學(xué)報(bào)，2005，19（2）：66－70.

［7］Malo P，Siitari P，Ahlgren O，et al.Semantic content filtering with wikipedia and ontologies ［C ］／／Proceedings of 2010IEEE International conference on data mining workshops，2010：518－526.

［8］Pang B.Lee L，Vaithyanathan S.Thumbs up？Sentiment classification using machine learning techniques［C］／／Proceedings of the Conference on Empirical Methods in Natural Language Processing，2002：79－86.

［9］張文修，吳偉志，等.粗糙集理論與方法［M］.科學(xué)出版社，2001.