余弦相似性
原理：首先我們先把兩段文本分詞，列出來所有單詞，其次我們計算每個詞語的詞頻，最後把詞語轉換為向量，這樣我們就只需要計算兩個向量的相似程度. 我們簡單表述如下 文本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
