快捷導(dǎo)航

.NET下文本相似度算法余弦定理和SimHash淺析及應(yīng)用實(shí)例分析

更新時(shí)間：2015年01月04日 12:08:42 投稿：shichen2014

這篇文章主要介紹了.NET下文本相似度算法余弦定理和SimHash淺析及應(yīng)用,實(shí)例形式詳細(xì)講述了相似度算法余弦定理和SimHash的原理與用法,需要的朋友可以參考下

本文實(shí)例講述了.NET下文本相似度算法余弦定理和SimHash淺析及應(yīng)用。分享給大家供大家參考。具體分析如下：

余弦相似性

原理：首先我們先把兩段文本分詞，列出來所有單詞，其次我們計(jì)算每個(gè)詞語的詞頻，最后把詞語轉(zhuǎn)換為向量，這樣我們就只需要計(jì)算兩個(gè)向量的相似程度.

我們簡(jiǎn)單表述如下

文本1：我/愛/北京/天安門/ 經(jīng)過分詞求詞頻得出向量（偽向量） [1,1,1,1]

文本2：我們/都愛/北京/天安門/ 經(jīng)過分詞求詞頻得出向量（偽向量） [1,0,1,2]

我們可以把它們想象成空間中的兩條線段，都是從原點(diǎn)（[0, 0, ...]）出發(fā)，指向不同的方向。兩條線段之間形成一個(gè)夾角，如果夾角為0度，意味著方向相同、線段重合；如果夾角為90度，意味著形成直角，方向完全不相似；如果夾角為180度，意味著方向正好相反。因此，我們可以通過夾角的大小，來判斷向量的相似程度。夾角越小，就代表越相似。

C#核心算法：

復(fù)制代碼代碼如下:

    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;
        }
}

缺點(diǎn)：

由于有可能一個(gè)文章的特征向量詞特別多導(dǎo)致整個(gè)向量維度很高，使得計(jì)算的代價(jià)太大不適合大數(shù)據(jù)量的計(jì)算。

SimHash原理：

算法的主要思想是降維，將高維的特征向量映射成一個(gè)f-bit的指紋(fingerprint)，通過比較兩篇文章的f-bit指紋的Hamming Distance來確定文章是否重復(fù)或者高度近似。由于每篇文章我們都可以事先計(jì)算好Hamming Distance來保存，到時(shí)候直接通過Hamming Distance來計(jì)算，所以速度非常快適合大數(shù)據(jù)計(jì)算。

Google就是基于此算法實(shí)現(xiàn)網(wǎng)頁文件查重的。我們假設(shè)有以下三段文本：

1，the cat sat on the mat

2，the cat sat on a mat

3，we all scream for ice cream

如何實(shí)現(xiàn)這種hash算法呢？以上述三個(gè)文本為例，整個(gè)過程可以分為以下六步：
1、選擇simhash的位數(shù)，請(qǐng)綜合考慮存儲(chǔ)成本以及數(shù)據(jù)集的大小，比如說32位
2、將simhash的各位初始化為0
3、提取原始文本中的特征，一般采用各種分詞的方式。比如對(duì)于"the cat sat on the mat"，采用兩兩分詞的方式得到如下結(jié)果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
4、使用傳統(tǒng)的32位hash函數(shù)計(jì)算各個(gè)word的hashcode，比如："th".hash = -502157718
，"he".hash = -369049682，……
5、對(duì)各word的hashcode的每一位，如果該位為1，則simhash相應(yīng)位的值加1；否則減1
6、對(duì)最后得到的32位的simhash，如果該位大于1，則設(shè)為1；否則設(shè)為0

希望本文所述對(duì)大家的.net程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: