垃圾郵件過濾的方法和系統的製作方法
2023-07-23 08:21:51
專利名稱：垃圾郵件過濾的方法和系統的製作方法
技術領域：
本發明涉及文本處理技術領域，尤其是一種垃圾郵件過濾的方法和系統。
背景技術：
當前，有很多技術可用於區分垃圾郵件。比如，白名單和黑名單過濾，這種方法簡單易行，但是需要實時更新白名單和黑名單，而且很難保證只有有限、固定的幾個用戶在發送垃圾郵件。比較常用的還有基於規則的過濾方法，即設置一些規則，只要符合這些規則的一條或幾條，就認為是垃圾郵件。這些規則通常有信頭分析、群發過濾、關鍵字匹配、郵件內容的其他特徵等。採用基於規則的過濾技術，確實能夠在一定時間內很好地防範了垃圾郵件。但其不足之處在於規則都是人工指定的，需要人們不斷去發現和總結、更新，人為因素比較多，一些沒有經驗的用戶可能很難提供有效的規則。而且，手工制定規則比較耗時，準確率也受到了限制。
發明內容
網際網路世界中垃圾郵件的泛濫，已經給人們帶來了極大的不便，並極大地消耗了網絡資源。因此，人們迫切需要一種能夠發現垃圾郵件的過濾方法，該方法必須滿足實時性，準確性，並且和語種無關。本發明的目的就是提供這樣一種能夠實時發現垃圾郵件的過濾方法。
將原始郵件庫中的垃圾郵件和合法郵件分別表示為通用後綴樹(GST)結構。對於新到達的郵件，通過每個文本位置的不定長統計，自動獲得其在垃圾郵件集和合法郵件集中的出現頻率，計算其與垃圾郵件集和合法郵件集的近似度，最終確定新到達郵件的屬性。此外，系統中的郵件庫修改裝置可以實時修改郵件庫中的郵件。
為了實現以上目的，本發明提供了一種垃圾郵件過濾的方法和系統，方法包括步驟參見圖5S1，對原始郵件庫進行轉換，表示為通用後綴樹結構的郵件庫；S2，對於新到達的郵件，對其在原始郵件庫中的出現頻率進行統計；S3，計算新到達的郵件與原始郵件庫的近似度，判斷其所屬類別；S4，將新到達的郵件加入到所屬類別；S5，將過時的郵件從原始語料庫中刪除。
垃圾郵件過濾的方法，對原始郵件庫進行轉換的步驟和將新到達的郵件加入到所屬類別的步驟包括構建通用後綴樹的步驟；在後綴樹節點上記錄統計信息的步驟；限定後綴樹深度的步驟。
統計新到達郵件在原始郵件庫中出現頻率的統計的步驟包括在每個郵件內容位置開始的不定長字串在通用後綴樹上進行匹配的步驟；計算新到達的郵件與原始郵件庫的近似度的步驟包括在對得到的出現頻率進行加權統計的步驟；將過時的郵件從原始語料庫中刪除的步驟包括刪除通用後綴樹的步驟；從通用後綴樹節點上刪除對應統計信息的步驟。
為了實現以上目的，本發明還提供了一種垃圾郵件過濾的系統，包括用於對原始郵件庫進行轉換，表示為通用後綴樹結構的郵件庫的裝置；用於對於新到達的郵件，對其在原始郵件庫中的出現頻率進行統計的裝置；用於計算新到達的郵件與原始郵件庫的近似度，判斷其所屬類別的裝置；用於將新到達的郵件加入到所屬類別的裝置；用於將過時的郵件從原始語料庫中刪除的裝置。
上述的垃圾郵件過濾的系統，用於對原始郵件庫進行轉換的裝置和用於將新到達的郵件加入到所屬類別的裝置包括構建通用後綴樹的裝置；在後綴樹節點上記錄統計信息的裝置；限定後綴樹深度的裝置。
用於統計新到達郵件在原始郵件庫中出現頻率的統計的裝置包括在每個郵件內容位置開始的不定長字串在通用後綴樹上進行匹配的裝置；用於計算新到達的郵件與原始郵件庫的近似度的裝置包括在對得到的出現頻率進行加權統計的裝置；用於將過時的郵件從原始語料庫中刪除的裝置包括刪除通用後綴樹的裝置；從通用後綴樹節點上刪除對應統計信息的裝置。
與本方法比較相關的是基於內容的郵件過濾方法，包括k近鄰、決策樹、貝葉斯分類器、支持向量機、Boosting方法、粗糙集(Rough Set)等。向量空間模型(VSM)的表示方法雖然便捷明了，但是它簡單地用特徵的出現頻率來表示文本，忽略了大量的其他信息，比如上下文信息。而且，特徵的提取需要綜合考慮訓練集中所有文檔，當一個文檔從訓練集中刪除或添加時，要進行所有文檔的重新訓練，這不符合垃圾郵件訓練集實時變動的要求。此外，採用了向量空間模型的文本表示，在訓練過程中，勢必要進行分詞或者使用N元語法。對於亞洲文字來說，詞和詞之間沒有特定的分隔符，分詞本身就是一個複雜繁瑣的過程。若使用N元語法，又需要考慮不同語種N取值的不同。
圖1是本發明的垃圾郵件過濾系統的基本原理圖。
圖2是本發明的通用後綴樹的實例圖。
圖3是本發明的通用後綴樹添加算法實例圖。
圖4是本發明的通用後綴樹刪除算法實例圖。
圖5是本發明的垃圾郵件過濾系統方法的流程圖。
具體實施例方式
如圖1所示，本發明的系統包括一個郵件內容表示裝置1，採用通用後綴樹模型(GSTM)的郵件內容表示方法，將原始郵件庫中的垃圾郵件和合法郵件分別表示成一棵通用後綴樹；一個頻率統計裝置2，採用不定長多元匹配的方法，得到新到達的郵件在原始郵件庫中的出現頻率；一個類別判斷裝置3，根據新到達郵件的出現頻率，採用加權統計的方法，計算郵件與不同類別原始郵件的近似度，最終判斷郵件所屬的類別；一個郵件庫修改裝置4，採用通用後綴樹模型的刪除、增加算法，對原始郵件庫進行修改。
頻率統計裝置2接收的新到達郵件，輸出連接於類別判斷裝置3，類別判斷裝置3輸出連接於郵件庫修改裝置4，郵件庫修改裝置4輸出連接於硬碟，硬碟的輸出連接於郵件內容表示裝置1，郵件內容表示裝置1連接於頻率統計裝置2。
各裝置的詳細操作將在下面分別詳細描述。
郵件內容表示裝置1的輸入為硬碟數據，將硬碟中的數據按類別表示成通用後綴樹，並將表示結果輸出到內存中。頻率統計裝置2輸入為在網關上接收的新到達郵件和內存中的通用後綴樹表示的訓練集，通過在後綴樹中的統計，將頻率統計結果輸出到內存中。類別判斷裝置3輸入為內存中的頻率統計結果，判斷郵件類別，並輸出判斷結果到顯示設備，並將判斷結果輸出到內存中。郵件庫修改裝置4輸入為內存中的郵件類別判斷結果，根據結果修改硬碟中的數據，最終輸出到硬碟中。顯示設備的輸入為類別判斷裝置3的判斷結果。硬碟輸出到郵件內容表示裝置1，輸入為郵件庫修改裝置的修改結果。
1 郵件內容表示裝置首先，描述如何根據本發明構建郵件內容對應通用後綴樹(GST)，即實現郵件內容表示裝置。
定義字符串S＝s1s2...si...sn，其中，si屬於給定的輸入字符集，那麼Si＝sisi+1...sn是S從位置i開始的後綴。一個有m個字符的串S，它的後綴樹是一棵有根的有向樹，共有m個葉子，分別標號為1到m。每一條邊都用S的非空子串來表示。從任一節點出來的兩條邊，它們必須以不同的字符開始。從根節點到葉子節點i，順序經過的樹邊的串聯，恰好為S從i位置開始的後綴，即Si。此外，為保證所有的後綴都結束在葉子節點，在字符串末尾添加不屬於輸入字符集的字符$。關於後綴樹的構建在由E.Ukkonen在algorithmica第249到260頁的論文On-lineconstruction of suffix trees中有詳細描述，這裡就不再詳述。
後綴樹的原理可以擴展擴展到多於一個輸入串，該擴展被稱為通用後綴串(GST)。
圖2中給出了字符串「abab$」和「bac$」的通用後綴樹例子。從GST的結構中，可以得到GST的每個節點的信息，包括
當前節點i(例如節點5){路徑(將所有被標誌的邊沿從根到節點i的路徑串聯起來)；(節點5的路徑是「ab」)路徑計數(路徑在原始郵件集中的出現頻率)；(「ab」在「abab$」和「bac$」中出現了兩次)子節點 節點j，...，節點k；(節點9和節點10)父節點 節點f；(節點1)}為了記錄字串在原始郵件庫中的出現頻率，改進了後綴樹算法。其基本思路為每當添加新的節點或直到葉子節點都能匹配時，在該節點的所有祖先節點的計數上加1。
圖中節點中的數字表示「節點號/頻率計數」。
如圖3所示，在表示「abab$」的樹上添加「bac$」的第一個後綴「bac$」，從根節點開始，只成功匹配上「ba」，於是添加表示「c$」的葉子節點，然後為該葉子節點的所有祖先節點計數加1。
為了找到該節點的所有祖先節點，需要上溯的次數為節點深度，那麼，改進後的算法時間複雜度為O(nlogn)，其中，logn表示樹的深度。在具體實現中，限制樹的最大深度。例如，限制樹的深度為K，當需要在深度為K的節點i上添加子節點j時，將該j的信息統一到i，從而使得logn成為一個常數K，即算法的時間複雜度為O(Kn)。
2 頻率統計裝置其次，描述如何根據本發明對新到達的郵件進行頻率統計，即實現頻率統計裝置。
本方法採用針對給定郵件的不定長統計，即字串的長度由新到達郵件自身決定。郵件內容表示裝置已經將原始郵件集根據垃圾郵件或合法郵件表示為GST1和GST2。令新到達郵件為d，對於郵件內容的任意位置k，在GST1和GST2上分別查找從k開始的字串直到無法匹配或者到達葉子節點。設匹配得到的字串長度為N，本方法要求同時得到1元到N元子串在在GST1和GST2中的出現頻率。
例如abba......
1元漢字串a；......
3元漢字串abb；......
然後，將出現頻率記錄在ac[1]，ac[2]，...，ac[N]中。再利用公式tf(k,Dj)=u=1Nacu*up]]>得到位置k的對應值。為了公式的統一起見，取N為足夠大，那麼當匹配成功的字串長度小於N的時候，ac[u]＝0，不影響最終的結果。p是字符串長度權重因子，為了強調相匹配字符串長度越大，郵件內容之間的相似度越高，一般取p大於1。通過上述步驟，GSTi就轉換為長度為(L-N+1)的詞頻數組了。
在實現上，由於GST特有的數據結構，保證了能夠在O(N)時間內，完成對長度為N的字串的匹配。同時，我們已經將出現頻率記錄在葉子節點上，所以在匹配的過程中就能夠得到1元到N元字串的出現頻率。如圖2所示，可以在表示字串「abab$」和「bac$」的後綴樹上，直接查找字串「bac」的出現頻率。設字串「abab$」和「bac$」所在的訓練集為D，從而得到tf(0，D)＝3×1p+2×2p+1×3p，tf(1，D)＝3×1p+1×2p，tf(2，D)＝1×1p。其中，0、1、2分別表示從字符串的「bac」的0、1、2位置開始統計。
3 類別判斷裝置再次，描述如何根據本發明計算新到達的郵件與原始郵件庫的近似度，判斷其所屬類別，即實現類別判斷裝置。
得到了郵件集Di的絕對詞頻[tf(0，Di)tf(1，Di)......tf(L-1，Di)]之後，給每個項賦權重時，應使得郵件內容中越重要的項權重越大。所以採用改進的tf-idf公式計算權重，即TFC權重，公式如下W(k，Di)＝tf((k，Di)×logp(M/mj+0.01)
w(k，Di)為位置k開始的多元組在郵件集Di中的權重，其中tf(k，Di)為頻率統計裝置中求得的位置k開始的多元組在郵件集Di中出現的頻率，M為郵件集的個數，mk為出現該多元組的郵件集個數。
新到達郵件d和郵件集Di之間的(內容)相關程度用它們之間的相似度Sim(D1，D2)來度量。當郵件被表示為相對詞頻的數組時，就可以藉助相對詞頻的累計值來表示相似度Sim=(d,Di)=j=0L-N+1W(k,Di)]]>本方法的屬性判斷就是比較新到達郵件和兩個郵件集近似度的大小。設垃圾郵件郵件集D1中郵件內容總長度為Z1，合法郵件郵件集D2中郵件內容總長度為Z2，默認情況下，每個郵件內容與新到達郵件匹配的可能性相同，那麼郵件數的多少和近似度成正比關係，所以決策規則是sim(d,D1)Z1>sim(d,D2)Z2dD1;]]>sim(d,D1)Z1sim(d,D2)Z2dD2;]]> 4 郵件庫修改裝置再次，描述如何根據本發明將新到達的郵件加入到所屬類別，或者將過時的郵件從原始語料庫中刪除，即實現郵件庫修改裝置。
當新的郵件根據分類算法被加入到某一類後，可以直接對下一輪的分類產生影響。在下一個郵件到來之前，只需要對將該郵件加入到所屬類的GST中，即可加入下一輪的數值化和分類過程。
在實現上，由於GST結構滿足動態增長，只需要在原有的樹結構添加相關信息，其算法複雜度與建樹算法相同，若新加入的郵件長度為N，那麼修改訓練集的算法複雜度為O(N)。
同時，考慮到用戶可能刪除郵件集中的郵件，所以需要GST刪除算法的支持。由於在後綴樹記錄了字串出現的頻率，本方法改進了原有的GST刪除算法。設從訓練集中刪除的某個郵件內容為Si，算法基本思路為從後綴樹根節點開始，依次匹配Si中的每個字符直到葉子節點。如果該葉子節點的計數值大於1，計數值減1即可。如果葉子節點的計數值為1，刪除該節點，若刪除操作導致其上層節點只有一個孩子，那麼將上層節點與另一個孩子節點合併。然後，對原葉子節點的所有祖先節點計數值減1。這樣，就完成了Si的一個後綴串的刪除。為了刪除Si的其他後綴，要通過後綴鏈進行查找，並進行類似刪除操作，直到Si的所有後綴都被刪除。圖中節點中的數字表示「節點號/頻率計數」。
如圖4所示，在表示「abab$」和「bac$」的樹上刪除「abab$」的第一個後綴「abab$」。由於葉子節點計數為1，刪除該節點，合併其父節點與另一個孩子節點。
由於處理每個葉子節點時，需要上溯到根節點。所以刪除算法的時間複雜度為O(nlogn)，在具體實現時，採用限制後綴樹深度為K的方法，使得時間複雜度為O(Kn)。圖中節點中的數字表示「節點號/頻率計數」。
積極效果採用以上的處理，我們可以對垃圾郵件進行實時過濾。其在文本表示上，採用了通用後綴樹模型(GSTM)；在統計上，使用了不定長多元統計的方法；在實現上，利用了後綴樹的數據結構和改進的通用後綴樹算法。由於通用後綴樹的添加算法具有線性特性，所以能夠滿足垃圾郵件訓練集的變動性；由於後綴樹匹配本身具有線性特性，而且改進後的樹節點上記錄了字串的出現頻率，所以能夠在線性時間內計算郵件與不同訓練集的近似度，從而滿足了垃圾郵件過濾的實時性特點；由於該方法保留了文本的上下文位置信息，相對於基於向量空間模型的其他方法，信息量更大，所以能夠得到較好的準確率；由於不需要基於具體語種的分詞過程，所以該方法獨立於語種。
權利要求
1.一種垃圾郵件過濾的方法，包括步驟S1，對原始郵件庫進行轉換，表示為通用後綴樹結構的郵件庫；S2，對於新到達的郵件，對其在原始郵件庫中的出現頻率進行統計；S3，計算新到達的郵件與原始郵件庫的近似度，判斷其所屬類別；S4，將新到達的郵件加入到所屬類別；S5，將過時的郵件從原始語料庫中刪除。
2.根據權利要求1的方法，其特徵在於對原始郵件庫進行轉換的步驟和將新到達的郵件加入到所屬類別的步驟包括構建通用後綴樹的步驟；在後綴樹節點上記錄統計信息的步驟；限定後綴樹深度的步驟。
3.根據權利要求1的方法，其特徵在於統計新到達郵件在原始郵件庫中出現頻率的統計的步驟包括在每個郵件內容位置開始的不定長字串在通用後綴樹上進行匹配的步驟；
4.根據權利要求1的方法，其特徵在於計算新到達的郵件與原始郵件庫的近似度的步驟包括在對得到的出現頻率進行加權統計的步驟；
5.根據權利要求1的方法，其特徵在於將過時的郵件從原始語料庫中刪除的步驟包括刪除通用後綴樹的步驟；從通用後綴樹節點上刪除對應統計信息的步驟。
6.一種垃圾郵件過濾的系統，包括用於對原始郵件庫進行轉換，表示為通用後綴樹結構的郵件庫的裝置；用於對於新到達的郵件，對其在原始郵件庫中的出現頻率進行統計的裝置；用於計算新到達的郵件與原始郵件庫的近似度，判斷其所屬類別的裝置；用於將新到達的郵件加入到所屬類別的裝置；用於將過時的郵件從原始語料庫中刪除的裝置。
7.根據權利要求6的系統，其特徵在於用於對原始郵件庫進行轉換的裝置和用於將新到達的郵件加入到所屬類別的裝置包括構建通用後綴樹的裝置；在後綴樹節點上記錄統計信息的裝置；限定後綴樹深度的裝置。
8.根據權利要求6的系統，其特徵在於用於統計新到達郵件在原始郵件庫中出現頻率的統計的裝置包括在每個郵件內容位置開始的不定長字串在通用後綴樹上進行匹配的裝置；
9.根據權利要求6的系統，其特徵在於用於計算新到達的郵件與原始郵件庫的近似度的裝置包括在對得到的出現頻率進行加權統計的裝置；
10.根據權利要求6的系統，其特徵在於用於將過時的郵件從原始語料庫中刪除的裝置包括刪除通用後綴樹的裝置；從通用後綴樹節點上刪除對應統計信息的裝置。
11.根據權利要求6-10的系統，其特徵在於，所述的系統包括郵件內容表示裝置1，採用通用後綴樹模型的郵件內容表示方法，將原始郵件庫中的垃圾郵件和合法郵件分別表示成一棵通用後綴樹；頻率統計裝置2，採用不定長多元匹配的方法，得到新到達的郵件在原始郵件庫中的出現頻率；類別判斷裝置3，根據新到達郵件的出現頻率，採用加權統計的方法，計算郵件與不同類別原始郵件的近似度，最終判斷郵件所屬的類別；郵件庫修改裝置4，採用通用後綴樹模型的刪除、增加算法，對原始郵件庫進行修改；頻率統計裝置2接收的新到達郵件，輸出連接於類別判斷裝置3，類別判斷裝置3輸出連接於郵件庫修改裝置4，郵件庫修改裝置4輸出連接於硬碟，硬碟的輸出連接於郵件內容表示裝置1，郵件內容表示裝置1連接於頻率統計裝置2。
12.根據權利要求1-5的垃圾郵件過濾的方法，其特徵在於，郵件內容表示裝置1的輸入為硬碟數據，將硬碟中的數據按類別表示成通用後綴樹，並將表示結果輸出到內存中；頻率統計裝置2輸入為在網關上接收的新到達郵件和內存中的通用後綴樹表示的訓練集，通過在後綴樹中的統計，將頻率統計結果輸出到內存中；類別判斷裝置3輸入為內存中的頻率統計結果，判斷郵件類別，並輸出判斷結果到顯示設備，並將判斷結果輸出到內存中；郵件庫修改裝置4輸入為內存中的郵件類別判斷結果，根據結果修改硬碟中的數據，最終輸出到硬碟中；顯示設備的輸入為類別判斷裝置3的判斷結果；硬碟輸出到郵件內容表示裝置1，輸入為郵件庫修改裝置的修改結果。
全文摘要
本發明涉及文本處理技術領域，尤其是一種垃圾郵件過濾的方法和系統。方法包括對原始郵件庫進行轉換；對於新到達的郵件進行統計；計算新到達的郵件與原始郵件庫的近似度，判斷其所屬類別；將新到達的郵件加入到所屬類別；將過時的郵件從原始語料庫中刪除。裝置包括用於對原始郵件庫進行轉換的裝置；用於對於新到達的郵件進行統計的裝置；用於計算新到達的郵件與原始郵件庫的近似度的裝置；用於將新到達的郵件加入到所屬類別的裝置；用於將過時的郵件從原始語料庫中刪除的裝置。此外，系統中的郵件庫修改裝置可以實時修改郵件庫中的郵件。
文檔編號G06F17/30GK1614607SQ20041000985
公開日2005年5月11日 申請日期2004年11月25日 優先權日2004年11月25日
發明者譚建龍, 張吉, 郭莉 申請人:中國科學院計算技術研究所