[转]文内情似性算法：simhash/minhash/余弦算法

上一次，我用TF-IDF算法自动提取要害词。

本日，我们再来研究另一个相干的题目。有些时辰，除了找到要害词，我们还但愿找到与原文章相似的其他文章。好比，"Google消息"在主消息下方，还提供多条相似的消息。

为了找出相似的文章，必要用到"余弦相似性"（cosine similiarity）。下面，我举一个例子来声名，什么是"余弦相似性"。

为了简朴起见，我们先从句子着手。

　　句子A：我喜好看电视，不喜好看影戏。

　　句子B：我不喜好看电视，也不喜好看影戏。

叨教奈何才气计较上面两句话的相似水平？

根基思绪是：假如这两句话的用词越相似，它们的内容就应该越相似。因此，可以从词频入手，计较它们的相似水平。

第一步，分词。

　　句子A：我/喜好/看/电视，不/喜好/看/影戏。

　　句子B：我/不/喜好/看/电视，也/不/喜好/看/影戏。

第二步，列出全部的词。

　　我，喜好，看，电视，影戏，不，也。

第三步，计较词频。

　　句子A：我 1，喜好 2，看 2，电视 1，影戏 1，不 1，也 0。

　　句子B：我 1，喜好 2，看 2，电视 1，影戏 1，不 2，也 1。

第四步，写出词频向量。

　　句子A：[1,0]

　　句子B：[1,1]

到这里，题目就酿成了怎样计较这两个向量的相似水平。

我们可以把它们想象成空间中的两条线段，都是从原点（[0,...]）出发，指向差异的偏向。两条线段之间形成一个夹角，假如夹角为0度，意味着偏向沟通、线段重合；假如夹角为90度，意味着形成直角，偏向完全不相似；假如夹角为180度，意味着偏向正好相反。因此，我们可以通过夹角的巨细，来判定向量的相似水平。夹角越小，就代表越相似。

以二维空间为例，上图的a和b是两个向量，我们要计较它们的夹角θ。余弦定理汇报我们，可以用下面的公式求得：

假定a向量是[x1,y1]，b向量是[x2,y2]，那么可以将余弦定理改写成下面的情势：

数学家已经证明，余弦的这种计较要领对n维向量也创立。假定A和B是两个n维向量，A是 [A1,A2,...,An] ，B是 [B1,B2,Bn] ，则A与B的夹角θ的余弦便是：

行使这个公式，我们就可以获得，句子A与句子B的夹角的余弦。

余弦值越靠近1，就表白夹角越靠近0度，也就是两个向量越相似，这就叫"余弦相似性"。以是，上面的句子A和句子B是很相似的，究竟上它们的夹角约莫为20.3度。

由此，我们就获得了"找出相似文章"的一种算法：

　　（1）行使TF-IDF算法，找出两篇文章的要害词；

　　（2）每篇文章各取出多少个要害词（好比20个），归并成一个荟萃，计较每篇文章对付这个荟萃中的词的词频（为了停止文章长度的差别，可以行使相对词频）；

　　（3）天生两篇文章各自的词频向量；

　　（4）计较两个向量的余弦相似度，值越大就暗示越相似。

"余弦相似度"是一种很是有效的算法，只要是计较两个向量的相似水平，都可以回收它。

下面是PHP实现余弦相似度计较的算法

<?php
/**
 * 数据说明引擎
 * 说明向量的元素 必需和基准向量的元素同等，取最大个数，说明向量不敷元素以0弥补。
 * 求出说明向量与基准向量的余弦值
 */
/**
 * 得到向量的模
 * @param unknown_type $array 传入说明数据的基准点的N维向量。|eg:array(1,1);
 */
function getMarkMod($arrParam){
        $strModDouble = 0;
        foreach($arrParam as $val){
                $strModDouble += $val * $val;
        }
        $strMod = sqrt($strModDouble);
        //是否必要保存小数点后几位
        return $strMod;
}

/**
 * 获取标杆的元素个数
 * @param unknown_type $arrParam
 * @return number
 */
function getMarkLenth($arrParam){
        $intLenth = count($arrParam);
        return $intLenth;
}

/**
 * 对传入数组举办索引分派，基准点的索引必需为k，求夹角的向量索引必需为 'j'.
 * @param unknown_type $arrParam
 * @param unknown_type $index
 * @ruturn $arrBack
 */
function handIndex($arrParam,$index = 'k'){
        foreach($arrParam as $key => $val){
                $in = $index.$key;
                $arrBack[$in] = $val;
        }
        return $arrBack;
}

/**
 *
 * @param unknown_type $arrMark 标杆向量数组（索引被处理赏罚过）|array('k0'=>1,'k1'=>2....)
 * @param unknown_type $arrAnaly 说明向量数组（索引被处理赏罚过）|array('j0'=>1,'j1'=>2....)
 * @param unknown_type $strMarkMod 标杆向量的模
 * @param unknown_type $intLenth 向量的长度
 */
function getCosine($arrMark,$arrAnaly,$strMarkMod,$intLenth){
        $strVector = 0;
        $strCosine = 0;
        for($i = 0; $i < $intLenth; $i++){
                $strMarkVal = $arrMark['k'.$i];
                $strAnalyVal = $arrAnaly['j'.$i];
                $strVector += $strMarkVal * $strAnalyVal;
        }
        $arrAnalyMod = getMarkMod($arrAnaly); //求说明向量的模
        $strFenzi = $strVector;
        $strFenMu = $arrAnalyMod * $strMarkMod;
        $strCosine = $strFenzi / $strFenMu;
        if(0 !== (int)$strFenMu){
                $strCosine = $strFenzi / $strFenMu;
        }
        return $strCosine;
}
//基准点的N维向量
$arrMark = array(1,1);
//说明点的N维向量
$arrAnaly = array(1,4,5);
//向量的模
$MarkMod = getMarkMod($arrMark);
//向量的长度
$MarkLenth = getMarkLenth($arrMark);
//标杆向量数组
$Index1 = handIndex($arrMark,"k");
//说明向量数组
$Index2 = handIndex($arrAnaly,"j");
//说明向量与基准向量的余弦值
$Cosine = getCosine($Index1,$Index2,$MarkMod,$MarkLenth);
echo "向量的模：".$MarkMod;
echo "<br>";
echo "向量的长度：".$MarkLenth;
echo "<br>";
echo "标杆向量数组：";
print_r($Index1);
echo "<br>";
echo "说明向量数组：";
print_r($Index2);
echo "<br>";
echo "说明向量与基准向量的余弦值：".$Cosine;
?>

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!