算法-c#-基于朴素贝叶斯+词频向量空间模型的文本分类实现

算法-c#-基于朴素贝叶斯+词频向量空间模型的文本分类实现

一、朴素贝叶斯分类：

公式：

P(C|X) = P(X|C)P(C)/P(X)

其中：

P(C|X)：后验概率

P(X|C)：似然概率（条件概率）

P(C)：先验概率

P(X)：联合概率

二、朴素贝叶斯文本分类

文本分类就是求解：“待分类文本特征”，在训练样本中各分类下的“后验概率” 。

三、朴素贝叶斯转换为文本分类的两个模型

1.多项式模型（词频模型）

在多项式模型中， 设某文档d=(t1,t2,…,tk)，tk是该文档中出现过的单词，允许重复，

则：

先验概率P(c)=“类c下单词总数”/“整个训练样本的单词总数”

条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+1)/(类c下单词总数+|V|)

V是训练样本的单词表（即抽取单词，单词出现多次，只算一个），

|V|则表示训练样本包含多少个不重复单词。在这里，m=|V|, p=1/|V|。

P(tk|c)可以看作是单词tk在证明d属于类c上提供了多大的证据，

而P(c)则可以认为是类别c在整体上占多大比例(有多大可能性)。

按照词频统计方式，还可以表示为：（词频向量空间，主要依赖这个模型）

先验概率P(c)=“类c下词频之和”/“整个训练样本的词频之和”

条件概率P(tk|c)=(单词tk在类c下的词频之和+1)/(训练样本类c的词频之和+训练样本类c下不重复单词个数)

训练文本集

yes:[Chinese,Beijing,Chinese]

yes:[Chinese,Chinese,Shanghai]

yes:[Chinese,Macao]

no:[Tokyo,Japan,Chinese]

给定一个新样本Chinese Chinese Chinese Tokyo Japan，对其进行分类。

该文本用属性向量表示为d=(Chinese, Chinese, Chinese, Tokyo, Japan)，

类别集合为Y={yes, no}。

类yes下总共有8个单词，类no下总共有3个单词，训练样本单词总数为11，

因此P(yes)=8/11, P(no)=3/11。

类"条件概率"计算如下：

P(Chinese | yes)=(5+1)/(8+6)=6/14=3/7 //类yes下单词Chinese在各个文档中出现过的次数之和+1/类yes下单词的总数(8)+总训练样本的不重复单词(6)

P(Japan | yes)=P(Tokyo | yes)= (0+1)/(8+6)=1/14

P(Chinese|no)=(1+1)/(3+6)=2/9

P(Japan|no)=P(Tokyo| no) =(1+1)/(3+6)=2/9

分母中的8，是指yes类别下textc的长度，也即训练样本的单词总数，

6是指训练样本有Chinese,Beijing,Shanghai, Macao, Tokyo, Japan 共6个单词，

3是指no类下共有3个单词。

有了以上类条件概率，开始计算后验概率，

P(yes | d)=(3/7)^3×(1/14)×(1/14)×(8/11)=分子乘积/分母乘积=108/184877≈0.00029209  //Chinese Chinese Chinese Tokyo Japan

P(no | d)= (2/9)^3×(2/9)×(2/9)×(3/11)=分子乘积/分母乘积=32/216513≈0.00014780

比较大小后，因此，这个文档属于类别china。

2.伯努利模型（文档模型）

P(c)= 类c下文件总数/整个训练样本的文件总数

P(tk|c)=(类c下包含单词tk的文件数+1)/(类c的文档总数+2)

在这里，m=2, p=1/2。

还是使用前面例子中的数据。

类yes下总共有3个文件，类no下有1个文件，训练样本文件总数4；

因此：

P(yes)=3/4

P(Chinese | yes)=(3+1)/(3+2)=4/5

P(Japan | yes)=P(Tokyo | yes)=(0+1)/(3+2)=1/5

P(Beijing | yes)= P(Macao|yes)= P(Shanghai |yes)=(1+1)/(3+2)=2/5

P(Chinese|no)=(1+1)/(1+2)=2/3

P(Japan|no)=P(Tokyo| no) =(1+1)/(1+2)=2/3

P(Beijing| no)= P(Macao| no)= P(Shanghai | no)=(0+1)/(1+2)=1/3

有了以上类条件概率，开始计算后验概率，

P(yes | d)=P(yes)×P(Chinese|yes) ×P(Japan|yes) ×P(Tokyo|yes)×(1-P(Beijing|yes)) ×(1-P(Shanghai|yes))×(1-P(Macao|yes))

=3/4×4/5×1/5×1/5×(1-2/5) ×(1-2/5)×(1-2/5)=81/15625≈0.005

P(no | d)= 1/4×2/3×2/3×2/3×(1-1/3)×(1-1/3)×(1-1/3)=16/729≈0.022

因此，这个文档不属于类别china。

3.两个模型的区别

二者的计算粒度不一样，多项式模型以单词为粒度，伯努利模型以文件为粒度，因此二者的先验概率和类条件概率的计算方法都不同。

计算后验概率时，对于一个文档d，多项式模型中，只有在d中出现过的单词，才会参与后验概率计算，伯努利模型中，没有在d中出现，

但是在全局单词表中出现的单词，也会参与计算，不过是作为“反方”参与的。

四、测试代码（朴素贝叶斯算法+词频向量模型）

using Grass.Extend;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;


namespace DiscoverTest.Arithmetic
{
    [TestClass]
    public class NbTest2
    {
        [TestMethod]
        public void NbType()
        {
            //列别集
            var types = new Dictionary<string, string>
            {
                {"yes","好天气"},
                {"no","坏天气"},
            };
            
            var trainSet = new []
            {
                new []{"yes","晴朗","适中","微风"},
                new []{"yes","高温","微风"},
                new []{"no","阴天","低温","高温","强风"},
                new []{"no","雨天","潮湿"},
            };


            var nb = new NaiveBayesClassifier(types, trainSet);


            Console.WriteLine(new string('~', 60));
            var content = "晴朗,高温,潮湿,微风";
            var type = nb.GetClassify(content);
            Console.WriteLine("结果={0}，{2} ；待分类特征={1}；", type, content, types[type]);


            Console.WriteLine(new string('~', 60));
            content = "阴天,低温,强风,晴朗";
            type = nb.GetClassify(content);
            Console.WriteLine("结果={0}，{2} ；待分类特征={1}；", type, content, types[type]);


            Console.WriteLine(new string('~', 60));
            content = "阴天,低温,晴朗,晴朗,适中";
            type = nb.GetClassify(content);
            Console.WriteLine("结果={0}，{2} ；待分类特征={1}；", type, content, types[type]);
        }
    }


    /// <summary>
    /// 朴素贝叶斯分类器
    /// </summary>
    public class NaiveBayesClassifier
    {
        /// <summary>
        /// 
        /// </summary>
        /// <param name="types">类别字典（key=类别代码；value=类别名称）</param>
        /// <param name="trainSet">
        /// 训练文本集：二维数组，[[分别代码,关键字1，关键字2，关键字3...],...]
        /// 如:[["a","1","2","3"],["a","2","3","4","5","6"],["b","11","12","13"],["b","21","22","23"]]
        /// </param>
        public NaiveBayesClassifier(Dictionary<string, string> types
            , string[][] trainSet)
        {
            //初始化
            types.Keys
                .ToList()
                .ForEach(x =>
                {
                    TrainTermSetTfGroup.Add(x, new List<int>());
                    TrainTermSetGroup.Add(x, new List<string>());
                });


            //构建不重复的训练文本关键字集合
            trainSet.ToList().ForEach(x =>
            {
                for (int i = 0; i < x.Length; i++)
                {
                    //第0项为类目
                    if (i == 0)
                        continue;
                    TrainTermSet.Add(x[i]);
                }
            });
            Console.WriteLine("训练集字典：{0}", TrainTermSet.ToJsonSerialize());
            //训练集分组
            SortedSet<string> set = new SortedSet<string>();
            List<string> list = new List<string>();
            types.Keys
                .ToList()
                .ForEach(x =>
                {
                    GroupByType(x,trainSet,ref list,ref set);
                    TrainTermSetTfGroup[x] = (new int[set.Count]).ToList();
                    TrainTermSetGroup[x] = set.ToList();
                });
            //训练集分组词频初始化
            InitTrainTf(trainSet);
        }
        #region 变量
        /// <summary>
        /// 训练样本集，不重复关键字集合
        /// </summary>
        public SortedSet<string> TrainTermSet = new SortedSet<string>();
        /// <summary>
        /// 类目的关键词分组(key=类目，value=类目下不重复有序关键词）
        /// </summary>
        public Dictionary<string, List<string>> TrainTermSetGroup = new Dictionary<string, List<string>>();
        /// <summary>
        /// 类目的词频向量空间(key=类目，value=类目下不重复有序关键词词频）
        /// </summary>
        public Dictionary<string, List<int>> TrainTermSetTfGroup = new Dictionary<string, List<int>>();
        /// <summary>
        /// 待分类文本，
        /// 按类目分组的词频向量空间(key=类目，value=词频向量）
        /// </summary>
        public Dictionary<string, List<int>> TempTfSetGroup = new Dictionary<string, List<int>>();
        /// <summary>
        /// 待分类文本，关键词列表(可重复)
        /// </summary>
        public List<string> TempTermList = new List<string>();
        /// <summary>
        /// 分类最终得分
        /// </summary>
        Dictionary<string, double> _typesScore = new Dictionary<string, double>(); 
        #endregion


        #region 方法
        /// <summary>
        /// 初始化训练集词频
        /// </summary>
        private void InitTrainTf(string[][] trainSet)
        {
            //string type = string.Empty;
            int index = 0;
            int total = 0;
            foreach (KeyValuePair<string, List<string>> item in TrainTermSetGroup)//训练集,分组
            {
                foreach (string[] arr in trainSet)//训练集
                {
                    if(!item.Key.Equals(arr[0]))
                        continue;
                    foreach (string term in item.Value)//训练集,分组词频
                    {
                        total = arr.Count(x=>x.Equals(term));//词频
                        index = TrainTermSetGroup[item.Key].FindIndex(x => x.Equals(term));//关键词位置
                        TrainTermSetTfGroup[item.Key][index] += total;//词频加总
                    }
                }
            }
            Console.WriteLine("训练集分组：{0}", TrainTermSetGroup.ToJsonSerialize());
            Console.WriteLine("训练集词频：{0}", TrainTermSetTfGroup.ToJsonSerialize());
        }
        /// <summary>
        /// 初始化待分类文本，在各个分类中的词频向量
        /// </summary>
        /// <param name="termList"></param>
        private void InitTempTfSetGroup(List<string> termList)
        {
            int index = 0;
            int total = 0;
            int tf = 0;
            TempTfSetGroup.Clear();
            foreach (KeyValuePair<string, List<string>> item in TrainTermSetGroup) //训练集,分组
            {
                TempTfSetGroup[item.Key] = (new int[item.Value.Count]).ToList();
                foreach (string term in item.Value)//每个分组下的关键词
                {
                    index = TrainTermSetGroup[item.Key].FindIndex(x => x.Equals(term));//关键词位置
                    total = termList.Count(x => x.Equals(term));//关键词次数
                    tf = TrainTermSetTfGroup[item.Key][index];//关键词词频


                    TempTfSetGroup[item.Key][index] = tf * total;
                }
            }
        }


        /// <summary>
        /// 获取指定类目的关键词
        /// </summary>
        /// <param name="type"></param>
        /// <param name="trainSet"></param>
        /// <param name="list"></param>
        /// <param name="set"></param>
        private void GroupByType(string type, string[][] trainSet, ref List<string> list, ref SortedSet<string> set)
        {
            list.Clear();
            set.Clear();
            
            for (int i = 0; i < trainSet.Length; i++)
            {
                for (int j = 0; j < trainSet[i].Length; j++)
                {
                    if(!type.Equals(trainSet[i][0]) || j==0) //j==0 为分类名
                        continue;
                    list.Add(trainSet[i][j]);
                    set.Add(trainSet[i][j]);
                }
            }
            list.Sort();
        }


        /// <summary>
        /// 分词
        /// </summary>
        /// <param name="content"></param>
        /// <returns>排序后的分词结果</returns>
        public List<string> GetTermSegment(string content)
        {
            var lst = new List<string>();
            Regex reg;
            MatchCollection ms;
            //遍历样本集关键词字典，对待分类文本进行分词
            foreach (string term in TrainTermSet)
            {
                reg = new Regex(term);
                if (!reg.IsMatch(content))
                    continue;
                ms = reg.Matches(content);
                for (int i = 0; i < ms.Count; i++)
                {
                    lst.Add(ms[i].Value);
                }
            }
            lst.Sort();
            Console.WriteLine("分词结果：{0}", lst.ToJsonSerialize());
            return lst;
        }


        /// <summary>
        /// 获取最终分类结果
        /// </summary>
        /// <returns></returns>
        public string GetClassify(string content)
        {
            //对文本进行分词
            TempTermList = GetTermSegment(content);//分词


            //初始化待分类文本，在各个分类中的词频
            InitTempTfSetGroup(TempTermList);


            /*
             * P(C|X)=P(X|C)P(C)/P(X)；后验概率=似然概率(条件概率)*先验概率/联合概率
             * 
             * 其中，P(X)联合概率，为常量，所以只需要计算和比较各个分类 P(X|C)P(C) 值
             * 
             * 公式：P(X|C)P(C)
             * 其中：
             * P(X|C)=P(x1|c1)P(x2|c1)...P(xn|c1)
             * P(x1|c1)="x1关键字在c1文档中出现过的次数之和+1"/"类c1下单词的总数(单词可重复)+总训练样本的不重复单词数"
             * P(c1)=类c1下总共有单词个数（可重复）/训练样本单词总数(可重复)，
             * 
             * 先验概率P(c1)=“类c下词频之和”/“整个训练样本的词频之和”
             * 条件概率P(x1|c1)=(单词x1在类c1下的词频之和+1)/(训练样本类c1的词频之和+训练样本类c1下不重复单词个数)
             * 
             */
            double prior = 1.0;
            double likelihood = 1.0;
            double typeScore = 1.0;
            _typesScore.Clear();
            foreach (var type in TrainTermSetGroup.Keys)
            {
                //计算先验概率P(c1)
                prior = GetPrior(type);
                //计算条件概率P(x1|c1)
                likelihood = GetLikelihood(type);
                //记录最终得分
                typeScore = prior*likelihood;
                NoteTypeScore(type,typeScore);
            }
            //返回最高得分的分类
            return GetMaxSoreType();
        }


        private string GetMaxSoreType()
        {
            //对字典中的值进行排序
            Dictionary<string, double > soretDic = _typesScore
                .OrderByDescending(x => x.Value)
                .ToDictionary(x => x.Key, x => x.Value);
            Console.WriteLine("排序后：{0}",soretDic.ToJsonSerialize());
            //返回第一个分数最高的类型code
            return soretDic.First().Key;
        }
        /// <summary>
        /// 记录类型得分
        /// </summary>
        /// <param name="type"></param>
        /// <param name="sore"></param>
        private void NoteTypeScore(string type, double sore)
        {
            if (_typesScore.ContainsKey(type))
            {
                _typesScore.Add(type, sore);
                return;
            }
            Console.WriteLine("得分：{0}={1}",type, sore);
            _typesScore[type] = sore;
        }
        /// <summary>
        /// 计算先验概率
        /// </summary>
        /// <param name="type"></param>
        /// <returns></returns>
        private double GetPrior(string type)
        {
            /*
             * 先验概率P(c1)=“类c下词频之和”/“整个训练样本的词频之和”
             */


            int tf = TrainTermSetTfGroup[type].Sum(x => x);//使用变量提高性能
            int tfAll = 0;//使用变量提高性能
            foreach (var key in TrainTermSetTfGroup.Keys)
            {
                tfAll += TrainTermSetTfGroup[key].Sum(x => x);
            }


            double result = tf * 1.0 / tfAll;
            Console.WriteLine("先验概率：{0}={1}", type, result);
            return result;
        }


        /// <summary>
        /// 计算似然概率 
        /// </summary>
        /// <param name="type"></param>
        /// <returns></returns>
        private double GetLikelihood(string type)
        {
            /*
             * P(X|c1)=P(x1|c1)P(x2|c1)...P(xn|c1)
             * P(x1|c1)="x1关键字在c1文档中出现过的次数之和+1"/"类c1下单词的总数(单词可重复)+总训练样本的不重复单词数"
             * 条件概率P(x1|c1)=(单词x1在类c1下的词频之和+1)/(训练样本类c1的词频之和+训练样本类c1下不重复单词个数)
             * 注：引入Laplace校准，它的思想非常简单，就是对没类别下所有划分的计数加1，解决 P(x1|c1)=0 的情况
             */
            int tf = TempTfSetGroup[type].Sum(x => x)+1;//使用变量提高性能
            int termCount = TrainTermSetTfGroup[type].Sum(x => x);
            int trainTermCount = TrainTermSet.Count;


            double result = tf*1.0/(termCount + trainTermCount);
            Console.WriteLine("条件概率：{0}={1}",type,result);
            return result;
        }


        #endregion


    }
}