文档章节

余弦定理实现新闻自动分类算法

一贱书生
 一贱书生
发布于 2017/04/16 21:06
字数 2469
阅读 61
收藏 0

前言

余弦定理,这个在初中课本中就出现过的公式,恐怕没有人不知道的吧。但是另外一个概念,可能不是很多的人会听说过,他叫空间向量,一般用e表示,高中课本中有专门讲过这个东西,有了余弦定理和向量空间,我们就可以做许多有意思的事情了,利用余弦定理计算文本相似度的算法就是其中一个很典型的例子。当然这个话题太老,说的人太多,没有什么新意,恰巧周末阅读了吴军博士的<<数学之美>>这门书,书中讲到了利用余弦定理实现新闻分类,于是就索性完成这个算法的初步模型。感兴趣的可以继续往下看。

算法背景

在以往,如果对一则新闻进行归类,一般使用的都是人工分类的办法,大体上看一下标题和首尾两段文字,就能知道新闻是属于财经的,体育的又或者是健康类的。但是在当今信息爆炸的时代,这显然是不可能完成的任务,所以我们急切的相用机器自己帮我们”分类“。最好的形式是我给计算机提供大量的已分类好的数据,等强大的计算机大脑训练好了这个分类模型,后边的事情就是他来完成了。看起来这好像很高深,很困难的样子,但是其实我们自己也可以写一个,只是效果可能不会那么好。

分类器实现原理

新闻自动分类器实现的本质也是利用余弦定理比较文本的相似度,于是这个问题的难点就在于这个特征向量哪里来,怎么去获得。特征向量,特征向量,关键两个字在于特征,新闻的特征就在于他的关键词,我的简单理解就是专业性的词语,换句话说,就是属于某类新闻特有的词语,比如金融类的新闻,关键词一般就是股票啊,公司啊,上市啊等等词语。这些词的寻找可以通过统计词频的方式实现,最后统计出来的关键词,进行降序排列,一个关键词就代表一个新的维度。 那么新的问题又来了,我要统计词频,那么就得首先进行分词,要把每个新闻句子的主谓宾统统挖掘出来啊,好像这个工作比我整个算法还要复杂的样子。OK,其实已经有人已经帮我们把这个问题解决了,在这个算法中我使用的是中科大的ICTCLAS分词系统,效果非常棒,举个例子,下面是我原始的新闻内容:

 

[java] view plain copy

 print?

  1. 教育部副部长:教育公平是社会公平重要基础  
  2. 7月23日,教育部党组副书记、副部长杜玉波为全国学联全体代表作《教育综合改革与青年学生成长成才》的专题报告。 中国青年网记者 张炎良 摄  
  3. 人民网北京7月24日电(记者 贺迎春 实习生 王斯慧  


经过分词系统处理后的分词效果:

 

 

[java] view plain copy

 print?

  1. 教育部/nt 副/b 部长/n :/wm 教育/v 公平/an 是/vshi 社会/n 公平/a 重要/a 基础/n   
  2. 7月/t 23日/t ,/wd 教育部/nt 党组/n 副/b 书记/n 、/wn 副/b 部长/n 杜玉波/nr 为/p 全国学联/nt 全体/n 代表作/n 《/wkz 教育/vn 综合/vn 改革/vn 与/cc 青年/n 学生/n 成长/vi 成才/vi 》/wky 的/ude1 专题/n 报告/n 。/wj  中国/ns 青年/n 网/n 记者/n  张/q 炎/ng 良/d  摄/vg   
  3. 人民/n 网/n 北京/ns 7月/t 24日/t 电/n (/wkz 记者/n  贺/vg 迎春/n  实习生/n  王斯慧/nr )/wky 昨日/t ,/wd 教育部/nt 副/b 部长  


OK,有了这个分词的结果之后,后面的事情就水到渠成了。

 

算法的实现步骤

1、给定训练的新闻数据集。

2、通过分词系统统计词频的方式,统计词频最高的N位作为特征词,即特征向量

3、输入测试数据,同样统计词频,并于训练数据的进行商的操作,得到特征向量值

4、最后利用余弦定理计算相似度,并与最小阈值做比较。

算法的代码实现

ICTCLAS工具类ICTCLAS.Java:

 

[java] view plain copy

 print?

  1. package NewsClassify;  
  2.   
  3. import java.io.File;  
  4. import java.io.FileOutputStream;  
  5. import java.io.InputStream;  
  6. import java.util.StringTokenizer;  
  7.   
  8. public class ICTCLAS50 {  
  9.     static {  
  10.         try {  
  11.             String libpath = System.getProperty("user.dir") + "\\lib";  
  12.             String path = null;  
  13.             StringTokenizer st = new StringTokenizer(libpath,  
  14.                     System.getProperty("path.separator"));  
  15.             if (st.hasMoreElements()) {  
  16.                 path = st.nextToken();  
  17.             }  
  18.   
  19.             // copy all dll files to java lib path  
  20.             File dllFile = null;  
  21.             InputStream inputStream = null;  
  22.             FileOutputStream outputStream = null;  
  23.             byte[] array = null;  
  24.   
  25.             dllFile = new File(new File(path), "ICTCLAS50.dll");  
  26.             if (!dllFile.exists()) {  
  27.                 inputStream = ICTCLAS50.class.getResource("/lib/ICTCLAS50.dll")  
  28.                         .openStream();  
  29.                 outputStream = new FileOutputStream(dllFile);  
  30.                 array = new byte[1024];  
  31.                 for (int i = inputStream.read(array); i != -1; i = inputStream  
  32.                         .read(array)) {  
  33.                     outputStream.write(array, 0, i);  
  34.                 }  
  35.                 outputStream.close();  
  36.             }  
  37.         } catch (Exception e) {  
  38.             e.printStackTrace();  
  39.         }  
  40.   
  41.         try {  
  42.             // load JniCall.dll  
  43.             System.loadLibrary("ICTCLAS50");  
  44.             System.out.println("4444");  
  45.         } catch (Error e) {  
  46.               
  47.             e.printStackTrace();  
  48.         }  
  49.     }  
  50.   
  51.     public native boolean ICTCLAS_Init(byte[] sPath);  
  52.   
  53.     public native boolean ICTCLAS_Exit();  
  54.   
  55.     public native int ICTCLAS_ImportUserDictFile(byte[] sPath, int eCodeType);  
  56.   
  57.     public native int ICTCLAS_SaveTheUsrDic();  
  58.   
  59.     public native int ICTCLAS_SetPOSmap(int nPOSmap);  
  60.   
  61.     public native boolean ICTCLAS_FileProcess(byte[] sSrcFilename,  
  62.             int eCodeType, int bPOSTagged, byte[] sDestFilename);  
  63.   
  64.     public native byte[] ICTCLAS_ParagraphProcess(byte[] sSrc, int eCodeType,  
  65.             int bPOSTagged);  
  66.   
  67.     public native byte[] nativeProcAPara(byte[] sSrc, int eCodeType,  
  68.             int bPOStagged);  
  69. }  

新闻实体类New.java

 

 

[java] view plain copy

 print?

  1. package NewsClassify;  
  2.   
  3. /** 
  4.  * 词语实体类 
  5.  *  
  6.  * @author lyq 
  7.  *  
  8.  */  
  9. public class Word implements Comparable<Word> {  
  10.     // 词语名称  
  11.     String name;  
  12.     // 词频  
  13.     Integer count;  
  14.   
  15.     public Word(String name, Integer count) {  
  16.         this.name = name;  
  17.         this.count = count;  
  18.     }  
  19.   
  20.     @Override  
  21.     public int compareTo(Word o) {  
  22.         // TODO Auto-generated method stub  
  23.         return o.count.compareTo(this.count);  
  24.     }  
  25. }  

分类算法类NewsClassify.java:

 

 

[java] view plain copy

 print?

  1. package NewsClassify;  
  2.   
  3. import java.io.BufferedReader;  
  4. import java.io.File;  
  5. import java.io.FileReader;  
  6. import java.io.IOException;  
  7. import java.util.ArrayList;  
  8. import java.util.Collections;  
  9.   
  10. /** 
  11.  * 分类算法模型 
  12.  *  
  13.  * @author lyq 
  14.  *  
  15.  */  
  16. public class NewsClassifyTool {  
  17.     // 余弦向量空间维数  
  18.     private int vectorNum;  
  19.     // 余弦相似度最小满足阈值  
  20.     private double minSupportValue;  
  21.     // 当前训练数据的新闻类别  
  22.     private String newsType;  
  23.     // 训练新闻数据文件地址  
  24.     private ArrayList<String> trainDataPaths;  
  25.   
  26.     public NewsClassifyTool(ArrayList<String> trainDataPaths, String newsType,  
  27.             int vectorNum, double minSupportValue) {  
  28.         this.trainDataPaths = trainDataPaths;  
  29.         this.newsType = newsType;  
  30.         this.vectorNum = vectorNum;  
  31.         this.minSupportValue = minSupportValue;  
  32.     }  
  33.   
  34.     /** 
  35.      * 从文件中读取数据 
  36.      */  
  37.     private String readDataFile(String filePath) {  
  38.         File file = new File(filePath);  
  39.         StringBuilder strBuilder = null;  
  40.   
  41.         try {  
  42.             BufferedReader in = new BufferedReader(new FileReader(file));  
  43.             String str;  
  44.             strBuilder = new StringBuilder();  
  45.             while ((str = in.readLine()) != null) {  
  46.                 strBuilder.append(str);  
  47.             }  
  48.             in.close();  
  49.         } catch (IOException e) {  
  50.             e.getStackTrace();  
  51.         }  
  52.   
  53.         return strBuilder.toString();  
  54.     }  
  55.   
  56.     /** 
  57.      * 计算测试数据的特征向量 
  58.      */  
  59.     private double[] calCharacterVectors(String filePath) {  
  60.         int index;  
  61.         double[] vectorDimensions;  
  62.         double[] temp;  
  63.         News news;  
  64.         News testNews;  
  65.         String newsCotent;  
  66.         String testContent;  
  67.         String parseContent;  
  68.         // 高频词汇  
  69.         ArrayList<Word> frequentWords;  
  70.         ArrayList<Word> wordList;  
  71.   
  72.         testContent = readDataFile(filePath);  
  73.         testNews = new News(testContent);  
  74.         parseNewsContent(filePath);  
  75.   
  76.         index = filePath.indexOf('.');  
  77.         parseContent = readDataFile(filePath.substring(0, index) + "-split.txt");  
  78.         testNews.statWords(parseContent);  
  79.   
  80.         vectorDimensions = new double[vectorNum];  
  81.         // 计算训练数据集的类别的特征向量  
  82.         for (String path : this.trainDataPaths) {  
  83.             newsCotent = readDataFile(path);  
  84.             news = new News(newsCotent);  
  85.   
  86.             // 进行分词操作  
  87.             index = path.indexOf('.');  
  88.             parseNewsContent(path);  
  89.             parseContent = readDataFile(path.substring(0, index) + "-split.txt");  
  90.             news.statWords(parseContent);  
  91.   
  92.             wordList = news.wordDatas;  
  93.             // 将词频统计结果降序排列  
  94.             Collections.sort(wordList);  
  95.   
  96.             frequentWords = new ArrayList<Word>();  
  97.             // 截取出前vectorDimens的词语  
  98.             for (int i = 0; i < vectorNum; i++) {  
  99.                 frequentWords.add(wordList.get(i));  
  100.             }  
  101.   
  102.             temp = testNews.calVectorDimension(frequentWords);  
  103.             // 将特征向量值进行累加  
  104.             for (int i = 0; i < vectorDimensions.length; i++) {  
  105.                 vectorDimensions[i] += temp[i];  
  106.             }  
  107.         }  
  108.   
  109.         // 最后取平均向量值作为最终的特征向量值  
  110.         for (int i = 0; i < vectorDimensions.length; i++) {  
  111.             vectorDimensions[i] /= trainDataPaths.size();  
  112.         }  
  113.   
  114.         return vectorDimensions;  
  115.     }  
  116.   
  117.     /** 
  118.      * 根据求得的向量空间计算余弦相似度值 
  119.      *  
  120.      * @param vectorDimension 
  121.      *            已求得的测试数据的特征向量值 
  122.      * @return 
  123.      */  
  124.     private double calCosValue(double[] vectorDimension) {  
  125.         double result;  
  126.         double num1;  
  127.         double num2;  
  128.         double temp1;  
  129.         double temp2;  
  130.         // 标准的特征向量,每个维度上都为1  
  131.         double[] standardVector;  
  132.   
  133.         standardVector = new double[vectorNum];  
  134.         for (int i = 0; i < vectorNum; i++) {  
  135.             standardVector[i] = 1;  
  136.         }  
  137.   
  138.         temp1 = 0;  
  139.         temp2 = 0;  
  140.         num1 = 0;  
  141.   
  142.         for (int i = 0; i < vectorNum; i++) {  
  143.             // 累加分子的值  
  144.             num1 += vectorDimension[i] * standardVector[i];  
  145.   
  146.             // 累加分母的值  
  147.             temp1 += vectorDimension[i] * vectorDimension[i];  
  148.             temp2 += standardVector[i] * standardVector[i];  
  149.         }  
  150.   
  151.         num2 = Math.sqrt(temp1) * Math.sqrt(temp2);  
  152.         // 套用余弦定理公式进行计算  
  153.         result = num1 / num2;  
  154.   
  155.         return result;  
  156.     }  
  157.   
  158.     /** 
  159.      * 进行新闻分类 
  160.      *  
  161.      * @param filePath 
  162.      *            测试新闻数据文件地址 
  163.      */  
  164.     public void newsClassify(String filePath) {  
  165.         double result;  
  166.         double[] vectorDimension;  
  167.   
  168.         vectorDimension = calCharacterVectors(filePath);  
  169.         result = calCosValue(vectorDimension);  
  170.   
  171.         // 如果余弦相似度值满足最小阈值要求,则属于目标分类  
  172.         if (result >= minSupportValue) {  
  173.             System.out.println(String.format("最终相似度结果为%s,大于阈值%s,所以此新闻属于%s类新闻",  
  174.                     result, minSupportValue, newsType));  
  175.         } else {  
  176.             System.out.println(String.format("最终相似度结果为%s,小于阈值%s,所以此新闻不属于%s类新闻",  
  177.                     result, minSupportValue, newsType));  
  178.         }  
  179.     }  
  180.   
  181.     /** 
  182.      * 利用分词系统进行新闻内容的分词 
  183.      *  
  184.      * @param srcPath 
  185.      *            新闻文件路径 
  186.      */  
  187.     private void parseNewsContent(String srcPath) {  
  188.         // TODO Auto-generated method stub  
  189.         int index;  
  190.         String dirApi;  
  191.         String desPath;  
  192.   
  193.         dirApi = System.getProperty("user.dir") + "\\lib";  
  194.         // 组装输出路径值  
  195.         index = srcPath.indexOf('.');  
  196.         desPath = srcPath.substring(0, index) + "-split.txt";  
  197.   
  198.         try {  
  199.             ICTCLAS50 testICTCLAS50 = new ICTCLAS50();  
  200.             // 分词所需库的路径、初始化  
  201.             if (testICTCLAS50.ICTCLAS_Init(dirApi.getBytes("GB2312")) == false) {  
  202.                 System.out.println("Init Fail!");  
  203.                 return;  
  204.             }  
  205.             // 将文件名string类型转为byte类型  
  206.             byte[] Inputfilenameb = srcPath.getBytes();  
  207.   
  208.             // 分词处理后输出文件名、将文件名string类型转为byte类型  
  209.             byte[] Outputfilenameb = desPath.getBytes();  
  210.   
  211.             // 文件分词(第一个参数为输入文件的名,第二个参数为文件编码类型,第三个参数为是否标记词性集1 yes,0  
  212.             // no,第四个参数为输出文件名)  
  213.             testICTCLAS50.ICTCLAS_FileProcess(Inputfilenameb, 0, 1,  
  214.                     Outputfilenameb);  
  215.             // 退出分词器  
  216.             testICTCLAS50.ICTCLAS_Exit();  
  217.         } catch (Exception ex) {  
  218.             ex.printStackTrace();  
  219.         }  
  220.   
  221.     }  
  222. }  

场景测试了Client.java:

 

 

[java] view plain copy

 print?

  1. package NewsClassify;  
  2.   
  3. import java.util.ArrayList;  
  4.   
  5.   
  6. /** 
  7.  * 新闻分类算法测试类 
  8.  * @author lyq 
  9.  * 
  10.  */  
  11. public class Client {  
  12.     public static void main(String[] args){  
  13.         String testFilePath1;  
  14.         String testFilePath2;  
  15.         String testFilePath3;  
  16.         String path;  
  17.         String newsType;  
  18.         int vectorNum;  
  19.         double minSupportValue;  
  20.         ArrayList<String> trainDataPaths;  
  21.         NewsClassifyTool classifyTool;  
  22.           
  23.         //添加测试以及训练集数据文件路径  
  24.         testFilePath1 = "C:\\Users\\lyq\\Desktop\\icon\\test\\testNews1.txt";  
  25.         testFilePath2 = "C:\\Users\\lyq\\Desktop\\icon\\test\\testNews2.txt";  
  26.         testFilePath3 = "C:\\Users\\lyq\\Desktop\\icon\\test\\testNews3.txt";  
  27.         trainDataPaths = new ArrayList<String>();  
  28.         path = "C:\\Users\\lyq\\Desktop\\icon\\test\\trainNews1.txt";  
  29.         trainDataPaths.add(path);  
  30.         path = "C:\\Users\\lyq\\Desktop\\icon\\test\\trainNews2.txt";  
  31.         trainDataPaths.add(path);  
  32.           
  33.         newsType = "金融";  
  34.         vectorNum = 10;  
  35.         minSupportValue = 0.45;  
  36.           
  37.         classifyTool = new NewsClassifyTool(trainDataPaths, newsType, vectorNum, minSupportValue);  
  38.         classifyTool.newsClassify(testFilePath1);  
  39.         classifyTool.newsClassify(testFilePath2);  
  40.         classifyTool.newsClassify(testFilePath3);  
  41.     }  
  42.   
  43. }  

结果输出:

 

 

[java] view plain copy

 print?

  1. 最终相似度结果为0.39999999999999997,小于阈值0.45,所以此新闻不属于金融类新闻  
  2. 最终相似度结果为0.4635393084189425,大于阈值0.45,所以此新闻属于金融类新闻  
  3. 最终相似度结果为0.661835948543857,大于阈值0.45,所以此新闻属于金融类新闻  

本文转载自:http://blog.csdn.net/Androidlushangderen/article/details/47090883

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
读《数学之美系列十二——余弦定理和新闻的分类》有感 + 代码规范

Google的新闻是自动分类而产生的,但是计算机只懂算法,是看不懂我们人类的新闻。若是人为地一个新闻一个新闻地划分又会浪费不必要的人力、物理。由此,我们设计出一个算法,帮助我们利用计算...

lycsuper
09/01
0
0
余弦定理的应用:基于文字的文本相似度计算

最近由于工作项目,需要判断两个txt文本是否相似,于是开始在网上找资料研究,因为在程序中会把文本转换成String再做比较,所以最开始找到了这篇关于 距离编辑算法 Blog写的非常好,受益匪浅...

大数据之路
2013/03/24
4.4K
5
TF-IDF与余弦相似性的应用(二):找出相似文章

上一次,我用TF-IDF算法自动提取关键词。 今天,我们再来研究另一个相关的问题。有些时候,除了找到关键词,我们还希望找到与原文章相似的其他文章。比如,"Google新闻"在主新闻下方,还提供...

阮一峰
2013/03/21
0
0
余弦距离、欧氏距离和杰卡德(Jaccard)相似性度量的比较

1、余弦距离 余弦距离,也称为余弦相似度,是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。 向量,是多维空间中有方向的线段,如果两个向量的方向一致,即夹角接近...

u011734144
2018/05/09
0
0
TF-IDF与余弦相似性的应用(二):找出相似文章

转自:http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html 上一次,我用 TF-IDF 算法自动提取关键词。 今天,我们再来研究另一个相关的问题。有些时候,除了找到关键词,我们还...

泳泳啊泳泳
2018/01/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

DevOps是如何实现效率的提升?

随着企业业务对软件系统日益依赖,IT管理与研发模式也随之对“敏态”模式产生了需求,也就是今天时常提起的DevOps。提升效率,是DevOps实践的核心内容之一。就让我们来一起从软件生命周期的业...

嘉为科技
6分钟前
2
0
总结:linux目录之proc

我们系统大部分的基础数据采集,其实就是读取proc目录下的文件,并解析获取数据的过程。 1、如cpu利用率:直接cat /proc/cpuinfo命令,然后获取输出内容,并解析里面的数据,如cpu核数等; ...

浮躁的码农
8分钟前
2
0
比原Bapp红包应用

喜迎国庆期间,比原链在自己的移动端钱包Bycoin(下载地址)和google插件钱byone中推出了红包应用,在国庆期间深受大家好评。 那我们今天就来大概介绍一下比原红包,以及基于比原链开发dapp应用...

比原链Bytom
9分钟前
2
0
Linux中没有rc.local文件的解决方法

Linux中没有rc.local文件的解决方法是什么呢?这应该是很多工程师比较头疼的问题,下面就给大家例举几个解决办法。 比较新的Linux发行版已经没有rc.local文件了。因为已经将其服务化了。 解决...

xiangyunyan
10分钟前
2
0
数据中台在阿里巴巴集团内部的实践情况

作者:品鉴 数据中台门在阿里巴巴集团干什么的,由哪个部门掌管?数据中台在阿里巴巴的主要作用是什么呢?外面吹嘘这么神秘的数据中台在阿里实践的如何呢?今天小编正好要采访数据技术及产品...

阿里云官方博客
10分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部