【商务智能】数据挖掘-分类算法:贝叶斯算法

一.前言

贝叶斯算法属于数据挖掘中的分类算法,对于分类和聚类的概念介绍可见之前的一篇文章:【商务智能】浅谈数据挖掘分类和聚类算法

本文将讲解和实现一个数据通用的贝叶斯算法程序。

二.算法讲解

转载请注明出处:http://jasonhan.me/blog/?p=179

在概率论中,有一个基本公式叫贝叶斯公式,用于计算条件概率:

images

其中P(x | y)表示在事件y发生的情况下事件x发生的概率。

贝叶斯分类算法就是利用这个公式来计算新数据属于某一个类别的概率。

理论描述比较晦涩,我们直接通过一个简单案例来讲解。

下面是关于不同性别的人的身高表,

Name Gender Height Class
Kristina F 1.6m Short
Jim M 2m Tall
Maggie F 1.9m Medium
Martha F 1.88m Medium
Stephanie F 1.7m Short
Bob M 1.85m Medium
Kathy F 1.6m Short
Dave M 1.7m Short
Worth M 2.2m Tall
Steven M 2.1m Tall
Debbie F 1.8m Medium
Todd M 1.95m Medium
Kim F 1.9m Medium
Amy F 1.8m Medium
Wynette F 1.75m Medium

我们把图中的每一列的名字叫做属性。Name属性我们可以不看,因为它只是起到一个标识作用,对数据没有影响。我们的目的在于通过这些数据来判断一个人是属于Short或Medium或Tall,即:给定一个人的Gender和Height,我们要预测这个人的Class。我们把我们需要预测的那个属性(这里是Class)叫做目标属性。

比如,我们现在要预测t=<Adam, 男,1.95>属于哪一个Class。

为了方便,我们先把身高做一个划分,把身高分为(0,1.6], (1.6,1.7], (1.7,1.8], (1.8,1.9],(1.9,2.0],(2.0,…] 总共6个区间。

ok,需要预测t=<Adam, 男,1.95>属于Short还是Medium还是Tall,就相当于我们要计算:

P(矮 | t)=?       P(中 | t)=?        P(高 | t)=?

根据上面列出的第二个公式,P(矮 | t)=P(t | 矮)*P(矮)/P(t)。以P(矮 | t)为例:

  • P(矮)=4/15.
  • P(t | 矮)即表示当一个人为矮时,他的数据是“男,1.95”的概率,所以就等于P(男矮)*P(1.95矮)。从数据中可以看到,矮的有4个,其中男的有1个,那么P(男矮)=1/4,而矮的里面身高为1.95的没有一个,即P(1.95矮)=0。所以P(t | 矮)=P(男矮)*P(1.95矮)=(1/4)*0=0
  • 同上可算出P(t | 中)和P(t | 高).
  • 由上面列出的两个公式中的第一个,可以得出P(t)=P(t | 矮)*P(矮)+P(t | 中)*P(中)+P(t | 高)*P(高)
  • 至此,我们已经算出了P(矮)、P(t | 矮)、P(t),由上面的P(矮 | t)=P(t | 矮)*P(矮)/P(t)即可算出P(矮 | t).

三.算法实现

下面使用java来实现上述 算法。

我们先看对于上述案例的一张表:

probtable

从图中可以看出,我们需要计算很多个概率,那我们需要给定数据集后就把各个概率算出来形成一个数据表吗?虽然是可以这样,但是如果过了几天又有新的一大堆数据来给系统学习,那这种方式就导致系统的可扩展性大大降低了。我们可以不去生成一个概率表,而是生成一个计数表(见上图中的中间的计数表),这样,每来一条数据,我们就去更新相应的计数,需要计算概率的时候我们就以各个计数去算。

当然,话说回来,相对于某些的应用情况可能这种方式不是很好,但我们考虑可扩展性和通用性,暂且以这种方式去实现。

总而言之,下面实现一个通用的贝叶斯分类算法,系统维护张计数表,随着每加进来一条数据进行动态增长。

先实现一个数据集类DataSet:

 

import java.util.ArrayList;

/**
 * 数据集,里面有属性集
 * 同时数据集维护一个目标属性的计数表
 * 而非目标属性的计数表交由各个属性去自己处理
 * @author Jason Han
 *
 */
public class DataSet 
{
	public static ArrayList<Attribute> attrSet;//属性集
	public String targetAttribute;//目标属性名
	public static ArrayList<String> targetValueRange;//目标属性的值域
	public static ArrayList<Double> targetValueCount;//目标属性各个值出现的个数

	/**
	 * 数据集初始化,输入一个属性集和一个目标属性名
	 * @param attrSet 属性集,里面有各个属性的名字
	 * @param targetAttribute //目标属性
	 */
	public DataSet(ArrayList<String> attrSet,String targetAttribute)
	{
		DataSet.attrSet=new ArrayList<Attribute>();
		for(int i=0;i<attrSet.size();i++)
		{
			DataSet.attrSet.add(new Attribute(attrSet.get(i),i));
		}
		this.targetAttribute=targetAttribute;
		targetValueRange=new ArrayList<String>();
		targetValueCount=new ArrayList<Double>();
	}

	/**
	 * 添加一行数据
	 * @param datas 动态参数,指一行数据的各个列的数据
	 */
	public void AddRow(String... datas)
	{
		ArrayList<String> row=new ArrayList<String>();
		for(String data :datas)
		{
			row.add(data);
		}

		//更新目标属性的值域
		String targetValue=row.get(DataSet.attrSet.size());
		if(!DataSet.targetValueRange.contains(targetValue))
		{
			DataSet.targetValueRange.add(targetValue);
			DataSet.targetValueCount.add(1.0);
		}
		else
		{
			int targetValueIndex=DataSet.targetValueRange.indexOf(targetValue);
			DataSet.targetValueCount.set(targetValueIndex,DataSet.targetValueCount.get(targetValueIndex)+1);
		}

		for(int i=0;i<DataSet.attrSet.size();i++)
		{
			Attribute attr=DataSet.attrSet.get(i);
			attr.AddData(row);//将数据交给属性去处理
		}
	}
}

下面实现属性类(Attribute):

import java.util.ArrayList;

/**
 * 属性类,包含了属性的值域和计数表,
 * 计数表中有该属性的各个值出现的个数
 * @author Jason Han
 *
 */
public class Attribute
{
	public ArrayList<String> range;//该属性对应的属性值的值域
	public ArrayList<ArrayList<Double>> countsMatix;//计数表,用于装每个属性值对应的目标属性值个数
	public String attrName;//属性名
	public int columnIndex;//该属性所在的列号

	public Attribute(String attrName,int columnIndex)
	{
		this.attrName=attrName;
		this.columnIndex=columnIndex;
		this.countsMatix=new ArrayList<ArrayList<Double>>();
		this.range=new ArrayList<String>();
	}

	/**
	 * 添加一条数据,统计个数,更新计数表
	 * @param dataRow 数据
	 */
	public void AddData(ArrayList<String> dataRow)
	{
		String columnValue=dataRow.get(columnIndex);//获取属性值
		String targetValue=dataRow.get(DataSet.attrSet.size());//获取目标属性值
		if(range.contains(columnValue))
		{
			int columnValueIndex=range.indexOf(columnValue);//属性值的在值域中的序号
			ArrayList<Double> matrixRow=countsMatix.get(columnValueIndex);
			int targetValueIndex=DataSet.targetValueRange.indexOf(targetValue);
			if(targetValueIndex>=matrixRow.size())
			{
				//将矩阵的行补足
				int matrixRowSize=matrixRow.size();
				for(int i=0;i<(DataSet.targetValueRange.size()-matrixRowSize);i++)
					matrixRow.add(new Double(0));
			}
			matrixRow.set(targetValueIndex, matrixRow.get(targetValueIndex)+1);
		}
		else
		{
			this.range.add(columnValue);//更新值域
			ArrayList<Double> matrixRow=new ArrayList<Double>();//新的计数表的行
			for(int i=0;i<DataSet.targetValueRange.size();i++)
			{
				matrixRow.add(new Double(0));
			}
			int targetValueIndex=DataSet.targetValueRange.indexOf(targetValue);
			matrixRow.set(targetValueIndex, new Double(1));
			this.countsMatix.add(matrixRow);
		}
	}
}

下面是主要的计算类(Bayes):

/**
 * 贝叶斯类,负责根据DataSet类的计数表对未知数据进行测试
 * @author Jason Han
 *
 */

public class Bayes
{
	public double[] Test(String... dataRow)
	{
		double[] likelihood=new double[DataSet.targetValueRange.size()];//各个目标属性值的似然
		//计算dataRow相对于各个目标属性值的似然,即:P(dataRow|targetValue)*P(targetValue)
		for(int i=0;i<DataSet.targetValueRange.size();i++)
		{
			String targetValue=DataSet.targetValueRange.get(i);
			double probOfTargetValue=this.GetProb(targetValue);//P(targetValue)
			Double probOfData=null;//P(dataRow|targetValue)
			for(int p=0;p<DataSet.attrSet.size();p++)
			{
				Attribute attr=DataSet.attrSet.get(p);
				double tempProb=this.GetProb(attr, dataRow[p], targetValue);
				if(probOfData==null)
					probOfData=tempProb;
				else
					probOfData*=tempProb;
			}
			likelihood[i]=probOfTargetValue*probOfData;
		}

		double sumLikelihood=0.0;
		for(int t=0;t<likelihood.length;t++)
		{
			sumLikelihood+=likelihood[t];
		}

		double[] result=new double[DataSet.targetValueRange.size()];
		for(int p=0;p<result.length;p++)
		{
			result[p]=sumLikelihood==0.0?0:(likelihood[p]/sumLikelihood);
		}
		return result;
	}

	/**
	 * 获取目标属性值中的某个特定值的概率,即:P(targetValue)
	 * @param targetValue 目标属性值中的某个特定值
	 * @return 概率
	 */
	private double GetProb(String targetValue)
	{
		double sum=0.0;
		double valueCount=0.0;
		for(int i=0;i<DataSet.targetValueRange.size();i++)
		{
			double count=DataSet.targetValueCount.get(i);
			String value=DataSet.targetValueRange.get(i);
			sum+=count;
			if(targetValue.equals(value))
				valueCount=count;
		}
		return sum<1?0:(valueCount/sum);
	}

	/**
	 * 获取P(attrValue|targetValue)
	 * @param attr 属性
	 * @param attrValue 属性值
	 * @param targetValue 目标属性值
	 * @return
	 */
	private double GetProb(Attribute attr,String attrValue,String targetValue)
	{
		int columnIndex=DataSet.targetValueRange.indexOf(targetValue);
		int rowIndex=attr.range.indexOf(attrValue);
		double columnSum=0.0;
		double count=0.0;
		for(int i=0;i<attr.range.size();i++)
		{
			double tempCount=columnIndex>=attr.countsMatix.get(i).size()?0:attr.countsMatix.get(i).get(columnIndex);
			columnSum+=tempCount;
			if(rowIndex==i)
				count=tempCount;
		}
		return columnSum<1?0:(count/columnSum);
	}
}

至此,一个通用的贝叶斯分类系统完成,如何使用呢?

添加数据代码:

//以上述案例为例

//设置属性集
ArrayList<String> attrSet=new ArrayList<String>();
attrSet.add("Gender");
attrSet.add("Height");
DataSet dataSet=new DataSet(attrSet,"Class");

//添加数据
dataSet.AddRow("F", "1", "Short");

测试代码:

Bayes bayes=new Bayes();
double[] result=bayes.Test(这里为需要测试的数据);
for(int i=0;i<result.length;i++)
{
	String targetValue=DataSet.targetValueRange.get(i);
	System.out.println("P("+targetValue+"):"+result[i]);
}

下面是测试结果(通过上面的身高的案例测试<Adam,M,1.95>):

bayesresult

 

 

 

end.

转载请注明出处:http://jasonhan.me/blog/?p=179

1 条评论

  1. Great Stuff, do you have a twitter account?

Sarah进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>