本文实例讲述了.NET下文本相似度算法余弦定理和SimHash浅析及应用。分享给大家供大家参考。具体分析如下:
余弦相似性
原理:首先我们先把两段文本分词,列出来所有单词,其次我们计算每个词语的词频,最后把词语转换为向量,这样我们就只需要计算两个向量的相似程度.
我们简单表述如下
文本1:我/爱/北京/天安门/ 经过分词求词频得出向量(伪向量) [1,1,1,1]
文本2:我们/都爱/北京/天安门/ 经过分词求词频得出向量(伪向量) [1,0,1,2]
我们可以把它们想象成空间中的两条线段,都是从原点([0, 0, ...])出发,指向不同的方向。两条线段之间形成一个夹角,如果夹角为0度,意味着方向相同、线段重合;如果夹角为90度,意味着形成直角,方向完全不相似;如果夹角为180度,意味着方向正好相反。因此,我们可以通过夹角的大小,来判断向量的相似程度。夹角越小,就代表越相似。
C#核心算法:
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;
}
}
希望本文所述对大家的.net程序设计有所帮助。
新闻热点
疑难解答