项目备忘

[/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.找视频的相关新闻和新闻的相关视频主要是通过计算相似性的