基于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 – 余弦定理和新闻的分类》

发表评论

电子邮件地址不会被公开。 必填项已用*标注