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

雨点打透心脏的1/2处 2024-02-18 18:47 59阅读 0赞

算法-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
    
    
        }
    }