基于TF/IDF的聚类算法原理

 

一.TF/IDF描述单个term与特定document的相关性
TF(Term Frequency): 表示一个term与某个document的相关性。
公式为这个term在document中出现的次数除以该document中所有term出现的总次数.

IDF(Inverse Document Frequency)表示一个term表示document的主题的权重大小。主要是通过包含了该term的docuement的数量和docuement set的总数量来比较的。出现的次数越多,权重越小。

   公式是log(D/Dt)   D是docuemnt set的总数量, Dt是包含了该term的document的总数。

这样,根据关键字k1,k2,k3进行搜索结果的相关性就变成TF1*IDF1 + TF2*IDF2 + TF3*IDF3。

比如document1的term总量为1000,k1,k2,k3在document1出现的次数是100,200,50。包含了k1, k2, k3的docuement总量分别是1000, 10000,5000。document set的总量为10000。
TF1 = 100/1000 = 0.1
TF2 = 200/1000 = 0.2
TF3 = 50/1000 = 0.05
IDF1 = log(10000/1000) = log(10) = 2.3
IDF2 = log(10000/100000) = log(1) = 0;
IDF3 = log(10000/5000) = log(2) = 0.69
这样关键字k1,k2,k3与docuement1的相关性= 0.1*2.3 + 0.2*0 + 0.05*0.69 = 0.2645
其中k1比k3的比重在document1要大,k2的比重是0.

TF/IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵(Kullback-Leibler Divergence).

二.用TF/IDF来描述document的相似性。
假如document1和document2的term的TF/IDF分别是t11,t12,t13,…t1n和t21,t22,t23,…,t2n.他们之间的相似性可以用余弦定理来表示。则:
cos(d1,d2) = d1和d2的内积/(d1的长度*d2的长度) = (t11*t21 + t12*t22 + t13*t23 + … + t1n*t2n)/(|d1|*|d2|).
d1 = sqrt(t11*t11 + t12*t12 + t13*t13 + … + t1n*t1n);
夹角越大,相似性越大。为1则表示d1和d2一致。

详细解释情况吴军的 《数学之美 系列九 — 如何确定网页和查询的相关性》 和 《数学之美系列 12 – 余弦定理和新闻的分类》

[转载][ZZ]经典的机器学习方面源代码库

今天给大家介绍一下经典的开源机器学习软件:

编程语言:搞实验个人认为当然matlab最灵活了(但是正版很贵),但是更为前途的是python(numpy+scipy+matplotlib)和C/C++,这样组合既可搞研究,也可搞商业开发,易用性不比matlab差,功能组合更为强大,个人认为,当然R和java也不错.

1.机器学习开源软件网(收录了各种机器学习的各种编程语言学术与商业的开源软件)

http://mloss.org

2 偶尔找到的机器学习资源网:(也非常全,1和2基本收录了所有ML的经典开源软件了)

http://www.dmoz.org/Computers/Artificial_Intelligence/Machine_Learning/Software/

3 libsvm (支持向量机界最牛的,不用多说了,台湾大学的林教授的杰作)

http://www.csie.ntu.edu.tw/~cjlin/libsvm/

4 WEKA (基于java的机器学习算法最全面最易用的开源软件)

http://www.cs.waikato.ac.nz/ml/weka/

5 scikit (本人最喜欢的一个基于python的机器学习软件,代码写得非常好,而且官方的文档非常全,所有都有例子,算法也齐全,开发也活跃
,强烈推荐给大家用)

http://scikit-learn.org/stable/

6 OpenCv(最牛的开源计算机视觉库了,前途无可限量,做图像处理与模式识别的一定要用,总不能整天抱着matlab做实验和工业界脱节吧,但是有一定难度)

http://opencv.willowgarage.com/wiki/

7 Orange (基于c++和python接口的机器学习软件,界面漂亮,调用方便,可以同时学习C++和python,还有可视化的功能,)

http://orange.biolab.si/

8 Mallet (基于JAVA实现的机器学习库,主要用于自然语言处理方面,特色是马尔可夫模型和随机域做得好,可和WEKA互补)

http://mallet.cs.umass.edu/

9 NLTK(PYTHON的自然处理开源库,非常易用,也强大,还有几本orelly的经典教程)

http://nltk.org/

10 lucene(基于java的包括nutch,solr,hadoop,mahout等全套,是做信息检索和搜索引擎的同志们必学的开源软件了,学JAVA的必学)

http://lucene.apache.org/

 

转载地址:http://www.cnblogs.com/kshenf/archive/2012/06/14/2548708.html

褪去华衣 裸视学习 探讨系列(机器学习全讲解)

写在最前:

本专题经 @老师木 同意, 特收录“老湿”对AI/ML的一些独到见解。如果非要问我为什么要特别收录这几篇文章,回答:个人认为,他的大部分见解已经并肩甚至超过了该领域的一般教授。如果你再八卦一下问这个专题为什么叫“褪去华衣 裸视学习”,答曰:这些见解一定程度上褪去了AI/ML的神秘色彩,可以让我们更客观的看待这一学科。

专题分为六个篇章:

1)机器学习 基础篇

褪去华衣 裸视学习 之 高斯分布

褪去华衣 裸视学习 之 sigmod函数

褪去华衣 裸视学习 之 关于‘基’

褪去华衣 裸视学习 之 随机数学

褪去华衣 裸视学习 之 小赞deep learning

2)机器学习 进阶篇

褪去华衣 裸视学习 之 有监督学习

褪去华衣 裸视学习 之 线性分类器

褪去华衣 裸视学习 之 SVM神话

褪去华衣 裸视学习 之 无监督学习

褪去华衣 裸视学习 之 概率图

3)机器学习 实战篇

褪去华衣 裸视学习 之 人机对话小思路

褪去华衣 裸视学习 之 Marr 视觉计算理论

褪去华衣 裸视学习 之 小议无监督分词

褪去华衣 裸视学习 之 博弈论与广告

4)机器学习 反思篇

褪去华衣 裸视学习 之 《机器学习那点事儿》解读

褪去华衣 裸视学习 之 李国杰院士大数据一文的不同意见

褪去华衣 裸视学习 之 机器学习无用论

褪去华衣 裸视学习 之 机器学习有点用

5)机器学习 方法论

褪去华衣 裸视学习 之 规则与统计

褪去华衣 裸视学习 之 优质数据

褪去华衣 裸视学习 之 跨界的机器学习

褪去华衣 裸视学习 之 概率与统计区别

6)机器学习 番外篇

褪去华衣 裸视学习 之 产品设计

褪去华衣 裸视学习 之 学术界

褪去华衣 裸视学习 之 如何学习

褪去华衣 裸视学习 之 机器学习教材

转载自: http://www.guzili.com/?p=45204

分类器评价、混淆矩阵与ROC曲线

假定你基于贝叶斯理论、神经网络或其他技术建立了自己的分类器。你如何得知自己是否干了一项漂亮的工作呢?你如何得知是否可以把自己的智能模块应用 于生产环境中,并获得同行的景仰以及老板的赞赏呢?评估分类器和创建它同样重要,如同在销售会议上,你会听到大量的夸大之词,但没有评估这就是一堆废话。 本节的目的在于帮助你评估自己的分类器,如果你是一个开发者或产品经理, 这会帮助你理解第三方产品的合理与否。

“没有人知道所有的事情”、“人都会犯错”。这些箴言在计算机领域也有其对应的版本:没有一个分类器可以解决所有的问题,也没有一个分类器在所有的 数据集中都能良好地工作。在分类范畴中的学习技术属于有监督学习,“有监督”意味着分类器会利用已知的分类结果历经一个训练的过程,通过这种监督,它会尝 试着学习蕴含在训练数据集中的信息。你可以想象得到,训练数据集与你部署环境中实际数据的相关性会是分类是否成功的关键。

以上两段文字摘自我和陈钢同学翻译、即将出版的《智能web算法》中讲述分类器的一章。

作者试图说明一个问题:分类器的评估与分类器本身同样重要。评估分类器可信度的一个基本工具是混淆矩阵(confusion matrix)。以一个二分类问题作为研究对象,图1的混淆矩阵显示了一个分类器可能会遭遇的所有情况,其中列(positive/negative)对 应于实例实际所属的类别,行(true/false)表示分类的正确与否(注,这里的混淆矩阵的结构跟[2]中的定义并不一样,但实际说明的问题是一致 的)。

 

图1 混淆矩阵图1 混淆矩阵

其中FP和FN就是我们常说的第一类错误与第二类错误,以这四个基本指标可以衍生出多个分类器评价指标,如图2。还有下文将会用到的TPR=TP/P=TP/(TP+FN)

 

图2 指标定义图2 指标定义

我们常用的就是分类器的精确度(accuracy),在某些如推荐或信息获取领域还会组合使用precision-recall作为评价指标。因为 你用于训练分类器的样本本身就是总体的一个抽样,所以这些指标的数值也仅仅是一种统计上的反映,如果你做多次抽样训练,跟别的随机变量一样,它一样会有期 望、方差、置信区间这些概念。理论上说,训练样本量越大,你得到的这些指标的可信度就越高(即它们以某个概率落在的置信区间越窄)。不幸的是,实际中你未 必会有那么多的样本,所以机器学习工作者设计出很多种方法来应对数据量不足情况下分类器的训练与评估,如k步交叉检验、留1法、boostrap等等。

以上这些都属于静态的指标,当正负样本不平衡时它会存在着严重的问题。极端情况下比如正负样本比例为1:99(这在有些领域并不少见),那么一个基 准分类器只要把所有样本都判为负,它就拥有了99%的精确度,但这时的评价指标是不具有参考价值的。另外就是,现代分类器很多都不是简单地给出一个0或1 的分类判定,而是给出一个分类的倾向程度,比如贝叶斯分类器输出的分类概率。对于这些分类器,当你取不同阈值,就可以得到不同的分类结果及分类器评价指 标,依此人们又发明出来ROC曲线以及AUC(曲线包围面积)指标来衡量分类器的总体可信度。

ROC曲线最初源于20世纪70年代的信号检测理论,描述的是分类混淆矩阵中FPR-TPR两个量之间的相对变化情况。如果二元分类器输出的是对正 样本的一个分类概率值,当取不同阈值时会得到不同的混淆矩阵,对应于ROC曲线上的一个点。那么ROC曲线就反映了FPR与TPR之间权衡的情况,通俗地 来说,即在TPR随着FPR递增的情况下,谁增长得更快,快多少的问题。TPR增长得越快,曲线越往上屈,AUC就越大,反映了模型的分类性能就越好。当 正负样本不平衡时,这种模型评价方式比起一般的精确度评价方式的好处尤其显著。一个典型的ROC曲线如图3所示(来自[2])

 

图3 ROC曲线图3 ROC曲线

[1] 《智能web算法》
[2] http://en.wikipedia.org/wiki/Receiver_operating_characteristic

交叉验证

以下简称交叉验证(Cross Validation)为CV.CV是用来验证分类器的性能一种统计分析方法,基本思想是把在某种意义下将原始数据(dataset)进行分组,一部分做 为训练集(train set),另一部分做为验证集(validation set),首先用训练集对分类器进行训练,在利用验证集来测试训练得到的模型(model),以此来做为评价分类器的性能指标.常见CV的方法如下:

1).Hold-Out Method

将原始数据随机分为两组,一组做为训练集,一组做为验证集,利用训练集训练分类器,然后利用验证集验证模型,记录最后的分类准确率为此Hold- OutMethod下分类器的性能指标.此种方法的好处的处理简单,只需随机把原始数据分为两组即可,其实严格意义来说Hold-Out Method并不能算是CV,因为这种方法没有达到交叉的思想,由于是随机的将原始数据分组,所以最后验证集分类准确率的高低与原始数据的分组有很大的关 系,所以这种方法得到的结果其实并不具有说服性.

2).K-fold Cross Validation(记为K-CV)

将原始数据分成K组(一般是均分),将每个子集数据分别做一次验证集,其余的K-1组子集数据作为训练集,这样会得到K个模型,用这K个模型最终的验证集 的分类准确率的平均数作为此K-CV下分类器的性能指标.K一般大于等于2,实际操作时一般从3开始取,只有在原始数据集合数据量小的时候才会尝试取 2.K-CV可以有效的避免过学习以及欠学习状态的发生,最后得到的结果也比较具有说服性.

3).Leave-One-Out Cross Validation(记为LOO-CV)

如果设原始数据有N个样本,那么LOO-CV就是N-CV,即每个样本单独作为验证集,其余的N-1个样本作为训练集,所以LOO-CV会得到N个模型, 用这N个模型最终的验证集的分类准确率的平均数作为此下LOO-CV分类器的性能指标.相比于前面的K-CV,LOO-CV有两个明显的优点:


a.每一回合中几乎所有的样本皆用于训练模型,因此最接近原始样本的分布,这样评估所得的结果比较可靠。


b.实验过程中没有随机因素会影响实验数据,确保实验过程是可以被复制的。

但LOO-CV的缺点则是计算成本高,因为需要建立的模型数量与原始数据样本数量相同,当原始数据样本数量相当多时,LOO-CV在实作上便有困难几乎就是不显示,除非每次训练分类器得到模型的速度很快,或是可以用并行化计算减少计算所需的时间.

Matlab SVM库函数的使用(libsvm)

在上篇文章中,对于SVM的原理,Matlab中libSVM的时候介绍的都非常的详细。

这篇文章是上篇文章中包含的一个很小很简单的部分。目的是方便以后我自己的查阅~~    ^_^

在以后使用libsvm的时候,不想再细细查阅SVM的理论,libSVM非常详细的使用,只是想要很快的对libsvm上手,用它来很快的做开发,那么这篇文章的目的就在这里。

在matlab中输入svmtrain,确定,给出了详细的说明。

>> svmtrain
Usage: model = svmtrain(training_label_vector, training_instance_matrix, ‘libsvm_options’);
libsvm_options:
-s svm_type : set type of SVM (default 0)
0 — C-SVC
1 — nu-SVC
2 — one-class SVM
3 — epsilon-SVR
4 — nu-SVR
-t kernel_type : set type of kernel function (default 2)
0 — linear: u’*v
1 — polynomial: (gamma*u’*v + coef0)^degree
2 — radial basis function: exp(-gamma*|u-v|^2)
3 — sigmoid: tanh(gamma*u’*v + coef0)
4 — precomputed kernel (kernel values in training_instance_matrix)
-d degree : set degree in kernel function (default 3)
-g gamma : set gamma in kernel function (default 1/num_features)
-r coef0 : set coef0 in kernel function (default 0)
-c cost : set the parameter C of C-SVC, epsilon-SVR, and nu-SVR (default 1)
-n nu : set the parameter nu of nu-SVC, one-class SVM, and nu-SVR (default 0.5)
-p epsilon : set the epsilon in loss function of epsilon-SVR (default 0.1)
-m cachesize : set cache memory size in MB (default 100)
-e epsilon : set tolerance of termination criterion (default 0.001)
-h shrinking : whether to use the shrinking heuristics, 0 or 1 (default 1)
-b probability_estimates : whether to train a SVC or SVR model for probability estimates, 0 or 1 (default 0)
-wi weight : set the parameter C of class i to weight*C, for C-SVC (default 1)
-v n : n-fold cross validation mode
-q : quiet mode (no outputs)

ans =

[]

>> model = svmtrain(training_label_vector, training_instance_matrix, ‘libsvm_options’);

svmtrain有三个参数,一个返回值。

返回的就是由训练得到的,在预测的时候将要用到的svm模型。

三个参数:

1. training_label_vector : 训练的标签向量,也就是一系列的-1,1组成的向量,-1表示训练集中该行放的负例的特征向量,

1表示在训练集中该行存放的是正例的特征向量。     向量是 m*1 维度 ( 假设训练集中一共有m个训练样本  )

2. training_instance_matrix : 训练集的样本的特征向量组成的特征矩阵。m*n维度。 m表示训练集中一共有m个样本。

n表示每一个样本使用一个n维的特征向量来表示。所以,在该特征向量矩阵中,每一行就表示一个样本的特征向量。

training_instance_matrix的顺序应该是和training_label_vector严格的保持一致的。

3. libsvm_options :  这是对建立的svm模型的一些参数的设置的选项。

也可以不写该参数而采用默认值。但是为了分类预测准确的目的一般还是需要填写这个选项的,并且根据对这个选项的调节来实现“svm参数调优”

常用到的参数有:
-s svm_type : set type of SVM (default 0)
0 -- C-SVC
1 -- nu-SVC
2 -- one-class SVM
3 -- epsilon-SVR
4 -- nu-SVR
-t kernel_type : set type of kernel function (default 2)
0 -- linear: u'*v
1 -- polynomial: (gamma*u'*v + coef0)^degree
2 -- radial basis function: exp(-gamma*|u-v|^2)
3 -- sigmoid: tanh(gamma*u'*v + coef0)
4 -- precomputed kernel (kernel values in training_instance_matrix)
-d degree : set degree in kernel function (default 3)
-g gamma : set gamma in kernel function (default 1/num_features)

-v n : n-fold cross validation mode
其中-s用来选定svm的类别,是用作分类器,还是做回归等,  用作分类器的话就设置 -s 0 或者省略,默认为-s 0

-t 用来设置svm的核函数,

-t 0 表示选用线性核函数

-t 1 表示选用多项式核函数

-t 2 表示选用径向基(高斯)核函数

-t  3 表示选用sigmoid核函数

-t 4 表示选用自定义核函数。 这个时候可以自己定义核函数,并且把核函数计算出来的核矩阵传入svmtrain,svmpredict中来进行训练和预测.

-d 用来设置多项式核函数的幂次。 由svmtrain的help文档中,我们就可以很轻易的看出,degree这个变量只有在-t 1多项式核函数的函数式中才出现,故而只有在-t 1 选用多项式核函数的时候-d 这个选项才有意义。 因为多项式核函数也是比较常用的核函数,故而-d选项还是比较常常用到,-d 3表示多项式核函数的幂次为3

-g 用来设置在 多项式函数、径向基核函数、sigmoid核函数中的gammar系数。 默认这个值选用1.

-v 用来设置在交叉验证的时候,fold的次数。

 

具体每一个参数设置为多少合适,往往需要经过参数选优过程之后才会知道。参数选优过程的本质,其实就是试一试啦~~哈哈。就是试一试这个参数正确率多少,变一下,把参数设置成那样,正确率是多少,然后选择一套正确率最高的参数。这样。呵呵。

 

而预测过程使用函数:svmpredict

直接在matlab中输入svmpredict 确定,给出了非常详细易懂的说明:

>> svmpredict
Usage: [predicted_label, accuracy, decision_values/prob_estimates] = svmpredict(testing_label_vector, testing_instance_matrix, model, 'libsvm_options')
Parameters:
model: SVM model structure from svmtrain.
libsvm_options:
-b probability_estimates: whether to predict probability estimates, 0 or 1 (default 0); one-class SVM not supported yet
Returns:
predicted_label: SVM prediction output vector.
accuracy: a vector with accuracy, mean squared error, squared correlation coefficient.
prob_estimates: If selected, probability estimate vector.

ans =

[]

>>

先说svmpredict的四个参数:testing_label_vector,testing_instance_matrix,model,’libsvm_options’

通常使用前三个参数就可以了。这篇文章为了快速入手而写,所以只介绍一下前三个参数,至于第四个参数的使用,查看matlab的help就可以知道了。

1.testing_label_vector,这个参数用于在预测的时候同时得到准确的预测正确率。 如果需要预测的测试集是事先就知道分类结果的,这种情况下往往是用来评测算法的性能或者评测分类器的性能的时候,这时候,这个序列中是对应于第二个参数testing_instance_matrix对应的分类label(-1,1的序列)。 如果不是用于评测算法或者分类器的性能,而是用于实际的预测的场合,那么这个参数的赋值是什么都无所谓的,但是行数应该和第二个参数testing_instance_matrix保持一致。

2.testing_instance_matrix:测试样本矩阵。其实就是测试样本的特征向量组成的矩阵。m*n维。表示m个样本,每一个样本表示成一个n维矩阵。矩阵的每一行表示的就是一个样本的特征向量。

3.model:进行预测时使用的svm model。这个model无疑是使用前面的函数svmtrain得到的。

svmpredict有三个返回值:

[predicted_label, accuracy, decision_values/prob_estimates]

1.predicted_label :返回一个-1,1的序列,该序列的行数与输入参数testing_instance_matrix的行数相同,每一行为1或者-1.表示的svm预测的改行对应的样本的分类结果,属于正类1,或者负类-1.

2.accuracy: 当输入的第一个参数testing_label_vector是先验的测试样本的正确分类的时候,这个返回值accuracy就是svm在这次预测中的正确率。

3.decision_values:我们知道svm分类过程本质是一个函数取优的过程,效果就是使得两个类别距离分类平面之间的margin最大化。

svm本质是优化问题

那么这个 decision_values 是一个m*1的向量,也就是行数与输入的测试样本数目相同。每一行的值对应的也就是这个测试样本在上边的这个优化函数中的目标函数的值了。从Predicted_label我们得到了每一个测试样本的分类结果(其实分类依据就是这个目标函数的值咯…),但是只有predict_labels我们不知道那个测试样本判别的有把握,哪些判别的不大有把握,也就是置信度的问题。 decision_values就给出了置信度。【应该decision_values和优化函数的目标函数不完全相同,希望读者能够斧正,并留言讨论。谢谢】