垃圾郵件過濾之初步研究 邱炫盛 2019/1/15

大綱 垃圾郵件過濾簡介 過濾模型介紹 實驗 結論與未來展望 規則導向過濾 機械學習導向過濾 貝氏分類器 潛藏語意分析 隱藏式馬可夫模型 2019/1/15 Speech Lab. NTNU

垃圾郵件過濾簡介：規則導向過濾 規則導向過濾： 可能遇到的問題： 亦可以自動學習規則： 事先定義好關鍵字，如果新郵件有部分符合，則認定為垃圾郵件 可能遇到的問題： 人工定義費時費力 中文斷詞問題 關鍵字定義是否明確 亦可以自動學習規則： RIPPER演算法 2019/1/15 Speech Lab. NTNU

垃圾郵件過濾簡介：機械學習導向過濾 郵件過濾模型： 本論文著重於此類型過濾 貝氏分類器（Bayesian Classifier) 潛藏語意分析(Latent Semantic Analysis, LSA) 隱藏式馬可夫模型(Hidden Markov Model, HMM) 本論文著重於此類型過濾 提出隱藏式馬可夫模型，並與其他模型作比較效果 2019/1/15 Speech Lab. NTNU

貝氏分類器 貝氏分類器從貝氏網路簡化而來 rooF: a new binary variable concerning cat making noise on the roof. CPT: Conditional Probability Table 2019/1/15 Speech Lab. NTNU

貝氏分類器 2019/1/15 Speech Lab. NTNU

貝氏分類器 2019/1/15 Speech Lab. NTNU

貝氏分類器 w2 C w1 w3 wn w2 C w1 w3 wn … … 簡單貝式分類器 複雜貝式分類器 2019/1/15 Speech Lab. NTNU

貝氏分類器 求取新郵件d屬於某類別Ck的機率： 求 與 求 可分成多變量伯努利事件與多項式事件模型 2019/1/15 求　　　　與 求 可分成多變量伯努利事件與多項式事件模型 2019/1/15 Speech Lab. NTNU

貝氏分類器：多變量伯努利模型 多變量伯努利模型： 給定類別Ck產生郵件d的機率： 給定類別產生詞wt的機率： 假設郵件d是由連續|V|次的伯努利試驗所產生 郵件d是|V|維的向量，每個維度t，其值Id,t為0或1 給定類別Ck產生郵件d的機率： 給定類別產生詞wt的機率： I(wt,di)表示某一個詞wt是否出現在郵件郵件di 2019/1/15 Speech Lab. NTNU

貝氏分類器：多項式模型 多項式模型： 給定類別Ck產生郵件d的機率： 給定類別產生詞wt的機率： 假設郵件d由一連串詞w組成，為多項式分布，詞w來自詞典V 郵件d是|V|維的向量，每個維度t，其值nd,t為詞出現次數 給定類別Ck產生郵件d的機率： 給定類別產生詞wt的機率： 2019/1/15 Speech Lab. NTNU

貝氏分類器 求給定郵件d屬於哪一類Ck的機率較大的類別 2019/1/15 Speech Lab. NTNU

潛藏語意分析 潛藏語意分析： 根據潛藏在文字中的語意來作郵件過濾 三步驟：建立特徵矩陣、奇異值分解運算(SVD)與產生語意指標(Semantic Anchor)及文件分類 2019/1/15 Speech Lab. NTNU

潛藏語意分析：第一步 建立特徵矩陣M 正規化熵值： 矩陣M，第一行向量為合法郵件向量，第二行是垃圾郵件向量，每一列表示某一個詞wt 第t列第k行，其值 正規化熵值： 使出現相同次數的詞wt有不同的權重 2019/1/15 Speech Lab. NTNU

潛藏語意分析：第二步 奇異值分解(SVD) 產生三個矩陣：U、S、V 產生了兩個語意上的映射：合法郵件映射與垃圾郵件映射， 表示合法郵件， 表示垃圾郵件。 2019/1/15 Speech Lab. NTNU

潛藏語意分析：第三步 郵件過濾： 測量方式 新郵件d也轉換成向量 ，與建矩陣方式相同。 郵件d投影到潛藏語意空間S 餘弦測量 2019/1/15 Speech Lab. NTNU

隱藏式馬可夫模型 隱藏式馬可夫模型假設類別中有屬於該類的生成模型 訓練三個語言模型 以詞為特徵：語言模型 合法郵件模型、垃圾郵件模型、通用郵件模型 使用SRILM toolkit 三種型態：單連、二連模型 2019/1/15 Speech Lab. NTNU

隱藏式馬可夫模型 型I： 型II： 型III： 2019/1/15 Speech Lab. NTNU

實驗 實驗語料： 表 1 Ling-Spam郵件語料資料表 表 2 中文訓練郵件語料資料表 表 3 中文測試郵件語料資料表 類別 合法郵件 垃圾郵件 數量 2412 481 總詞數 1,531,209 439,040 平均長度 634.83 912.77 收錄時期 ~July 17, 2000 表 2 中文訓練郵件語料資料表 表 3 中文測試郵件語料資料表 類別 合法郵件 垃圾郵件 數量 1188 430 總詞數 157,861 74,197 平均長度 132.88 172.55 收錄時期 ~March 2005 ~June 2005 類別 合法郵件 垃圾郵件 數量 171 83 總詞數 11,844 5,174 平均長度 69.26 62.34 收錄時期 April 2005 July 2005 2019/1/15 Speech Lab. NTNU

實驗 特徵選取： 交互資訊： 多變量伯努利模型： 多項式模型： 透過交互資訊(Mutual Information)選出部份詞當新的特徵 　　　　：訓練語料中某類別中包含詞的郵件數除以所有類別郵件總數 　　　：某一類別的郵件數除以所有類別的郵件總數 　　　：所有類別中包含詞的郵件數除以所有類別的郵件總數。 多項式模型： 　　　　：訓練語料中某類別中詞的詞頻數數除以兩類別總詞數 　　　：某一類別的總詞數除以所有類別總詞數 　　　：所有類別中詞頻數除以有類別總詞數 2019/1/15 Speech Lab. NTNU

實驗 實驗一：特徵數量與正確率的關係 正相關 2019/1/15 Speech Lab. NTNU

表 4 LSA維度與正確率實驗結果(使用Ling-Spam語料) 實驗二：潛藏語意分析維度與正確率的關係 表 4 LSA維度與正確率實驗結果(使用Ling-Spam語料) 合法郵件正確率(%) 垃圾郵件正確率(%) 整體正確率(%) d=2604, r=25 85.49 66.34 82.31 d=2604, r=100 85.66 68.42 82.79 d=2604, r=250 85.74 82.86 d=2604, r=500 85.78 82.89 d=2, r=2 94.36 91.07 93.81 d表示訓練郵件總數，r表示SVD的維度 2019/1/15 Speech Lab. NTNU

表 5 隱藏式馬可夫模型各類型比較(使用Ling-Spam語料) 實驗 實驗三：隱藏式馬可夫模型三種型式與正確率的關係 表 5 隱藏式馬可夫模型各類型比較(使用Ling-Spam語料) 合法郵件正確率(%) 垃圾郵件正確率(%) 整體正確率(%) 型I 99.42 96.68 98.96 型II 99.96 97.30 99.52 型III 98.34 99.69 2019/1/15 Speech Lab. NTNU

表 6 各種模型正確率(使用Ling-Spam語料) 實驗 實驗結果： 表 6 各種模型正確率(使用Ling-Spam語料) 合法郵件正確率(%) 垃圾郵件正確率(%) 整體正確率(%) MVB 99.50 64.67 93.71 MN 99.42 97.73 99.14 LSA 94.36 91.07 93.81 HMM 99.96 98.34 99.69 2019/1/15 Speech Lab. NTNU

實驗 實驗結果： 表7 各種模型正確率(使用中文語料) 合法郵件正確率(%) 垃圾郵件正確率(%) 整體正確率(%) MVB 99.42 49.40 86.12 MN 98.25 60.02 88.15 LSA 67.47 90.93 HMM 74.70 91.99 2019/1/15 Speech Lab. NTNU

結論與未來展望 找強建性特徵的方法 建立模型的方法 語音辨識與文件分類技術結合應用 PLSA TMM ME 2019/1/15 Speech Lab. NTNU