[/color]待,[color=red]svm 分类和knn分类
svm:
http://lovejuan1314.iteye.com/blog/647920点击这个博客右边的文本分类就有完整的十章svm的东东
1)
Vapnik于1995年首先提出的,解决小样本、非线性及高维模式识别中表现出许多特有的优势
SVM正是这样一种努力最小化结构风险的算法。
SVM其他的特点就比较容易理解了。
小样本,并不是说样本的绝对数量少(实际上,对任何算法来说,更多的样本几乎总是能带来更好的效果),而是说与问题的复杂度比起来,SVM算法要求的样本数是相对比较少的。
非线性,是指SVM擅长应付样本数据线性不可分的情况,
主要通过核函数技术(主要是把非线性的东西变为大部分线性)和松弛变量(也有人叫惩罚变量)(主要是对一些偏离大部分线性的点进行惩罚,看这些点的权重大不大)来实现,这一部分是SVM的精髓,以后会详细讨论。多说一句,关于文本分类这个问题究竟是不是线性可分的,尚没有定论,因此不能简单的认为它是线性可分的而作简化处理,在水落石出之前,只好先当它是线性不可分的(反正线性可分也不过是线性不可分的一种特例而已,我们向来不怕方法过于通用)。
高维模式识别是指
样本维数很高,例如文本的向量表示,如果没有经过另一系列文章(《文本分类入门》)中提到过的降维处理,出现几万维的情况很正常,其他算法基本就没有能力应付了,SVM却可以,主要是因为SVM 产生的分类器很简洁,用到的样本信息很少(仅仅用到那些称之为“支持向量”的样本,此为后话),使得即使样本维数很高,也不会给存储和计算带来大麻烦(相对照而言,kNN算法在分类时就要用到所有样本,样本数巨大,每个样本维数再一高,这日子就没法过了……)。
一般的,如果一个线性函数能够将样本完全正确的分开,就称这些数据是
线性可分的,否则称为
非线性可分的。
什么叫线性函数呢?在一维空间里就是一个点,在二维空间里就是一条直线,三维空间里就是一个平面,可以如此想象下去,如果不关注空间的维数,这种线性函数还有一个统一的名称——
超平面(Hyper Plane)!
几何间隔所表示的正是点到超平面的欧氏距离。同样可以定义一个点的集合(就是
一组样本)到某个超平面的距离为此集合中离超平面最近的点的距离。
SVM的目标: 因此最大化几何间隔成了我们训练阶段的目标
核函数的作用是:低维空间映射到高维空间,这样在低维中间内不线性的分割到高维空间内就变为了线性分割了。
如果使用核函数向高维空间映射后,问题仍然是线性不可分的,那怎么办? 引入了松弛变量
knn分类法:KNN法(K-Nearest Neighbor)
kNN(k Nearest Neighbors)算法又叫k最临近方法, 总体来说kNN算法是相对比较容易理解的算法之一,假设每一个类包含多个
样本数据,而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类, kNN就是计算每个样本数据到待分类数据的距离,取和待分类数据最近的k各样本数据,那么这个k个样本数据中哪个类别的样本数据占多数,则待分类数据就属于该类别。
因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
该方法的不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。另外还有一种Reverse KNN法,能降低KNN算法的计算复杂度,提高分类的效率。
该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
我们的方法类似与knn方法,只不过是每个类只有一个样本
1. TP_StoreVideoTfIdfTask
首先和字典绑定,进行切词分词,分词的策略:首先根据句子结束的标点符号来分句。然后再对每个句子进行分词,分词首先根据位置一个一个移动,是根据字典来判断字符串是不是存在于字典的word(这里用到了hashtable增加速度),继续找下去,直到找到最大的字符串word(限定了一个最大值,如果大过这个就算了,按照之前找到的word的位置切分)的那个为止,一个个这样移动。 可以用lucene
tf: term frequence: tf = 单词在这个文本中出现的次数/这个文本中的单词的总的个数
idf: inverse document frequence: idf = log(所有文档的总数/这个单词在多少文档中出现)
2.TP_ClassifyVideosTask
首先装载一个词频(freq)文件,里面有每个单词在每个类别(1-13)出现的doc数
格式如下
单词 类别 在这类出现的doc数
啊哈哈 1 100
啊哈哈 2 130
.....
啊哈哈 13 126
根据这个词频文件就可以计算每个类别的tf-idf的一个向量。
tf = 该词在这类中出现的doc数/这个类别中所有的doc数
idf = log(
所有类别中的doc数/这个单词在
所有类别中出现的doc数)
然后把待分类doc的tf-idf向量和每类进行比较,比较之前先sort一下,进行cos距离的计算。
(如果两个向量中有相同的单词,则tfidf的weight相乘)/sqrt(doc的tfidf)*sqrt(类别的tfidf)
3.TP_ClusterVideosTask
首先一个小小的技巧,往往时间上相近的新闻往往是相关的,时间上相差太远的新闻往往是不相关的,所以我们分为周聚类和月聚类。
总体的思想是这样的,一开始我们初始化每个文档构成自己的一类。然后后面慢慢地根据两个类别的相似性进行合并类别,要设定一个参数clusterSimilarityThreshlod,这个参数的意思是如果两个类别的相似性大于这个值,则这两个类别合并。一个简单的合并策略是把文档数少的类别加入到文档数大的类别中来。具体怎样对两个比较相似的类进行合并呢。思想是这样的,如果两篇文档它们的相似性比较高的话,那这两篇文档所属的两个类的相似性也比较高。两个类的相似性可以表示为这两个类的文档的相似性的平均值。
具体是这样做的,首先拿到要求聚类的所有文档的tf-idf向量,然后计算文档中两两的相似性,如果这个相似性的值>一个阈值的话,就把(两篇文档的id和他的相似性组成一个struct)加入到一个vector中来,然后根据相似性的大小从大到小对这个vector进行排序。
对这个vector进行遍历,拿到每个元素,它的两个doc的id,然后查看这两个doc各属于哪一类,然后计算这两个类别的相似性(这里主要是根据这两个类别的文档间相似性的平均值),如果连个类别的相似性大于一定阈值的话,我们就合并这两个类别。
4.人名地名抽取主要是看字典中这个单词的属性是什么
5.摘要生成主要是拿出最大tf_idf的句子。
6.topic:主要是拿出最大tf-idf的单词
7.找视频的相关新闻和新闻的相关视频主要是通过计算相似性的
分享到:
相关推荐
项目备忘录模板.doc
项目工程备忘录
博思智联均瑶集团项目备忘录均瑶集团1227.pdf
项目执行过程中,往往遇到因为各种环境因素和条件制约而引起的变更情况,此事需要做好变更后的版本记录工作,做到变更后有据可查。
Notebook是集Word强大的文字处理功能和MATLAB丰富的数学运算能力于一身的工作环境,其功能包括文字处理、科学计算、图形演示和工程设计等,其主要应用于文件说明、记录MATLAB操作、项目备忘录、文档演示等场合。...
基于Android的手机备忘录软件设计.doc
Android开源项目第一篇——个性化控件(View)篇Android开源项目第二篇——工具库篇Android开源项目第三篇——优秀项目篇Android开源项目
软件实施备忘录--在IT行业,特别是管理软件实施行业能够成为一个成功的项目经理是非常困难的一件事情,一个成功的IT经理,被要求熟悉计算机软硬件知识,精通企业业务背景,拥有良好的沟通技巧和说服能力,当然在项目...
微信小程序项目实例——备忘录 项目是一个备忘录,拥有记录文字、计时和提醒的基本功能 项目只有一个页面,整体简约便捷
XX项目进展备忘录.doc
微信小程序项目实例——备忘录小程序项目实例源码(95分以上课设大作业项目).zip 高分必过项目,需要小程序项目实战和课程设计大作业的可以放心下载,代码完整下载即用,无需修改确保可以运行。 微信小程序项目...
这是一个基于Android的手机备忘录软件设计,很有参考价值,有需要的志同者,不妨下载!
项目投资备忘录
安全备忘单翻译项目 _
这是我刚学android时自己写的一个例子,主要用到了Activity,ContentProvider, BroadcastReceiver三大组件,还有涉及其他知识,我认为刚学android的话挺不错的例子
毕业设计基于JavaWeb实现的一个备忘录系统项目源码。难度适中,新手自己可操作 备忘录 介绍 后端部分基于Servlet、Jdbc实现. 前端部分基于Layui、jqury实现。 一个简单的前后端分离Demo,前后端交互JSON数据格式 ...
设计和实现一个类似个人备忘录的 Android APP ,数据库采用 SQLite (也可以直接访问 Web 端 MySQL 数据库、或提供 Web 接口访问 MySQL 数据库)。 1.用户注册和登录(这类 APP 一般面对个人,用户不需要分类别); ...
微信小程序项目源码毕业设计期末大作业课程设计前端源码 微信小程序项目源码毕业设计期末大作业课程设计前端源码 微信小程序项目源码毕业设计期末大作业课程设计前端源码 微信小程序项目源码毕业设计期末大作业课程...
1-开工申请表.docx 10-问题跟踪表.docx 12-项目周报.docx 13-项目月报.doc 14 - 数据库(顶层)设计说明(DBDD).doc ...41-项目备忘录.doc 42-培训记录.doc 43-系统运维方案.docx 44-试运行报告.docx 46-用户使用意见.doc
微信小程序项目实例——备忘录小程序源码(95分以上课设大作业项目).zip 高分必过项目,需要小程序项目实战和课程设计的可以放心下载,代码完整下载即用,无需修改确保可以运行。 微信小程序项目实例——备忘录小...