贝叶斯公式是在1763年提出来的：
假定B1,B2,……是某个过程的若干可能的前提，则P(Bi)是人们事先对各前提条件出现可能性大小的估计，称之为验前概率.如果这个过程得到了一个结果A，那么贝叶斯公式提供了我们根据A的出现而对前提条件做出新评价的方法.P(Bi∣A)既是对前提Bi的出现概率的重新认识，称 P(Bi∣A)为验后概率.经过多年的发展与完善，贝叶斯公式以及由此发展起来的一整套理论与方法，已经成为概率统计中的一个冠以“贝叶斯”名字的学派，在自然科学及国民经济的许多领域中有着广泛应用.
一． 贝叶斯过滤算法的基本步骤
1) 收集大量的垃圾邮件和非垃圾邮件，建立垃圾邮件集和非垃圾邮件集。
2) 提取邮件主题和邮件体中的独立字串例如 ABC32，￥234等作为TOKEN串并统计提取出的TOKEN串出现的次数即字频。按照上述的方法分别处理垃圾邮件集和非垃圾邮件集中的所有邮件。
3) 每一个邮件集对应一个哈希表，hashtable_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。
4) 计算每个哈希表中TOKEN串出现的概率P=（某TOKEN串的字频）/（对应哈希表的长度），替换存储哈希表的映射关系，概率P替换字频，TOKEN串到概率P的映射关系。
5) 综合考虑hashtable_good和hashtable_bad，推断出当新来的邮件中出现某个TOKEN串时，该新邮件为垃圾邮件的概率。数学表达式为：
A事件----邮件为垃圾邮件;
t1,t2 …….tn代表TOKEN串
则P（A|ti）表示在邮件中出现TOKEN串ti时，该邮件为垃圾邮件的概率。
设
P1（ti）=（ti在hashtable_good中的值）
P2（ti）=（ti在hashtable_ bad中的值）
则 P（A|ti）= P1（ti）/[（P1（ti）+ P2（ti）]；
/*
假设有三个哈希表hashtable_good、hashtable_ bad和hashtable_ unkown
设
P1（ti）=（ti在hashtable_good中的值）
P2（ti）=（ti在hashtable_ bad中的值）
P3（ti）=（ti在hashtable_unkown中的值）
则 P（A|ti）= P1（ti）/[（P1（ti）+ P2（ti）+ P3（ti）]；
四、五..个哈希表类似
*/
6) 建立新的哈希表 hashtable_probability存储TOKEN串ti到P（A|ti）的映射
7) 至此，垃圾邮件集和非垃圾邮件集的学习过程结束。根据建立的哈希表 hashtable_probability可以估计一封新到的邮件为垃圾邮件的可能性。
当新到一封邮件时，按照步骤2）生成TOKEN串。查询hashtable_probability得到该TOKEN 串的键值。
假设由该邮件共得到N个TOKEN串，t1,t2…….tn, hashtable_probability中对应的值为P1，P2，。。。。。。PN，
P(A|t1 ,t2, t3……tn)表示在邮件中同时出现多个TOKEN串t1,t2…….tn时，该邮件为垃圾邮件的概率。
由复合概率公式可得
P(A|t1 ,t2, t3……tn)=（P1*P2*。。。。PN）/[P1*P2*。。。。。PN+（1-P1）*（1-P2）*。。。（1-PN）]
当P(A|t1 ,t2, t3……tn)超过预定阈值时，就可以判断邮件为垃圾邮件。
二． 贝叶斯过滤算法举例
例如：一封含有“法学家”字样的垃圾邮件 A
和 一封含有“法律”字样的非垃圾邮件B
根据邮件A生成hashtable_ bad，该哈希表中的记录为
法：1次
学：1次
家：1次
计算得在本表中：
法出现的概率为0。3
学出现的概率为0。3
家出现的概率为0。3
根据邮件B生成hashtable_good，该哈希表中的记录为：
法：1
律：1
计算得在本表中：
法出现的概率为0。5
律出现的概率为0。5
综合考虑两个哈希表，共有四个TOKEN串： 法 学 家 律
当邮件中出现“法”时，该邮件为垃圾邮件的概率为：
P=0。3/（0。3+0。5）=0。375
出现“学”时：
P=0。3/（0。3+0）=1
出现“家“时：
P=0。3/（0。3+0）=1
出现“律”时
P=0/（0+0。5）=0；
由此可得第三个哈希表：hashtable_probability 其数据为：
法：0。375
学：1
家：1
律：0
当新到一封含有“功律”的邮件时，我们可得到两个TOKEN串，功 律
查询哈希表hashtable_probability可得
P（垃圾邮件| 功）=1
P （垃圾邮件|律）=0
此时该邮件为垃圾邮件的可能性为：
P=（0*1）/[0*1+（1-0）*（1-1）]=0
由此可推出该邮件为非垃圾邮件
![]()
Java 代码：
|
/* Description：贝叶斯算法判断垃圾邮件
* * author:Tony
* * date: 2007/10/23
*/
import org.apache.lucene.analysis.Token;
import org.apache.lucene.analysis.cn.*;
import java.util.*;
import java.io.*;
public class Bayes
{
private Hashtable badHash;
private Hashtable goodHash;
private Hashtable probabilityHash;
//初始化
public void init()throws Exception
{
badHash = new Hashtable();
goodHash = new Hashtable();
buildEmailHash("D:\\JavaWorkSpace\\Bayes\\src\\data\\badEmail",badHash);
buildEmailHash("D:\\JavaWorkSpace\\Bayes\\src\\data\\goodEmail",goodHash);
buildNewHashTable();
}
//创建垃圾邮件哈希表
public void buildEmailHash(String path, Hashtable table) throws Exception
{
String badInput = readFile(path);
ChineseTokenizer tokenizer = new ChineseTokenizer(
new StringReader(badInput));
Token token;
Hashtable tempHash = new Hashtable();
double rate = 0.0;
int total = 0;
while ((token = tokenizer.next()) != null)
{
total++;
String temp = token.termText();
if(table.containsKey(temp))
{
int counter = (Integer)tempHash.get(temp);
counter++;
tempHash.remove(temp);
tempHash.put(temp, counter);
}
else
{
tempHash.put(temp, 1);
}
}
//将垃圾邮件中字符及其概率放入badhash中
for(Iterator it = tempHash.keySet().iterator(); it.hasNext();)
{
String key = (String)it.next();
rate = (Integer)tempHash.get(key)/total;
table.put(key, rate);
}
}
/*创建新的probability Hash表，其中的概率表示
在邮件中出现 TOKEN 串 ti 时，该邮件为垃圾邮件的概率
*/
public void buildNewHashTable()
{
for(Iterator it = badHash.keySet().iterator(); it.hasNext();)
{
String key = (String)it.next();
// P （ A|ti ） =P2 （ ti ） /[ （ P1 （ ti ） +P2 （ ti ） ]
double badRate = (Double)badHash.get(key);
double allRate = badRate;
if(goodHash.containsKey(key))
{
allRate += (Double)goodHash.get(key);
}
probabilityHash.put(key, (badRate/allRate));
}
}
//读文件
public String readFile(String path)throws Exception
{
BufferedReader br = new BufferedReader(
new FileReader(path));
String str = "";
while(true)
{
if(br.readLine() == null) break;
str += br.readLine();
}
br.close();
return str;
}
//判断是否为垃圾邮件 返回true表示非垃圾邮件 返回false表示是垃圾邮件
public boolean judgeEmail(String email, double weight) throws Exception
{
//P(A|t1 ,t2, t3……tn)=（P1*P2*……PN）/[P1*P2*……PN+（1-P1）*（1-P2）*……（1-PN）]
ChineseTokenizer tokenizer = new ChineseTokenizer(
new StringReader(email));
Token token;
boolean flag = true;
double rate = 1.0;
double tempRate = 1.0;
double finalRate = 0.0;
while ((token = tokenizer.next()) != null)
{
String key = token.termText();
if(!probabilityHash.containsKey(key))
{
break;
}
else
{
double temp = (Double)probabilityHash.get(key);
tempRate *= 1 - temp;
rate *= temp;
}
}
finalRate = rate/(rate + tempRate);
if(finalRate > weight) flag = false;
return flag;
}
public static void main(String args[]) throws Exception
{
Bayes bayes = new Bayes();
bayes.init();
String email ="";
double weight = 0.5;
if(bayes.judgeEmail(email, weight))
{
System.out.println("It is OK!");
}
else
{
System.out.println("It is wrong!");
}
}
}
|
阅读(1141) | 评论(0) | 转发(0) |
