朴素贝叶斯在文本分类中的应用

       听过朴素贝叶斯的人，知道多项式朴素贝叶斯是神马，伯努利贝叶斯是神马吗？如果不知道，请继续读下去。

      其实所谓的“多项式”或“伯努利”，只不过是在求先验概率和条件概率时统计方法不一样，基本原理没变。

      贝叶斯分类算法（Naive Bayes）是一种基于统计的概率模型算法。在许多场合，朴素贝叶斯可以与决策树，SVM相媲美。它能应用到大数据中，方法简单且分类准确率高、速度快。但它基于属性之间的独立，在实际情况中经常是不成立的，因此分类准确率可能会下降。总的来说，NB是学习代价较低（理论简单，不像SVM和神经网络那么复杂），但效果较好的分类算法。

      贝叶斯分类算法基于托马斯贝叶斯发明的贝叶斯定理，他提出的贝叶斯定理对于现代概率论和数理统计的发展有重要的影响。

      贝叶斯定理：

           对于随机事件A和B：A发生的概率为P（A），B发生的概率为P（B），在B发生的情况下，A发生的概率为P（A|B）。A和B一起发生的联合概率为P（AB）。有：P（A|B） X P(B) = P(AB) = P(B|A) X P(A)，则有：

P(A|B) = P(B|A)P(A) / P(B)

      文本分类（Text Categorization）是指计算机将一片文档归于预先给定的某一类或几类的过程。文本分类的特征提取过程是分词。目前比较好的中文分词器有中科院的ictclas，庖丁，IK等等。经过分词后，每个词就是一个特征。分词中可以自己配置停用词库，扩展词库等。特征选择有诸如TF-IDF，CHI等特征选择算法，就不在此赘述。

      朴素贝叶斯计算先验概率P（C）和条件概率P（X|C）的方法有两种：多项式模型和伯努利模型。两者在计算的时候有两点差别：多项式会统计词频，而伯努利认为单词出现就记为1，没出现记为0，可以看到一个是基于词频，一个是基于文档频率；伯努利在分类时，将词库中的没有出现在待分类文本的词作为反方考虑。

      在计算条件概率时，当待分类文本中的某个词没有出现在词库中时，概率为0，会导致很严重的问题，需要考虑拉普拉斯平滑（laplace smoothing）：它是将所有词出现的次数+1，再进行统计。

      再一个问题就是概率太小而词数太多，会超double，用log将乘法转成加法。

      多项式朴素贝叶斯算法伪代码如下：

 

       伯努利朴素贝叶斯算法伪代码如下：

 

多项式朴素贝叶斯代码：

 

public class NaiveBayesManager {

    /**关键词索引 关键词-索引*/
    private Map<String, Integer> termIndex;
    /**类的索引 类名称-索引*/
    private Map<String, Integer> classIndex;
    /** 类名 */
    private List<String>         className;

    /**某类的文档中所有特征出现的总次数*/
    private int                  classTermsCount[];

    /**某类的文档中某特征出现的次数之和*/
    private int                  classKeyMap[][];

    /**类的个数*/
    private int                  numClasses      = 0;

    /**训练样本的所有特征(出现多次只算一个)*/
    private int                  vocabulary      = 0;

    /**训练样本的特征总次数*/
    private int                  totalTermsCount = 0;

    /** 建立类名和特征名的索引 */
    private void buildIndex(List<Corpus> orignCorpus) {
        classIndex = new HashMap<String, Integer>();
        termIndex = new HashMap<String, Integer>();
        className = new ArrayList<String>();
        Integer idTerm = new Integer(-1);
        Integer idClass = new Integer(-1);
        for (int i = 0; i < orignCorpus.size(); ++i) {
            Corpus corpus = orignCorpus.get(i);
            List<String> terms = corpus.getSegments();
            String label = corpus.getCat();
            if (!classIndex.containsKey(label)) {
                idClass++;
                classIndex.put(label, idClass);
                className.add(label);
            }
            for (String term : terms) {
                totalTermsCount++;
                if (!termIndex.containsKey(term)) {
                    idTerm++;
                    termIndex.put(term, idTerm);
                }
            }
        }
        vocabulary = termIndex.size();
        numClasses = classIndex.size();
    }

    /**
     * 训练
     * */
    public void startTraining(List<Corpus> orignCorpus) {
        buildIndex(orignCorpus);
        classTermsCount = new int[numClasses + 1];
        classKeyMap = new int[numClasses + 1][vocabulary + 1];
        for (int i = 0; i < orignCorpus.size(); ++i) {
            Corpus corpus = orignCorpus.get(i);
            List<String> terms = corpus.getSegments();
            String label = corpus.getCat();
            Integer labelIndex = classIndex.get(label);
            for (String term : terms) {
                Integer wordIndex = termIndex.get(term);
                classTermsCount[labelIndex]++;
                classKeyMap[labelIndex][wordIndex]++;
            }
        }
    }

    public String classify(List<String> terms) {
        int result = 0;
        double maxPro = Double.NEGATIVE_INFINITY;
        for (int cIndex = 0; cIndex < numClasses; ++cIndex) {
            double pro = Math.log10(getPreProbability(cIndex));
            for (String term : terms) {
                pro += Math.log10(getClassConditonalProbability(cIndex, term));
            }
            if (maxPro < pro) {
                maxPro = pro;
                result = cIndex;
            }
        }
        return className.get(result);
    }

    private double getPreProbability(int classIndex) {
        double ret = 0;
        int NC = classTermsCount[classIndex];
        int N = totalTermsCount;
        ret = 1.0 * NC / N;
        return ret;
    }

    private double getClassConditonalProbability(int classIndex, String term) {
        double ret = 0;
        int NCX = 0;
        int N = 0;
        int V = 0;

        Integer wordIndex = termIndex.get(term);
        if (wordIndex != null)
            NCX = classKeyMap[classIndex][wordIndex];

        N = classTermsCount[classIndex];

        V = vocabulary;

        ret = (NCX + 1.0) / (N + V); //laplace smoothing. 拉普拉斯平滑处理 
        return ret;
    }

    public Map<String, Integer> getTermIndex() {
        return termIndex;
    }

    public void setTermIndex(Map<String, Integer> termIndex) {
        this.termIndex = termIndex;
    }

    public Map<String, Integer> getClassIndex() {
        return classIndex;
    }

    public void setClassIndex(Map<String, Integer> classIndex) {
        this.classIndex = classIndex;
    }

    public List<String> getClassName() {
        return className;
    }

    public void setClassName(List<String> className) {
        this.className = className;
    }

    public int[] getClassTermsCount() {
        return classTermsCount;
    }

    public void setClassTermsCount(int[] classTermsCount) {
        this.classTermsCount = classTermsCount;
    }

    public int[][] getClassKeyMap() {
        return classKeyMap;
    }

    public void setClassKeyMap(int[][] classKeyMap) {
        this.classKeyMap = classKeyMap;
    }

    public int getNumClasses() {
        return numClasses;
    }

    public void setNumClasses(int numClasses) {
        this.numClasses = numClasses;
    }

    public int getVocabulary() {
        return vocabulary;
    }

    public void setVocabulary(int vocabulary) {
        this.vocabulary = vocabulary;
    }

    public int getTotalTermsCount() {
        return totalTermsCount;
    }

    public void setTotalTermsCount(int totalTermsCount) {
        this.totalTermsCount = totalTermsCount;
    }

    public static String getSplitword() {
        return splitWord;
    }

}

 

伯努利朴素贝叶斯代码：

 

/**
 * @author zhongmin.yzm
 * 语料训练并载入内存
 * */
public class TrainingDataManager {

    /** 特征索引 */
    private Map<String, Integer> termIndex;
    /** 类索引 */
    private Map<String, Integer> classIndex;
    /** 索引-类名 */
    public List<String>          className;

    /**类的个数*/
    private int                  numClasses = 0;

    /**训练样本的所有特征(出现多次只算一个)*/
    private int                  vocabulary = 0;

    /**训练文本总数*/
    private int                  DocsNum    = 0;

    /**属于某类的文档个数*/
    private int[]                classDocs;

    /**类别c中包含属性 x的训练文本数量*/
    private int[][]              classKeyMap;

    /** 标志位: 分类时的优化 */
    private static boolean       flag[];

    private void buildIndex(List<List<String>> contents, List<String> labels) {
        classIndex = new HashMap<String, Integer>();
        termIndex = new HashMap<String, Integer>();
        className = new ArrayList<String>();
        Integer idTerm = new Integer(-1);
        Integer idClass = new Integer(-1);
        DocsNum = labels.size();
        for (int i = 0; i < DocsNum; ++i) {
            List<String> content = contents.get(i);
            String label = labels.get(i);
            if (!classIndex.containsKey(label)) {
                idClass++;
                classIndex.put(label, idClass);
                className.add(label);
            }
            for (String term : content) {
                if (!termIndex.containsKey(term)) {
                    idTerm++;
                    termIndex.put(term, idTerm);
                }
            }
        }
        vocabulary = termIndex.size();
        numClasses = classIndex.size();
    }

    public void startTraining(List<List<String>> contents, List<String> labels) {
        buildIndex(contents, labels);
        //去重
        List<List<Integer>> contentsIndex = new ArrayList<List<Integer>>();
        for (int i = 0; i < DocsNum; ++i) {
            List<Integer> contentIndex = new ArrayList<Integer>();
            List<String> content = contents.get(i);
            for (String str : content) {
                Integer wordIndex = termIndex.get(str);
                contentIndex.add(wordIndex);
            }
            Collections.sort(contentIndex);
            int num = contentIndex.size();
            List<Integer> tmp = new ArrayList<Integer>();
            for (int j = 0; j < num; ++j) {
                if (j == 0 || contentIndex.get(j - 1) != contentIndex.get(j)) {
                    tmp.add(contentIndex.get(j));
                }
            }
            contentsIndex.add(tmp);
        }
        //
        classDocs = new int[numClasses];
        classKeyMap = new int[numClasses][vocabulary];
        flag = new boolean[vocabulary];
        for (int i = 0; i < DocsNum; ++i) {
            List<Integer> content = contentsIndex.get(i);
            String label = labels.get(i);
            Integer labelIndex = classIndex.get(label);
            classDocs[labelIndex]++;
            for (Integer wordIndex : content) {
                classKeyMap[labelIndex][wordIndex]++;
            }
        }
    }

    /** 分类 时间复杂度 O(c*v) */
    public String classify(List<String> text) {
        double maxPro = Double.NEGATIVE_INFINITY;
        int resultIndex = 0;
        //标记待分类文本中哪些特征 属于 特征表
        for (int i = 0; i < vocabulary; ++i)
            flag[i] = false;
        for (String term : text) {
            Integer wordIndex = termIndex.get(term);
            if (wordIndex != null)
                flag[wordIndex] = true;
        }
        //对特征集中的每个特征: 若出现在待分类文本中,直接计算;否则作为反方参与
        for (int classIndex = 0; classIndex < numClasses; ++classIndex) {
            double pro = Math.log10(getPreProbability(classIndex));
            for (int wordIndex = 0; wordIndex < vocabulary; ++wordIndex) {
                if (flag[wordIndex])
                    pro += Math.log10(getClassConditionalProbability(classIndex, wordIndex));
                else
                    pro += Math.log10(1 - getClassConditionalProbability(classIndex, wordIndex));
            }
            if (maxPro < pro) {
                maxPro = pro;
                resultIndex = classIndex;
            }
        }
        return className.get(resultIndex);
    }

    /** 先验概率: 类C包含的文档数/总文档数 */
    private double getPreProbability(int classIndex) {
        double ret = 0.0;
        ret = 1.0 * classDocs[classIndex] / DocsNum;
        return ret;
    }

    /** 条件概率: 类C中包含关键字t的文档个数/类C包含的文档数 */
    private double getClassConditionalProbability(int classIndex, int termIndex) {
        int NCX = classKeyMap[classIndex][termIndex];
        int N = classDocs[classIndex];
        double ret = (NCX + 1.0) / (N + DocsNum);
        return ret;
    }

}