.NET下文本相似度算法余弦定理和SimHash浅析及应用实例分析
本文实例讲述了.NET下文本相似度算法余弦定理和SimHash浅析及应用。分享给大家供大家参考。具体分析如下：
余弦相似性
原理：首先我们先把两段文本分词，列出来所有单词，其次我们计算每个词语的词频，最后把词语转换为向量，这样我们就只需要计算两个向量的相似程度.
我们简单表述如下
文本1：我/爱/北京/天安门/ 经过分词求词频得出向量（伪向量） [1,1,1,1]
文本2：我们/都爱/北京/天安门/ 经过分词求词频得出向量（伪向量） [1,0,1,2]
我们可以把它们想象成空间中的两条线段，都是从原点（[0, 0, ...]）出发，指向不同的方向。两条线段之间形成一个夹角，如果夹角为0度，意味着方向相同、线段重合；如果夹角为90度，意味着形成直角，方向完全不相似；如果夹角为180度，意味着方向正好相反。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。
C#核心算法：
public class TFIDFMeasure
{
private string[] _docs;
private string[][] _ngramDoc;
private int _numDocs=0;
private int _numTerms=0;
private ArrayList _terms;
private int[][] _termFreq;
private float[][] _termWeight;
private int[] _maxTermFreq;
private int[] _docFreq;
public class TermVector
{
public static float ComputeCosineSimilarity(float[] vector1, float[] vector2)
{
if (vector1.Length != vector2.Length)
throw new Exception("DIFER LENGTH");
float denom=(VectorLength(vector1) * VectorLength(vector2));
if (denom == 0F)
return 0F;
else
return (InnerProduct(vector1, vector2) / denom);
}
public static float InnerProduct(float[] vector1, float[] vector2)
{
if (vector1.Length != vector2.Length)
throw new Exception("DIFFER LENGTH ARE NOT ALLOWED");
float result=0F;
for (int i=0; i < vector1.Length; i++)
result += vector1[i] * vector2[i];
return result;
}
public static float VectorLength(float[] vector)
{
float sum=0.0F;
for (int i=0; i < vector.Length; i++)
sum=sum + (vector[i] * vector[i]);
return (float)Math.Sqrt(sum);
}
}
private IDictionary _wordsIndex=new Hashtable() ;
public TFIDFMeasure(string[] documents)
{
_docs=documents;
_numDocs=documents.Length ;
MyInit();
}
private void GeneratNgramText()
{
}
private ArrayList GenerateTerms(string[] docs)
{
ArrayList uniques=new ArrayList() ;
_ngramDoc=new string[_numDocs][] ;
for (int i=0; i < docs.Length ; i++)
{
Tokeniser tokenizer=new Tokeniser() ;
string[] words=tokenizer.Partition(docs[i]);
for (int j=0; j < words.Length ; j++)
if (!uniques.Contains(words[j]) )
uniques.Add(words[j]) ;
}
return uniques;
}
private static object AddElement(IDictionary collection, object key, object newValue)
{
object element=collection[key];
collection[key]=newValue;
return element;
}
private int GetTermIndex(string term)
{
object index=_wordsIndex[term];
if (index == null) return -1;
return (int) index;
}
private void MyInit()
{
_terms=GenerateTerms (_docs );
_numTerms=_terms.Count ;
_maxTermFreq=new int[_numDocs] ;
_docFreq=new int[_numTerms] ;
_termFreq =new int[_numTerms][] ;
_termWeight=new float[_numTerms][] ;
for(int i=0; i < _terms.Count ; i++)
{
_termWeight[i]=new float[_numDocs] ;
_termFreq[i]=new int[_numDocs] ;
AddElement(_wordsIndex, _terms[i], i);
}
GenerateTermFrequency ();
GenerateTermWeight();
}
private float Log(float num)
{
return (float) Math.Log(num) ;//log2
}
private void GenerateTermFrequency()
{
for(int i=0; i < _numDocs ; i++)
{
string curDoc=_docs[i];
IDictionary freq=GetWordFrequency(curDoc);
IDictionaryEnumerator enums=freq.GetEnumerator() ;
_maxTermFreq[i]=int.MinValue ;
while (enums.MoveNext())
{
string word=(string)enums.Key;
int wordFreq=(int)enums.Value ;
int termIndex=GetTermIndex(word);
_termFreq [termIndex][i]=wordFreq;
_docFreq[termIndex] ++;
if (wordFreq > _maxTermFreq[i]) _maxTermFreq[i]=wordFreq;
}
}
}
private void GenerateTermWeight()
{
for(int i=0; i < _numTerms ; i++)
{
for(int j=0; j < _numDocs ; j++)
_termWeight[i][j]=ComputeTermWeight (i, j);
}
}
private float GetTermFrequency(int term, int doc)
{
int freq=_termFreq [term][doc];
int maxfreq=_maxTermFreq[doc];
return ( (float) freq/(float)maxfreq );
}
private float GetInverseDocumentFrequency(int term)
{
int df=_docFreq[term];
return Log((float) (_numDocs) / (float) df );
}
private float ComputeTermWeight(int term, int doc)
{
float tf=GetTermFrequency (term, doc);
float idf=GetInverseDocumentFrequency(term);
return tf * idf;
}
private float[] GetTermVector(int doc)
{
float[] w=new float[_numTerms] ;
for (int i=0; i < _numTerms; i++)
w[i]=_termWeight[i][doc];
return w;
}
public float GetSimilarity(int doc_i, int doc_j)
{
float[] vector1=GetTermVector (doc_i);
float[] vector2=GetTermVector (doc_j);
return TermVector.ComputeCosineSimilarity(vector1, vector2);
}
private IDictionary GetWordFrequency(string input)
{
string convertedInput=input.ToLower() ;
Tokeniser tokenizer=new Tokeniser() ;
String[] words=tokenizer.Partition(convertedInput);
Array.Sort(words);
String[] distinctWords=GetDistinctWords(words);
IDictionary result=new Hashtable();
for (int i=0; i < distinctWords.Length; i++)
{
object tmp;
tmp=CountWords(distinctWords[i], words);
result[distinctWords[i]]=tmp;
}
return result;
}
private string[] GetDistinctWords(String[] input)
{
if (input == null)
return new string[0];
else
{
ArrayList list=new ArrayList() ;
for (int i=0; i < input.Length; i++)
if (!list.Contains(input[i])) // N-GRAM SIMILARITY?
list.Add(input[i]);
return Tokeniser.ArrayListToArray(list) ;
}
}
private int CountWords(string word, string[] words)
{
int itemIdx=Array.BinarySearch(words, word);
if (itemIdx > 0)
while (itemIdx > 0 && words[itemIdx].Equals(word))
itemIdx--;
int count=0;
while (itemIdx < words.Length && itemIdx >= 0)
{
if (words[itemIdx].Equals(word)) count++;
itemIdx++;
if (itemIdx < words.Length)
if (!words[itemIdx].Equals(word)) break;
}
return count;
}
}
缺点：
由于有可能一个文章的特征向量词特别多导致整个向量维度很高，使得计算的代价太大不适合大数据量的计算。
SimHash原理：
算法的主要思想是降维，将高维的特征向量映射成一个f-bit的指纹(fingerprint)，通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。由于每篇文章我们都可以事先计算好Hamming Distance来保存，到时候直接通过Hamming Distance来计算，所以速度非常快适合大数据计算。
Google就是基于此算法实现网页文件查重的。我们假设有以下三段文本：
1，the cat sat on the mat
2，the cat sat on a mat
3，we all scream for ice cream
如何实现这种hash算法呢？以上述三个文本为例，整个过程可以分为以下六步：
1、选择simhash的位数，请综合考虑存储成本以及数据集的大小，比如说32位
2、将simhash的各位初始化为0
3、提取原始文本中的特征，一般采用各种分词的方式。比如对于"the cat sat on the mat"，采用两两分词的方式得到如下结果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
4、使用传统的32位hash函数计算各个word的hashcode，比如："th".hash = -502157718
，"he".hash = -369049682，……
5、对各word的hashcode的每一位，如果该位为1，则simhash相应位的值加1；否则减1
6、对最后得到的32位的simhash，如果该位大于1，则设为1；否则设为0
希望本文所述对大家的.net程序设计有所帮助。
-
问题内容： 我计算了两个文档的tf / idf值。以下是tf / idf值： 这些文件就像： 如何使用这些值来计算余弦相似度？ 我知道我应该计算点积，然后找到距离并除以点积。如何使用我的值来计算？ 还有一个问题： 两个文档的字数相同是否重要？ 问题答案： a * b是点积 一些细节： 是。在某种程度上，a和b必须具有相同的长度。但是a和b通常具有稀疏表示，您只需要存储非零条目，就可以更快地计算范数
-
问题内容： 假设您在数据库中按以下方式构造了一个表： 为了清楚起见，应输出： 请注意，由于向量存储在数据库中，因此我们仅需要存储非零条目。在此示例中，我们只有两个向量$ v_ {99} =（4,3,4,0）$和$ v_ {1234} =（0,5,2,3）$都在$ \ mathbb {R}中^ 4 $。 这些向量的余弦相似度应为$ \ displaystyle \ frac {23} {\ sqrt
-
本文向大家介绍余弦相似性计算及python代码实现过程解析，包括了余弦相似性计算及python代码实现过程解析的使用技巧和注意事项，需要的朋友参考一下 A：西米喜欢健身 B：超超不爱健身，喜欢打游戏 step1:分词 A：西米／喜欢／健身 B：超超／不／喜欢／健身，喜欢／打／游戏 step2:列出两个句子的并集 西米／喜欢／健身／超超／不／打／游戏 step3:计算词频向量 A：[1,1,1,0,
-
本文向大家介绍Python 余弦相似度与皮尔逊相关系数 计算实例，包括了Python 余弦相似度与皮尔逊相关系数 计算实例的使用技巧和注意事项，需要的朋友参考一下 夹角余弦(Cosine) 也可以叫余弦相似度。 几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。 (1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式： (2) 两个n维
-
我试图用余弦相似性来找出两个文本文件的相似性。当我提供文本时，我可以发现这一点。但我想在阅读完电脑中的文本文件后得到结果。
-
问题内容： 如何找到向量之间的余弦相似度？ 我需要找到相似性来衡量两行文本之间的相关性。 例如，我有两个句子： 用户界面系统 用户界面机 …及其在tF-idf之后的向量，然后使用LSI进行标准化，例如 和。 如何测量这些向量之间的相似性？ 问题答案： 我最近在大学的信息检索部门做了一些tf-idf的工作。我使用了这种余弦相似度方法，该方法使用Jama：Java Matrix Package 。 有