taoCMS是基于php+sqlite/mysql的国内最小(100Kb左右)的功能完善、开源免费的CMS管理系统

PHP处理海量样本相似度聚类算法

2017-02-20

catalogue

1. TF-IDF
2. 基于空间向量的余弦算法
3. 最长公共子序列
4. 最小编辑距离算法
5. similar_text
6. local sensitive hash 局部非敏感哈希
7. SSDEEP Hash
8. K-means聚类算法
9. 二分K-means算法

 

1. TF-IDF

Relevant Link:

http://qianxunniao.iteye.com/blog/1831780

 

2. 基于空间向量的余弦算法

将分词后的词频作为向量分量,将每个文件转化为一个向量,通过计算向量之间的余弦值,本质上是在计算不同文本的词频的相似度

 

3. 最长公共子序列
该算法的最大缺陷是计算CPU消耗较大

1. 将两个字符串分别以行和列组成矩阵
2. 计算每个节点行列字符是否相同,如相同则为1。
3. 通过找出值为1的最长对角线即可得到最长公共子串 

为进一步提升该算法,我们可以将字符相同节点的值加上左上角(d[i-1,j-1])的值,这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串

Relevant Link:

https://segmentfault.com/q/1010000000738974
http://www.speedphp.com/thread-4840-1-1.html
http://www.cnblogs.com/liangxiaxu/archive/2012/05/05/2484972.html

 

4. 最小编辑距离算法

设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大

1. 对两部分文本进行处理,将所有的非文本字符替换为分段标记"#"
2. 较长文本作为基准文本,遍历分段之后的短文本,发现长文本包含短文本子句后在长本文中移除,未发现匹配的字句累加长度
3. 比较剩余文本长度与两段文本长度和,其比值为不匹配比率

PHP中的levenshtein()函数已经实现了该功能

Relevant Link:

http://php.net/manual/zh/function.levenshtein.php

 

5. similar_text

Relevant Link:

http://php.net/manual/zh/function.metaphone.php
http://php.net/manual/zh/function.soundex.php
http://php.net/manual/zh/function.similar-text.php 

 

6. local sensitive hash 局部非敏感哈希

在对海量样本进行大规模相似度聚类运算的时候,需要首要考虑的问题是计算耗时。为此我们需要一种应对于海量数据场景的去重方案,可以采取一种叫做 local sensitive hash 局部敏感哈希 的算法,该算法模型可以把文档降维到hash数字,数字两两计算运算量要小很多(google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别)。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》

0x1: 基本概念

1. 分词
把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1 ~ 5)。比如
"美国51区雇员称内部有9架飞碟,曾看见灰色外星人" ==> 分词后为 
"美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)": 括号里是代表单词在整个句子里重要程度,数字越大越重要

2. hash
通过hash算法把每个词变成hash值,比如
"美国"通过hash算法计算为 100101
"51区"通过hash算法计算为 101011
这样我们的字符串就变成了一串串数字,下一步我们要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时 

3. 加权
通过2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如
"美国"的hash值为"100101",通过加权计算为"4 -4 -4 4 -4 4"
"51区"的hash值为"101011",通过加权计算为"5 -5 5 -5 5 5"

4. 合并
把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 
"美国""4 -4 -4 4 -4 4"
"51区""5 -5 5 -5 5 5"
把每一位进行累加,"4+5 -4+-5 -4+5 4+-5 -4+5 4+5" ==》 "9 -9 1 -1 1 9"(这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加)

5. 降维
把4步算出来的"9 -9 1 -1 1 9"变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为: "1 0 1 0 1 1"
复制代码

整个过程图为

Relevant Link:

复制代码
http://blog.jobbole.com/46839/
http://jacoxu.com/?p=366
https://github.com/yanyiwu/simhash
https://github.com/leonsim/simhash
https://github.com/zhujun1980/simhash
https://github.com/Sin30/simhash-demo/blob/master/simhash.php
https://github.com/tgalopin/SimHashPhp
http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf
复制代码

 

7. SSDEEP Hash

SSDEEP Hash的思想和MD5/SHAX正好相反,是一种局部不敏感Hash算法,通过对待检测文本的分段切割,综合加权得到一个降维的模糊化Hash。能够对小范围的修改有较好的容错性

0x1: 改善SSDEEP Hash效果

1、 对不满32byte的文本,填充Padding到32bytes

Relevant Link:

 

8. K-means聚类算法


1. 使用K-means(K近邻)算法对文本进行分类,首先要面对的问题是,如何将文本转化为可度量距离的"点特征集合",一个可行的方法是将文本提取为一个词频向量(高维空间的坐标点),这样就将文本转化为一个点
2. 二维坐标点的X, Y 坐标,其实是一种向量,是一种数学抽象。现实世界中很多属性是可以抽象成向量的,比如,我们的年龄,我们的喜好,我们的商品,等等,能抽象成向量的目的就是可以让计算机知道某两个属性间的距离。如:我们认为,18岁的人离24岁的人的距离要比离12岁的距离要近,鞋子这个商品离衣服这个商品的距离要比电脑要近,等等
3. 只要能把现实世界的物体的属性抽象成向量,就可以用K-Means算法来归类了
4. 所以使用k-means进行样本分类的难点在于如何提取feature,构成一个多维的坐标点空间,并带入模型运算

聚类属于无监督学习,以往的回归、朴素贝叶斯、SVM等都是有类别标签y的,也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y,只有特征x,比如假设宇宙中的星星可以表示成三维空间中的点集。聚类的目的是找到每个样本x潜在的类别y,并将同类别y的样本x放在一起。比如上面的星星,聚类后结果是一个个星团,星团里面的点相互距离比较近,星团间的星星距离就比较远了。

在聚类问题中,给我们的训练样本是,每个,没有了y。

K-means算法是将样本聚类成k个簇(cluster),具体算法描述如下

1、 随机选取k个聚类质心点(cluster centroids)为。

2、 重复下面过程直到收敛 {

               对于每一个样例i,计算其应该属于的类

               

               对于每一个类j,重新计算该类的质心

               

}

K是我们事先给定的聚类数,代表样例i与k个类中距离最近的那个类,的值是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测,拿星团模型来解释就是要将所有的星星聚成k个星团,首先随机选取k个宇宙中的点(或者k个星星)作为k个星团的质心,然后第一步对于每一个星星计算其到k个质心中每一个的距离,然后选取距离最近的那个星团作为,这样经过第一步每一个星星都有了所属的星团;第二步对于每一个星团,重新计算它的质心(对里面所有的星星坐标求平均)。重复迭代(逐个遍历所有点假设为质心)第一步和第二步直到质心不变或者变化很小(得到最优解)

下图展示了对n个样本点进行K-means聚类的效果,这里k取2(二分)


K-means面对的第一个问题是如何保证收敛,最优解求解算法中强调结束条件就是收敛,可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性,我们定义畸变函数(distortion function)如下:


J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值,那么首先可以固定每个类的质心,调整每个样例的所属的类别来让J函数减少,同样,固定,调整每个类的质心也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时,和c也同时收敛。(在理论上,可以有多组不同的和c值能够使得J取得最小值,但这种现象实际上很少见)

由于畸变函数J是非凸函数,意味着我们不能保证取得的最小值是全局最小值,也就是说k-means对质心初始位置的选取比较感冒,但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优,那么可以选取不同的初始值跑多遍k-means,然后取其中最小的J对应的clip_image018[8]和c输出。

Relevant Link:

http://coolshell.cn/articles/7779.html
http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html

 

9. 二分K-means算法

K-means算法本身存在几个缺陷

1. 可能收敛到局部最小值
2. 在大规模数据集上收敛较慢

当陷入局部最小值的时候,处理方法就是多运行几次K-means算法,然后选择畸变函数J较小的作为最佳聚类结果。这样的效率显然太低,我们希望能得到一次就能给出接近最优的聚类结果 
其实K-means的缺点的根本原因就是:对K个质心的初始选取比较敏感。质心选取得不好很有可能就会陷入局部最小值
基于以上情况,有人提出了二分K-means算法来解决这种情况,也就是弱化初始质心的选取对最终聚类效果的影响

Relevant Link:

http://blog.jobbole.com/86914/

类别:未分组 | 阅读:377367 | 评论:0 | 标签:

想收藏或者和大家分享这篇好文章→

“PHP处理海量样本相似度聚类算法”共有0条留言

发表评论

姓名:

邮箱:

网址:

验证码:

公告

taoCMS发布taoCMS 3.0.2(最后更新21年03月15日),请大家速速升级,欢迎大家试用和提出您宝贵的意见建议。

捐助与联系

☟请使用新浪微博联系我☟

☟在github上follow我☟

标签云