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

最小哈希：

行的随机分列转换（也称置换运算）

哈希值：分列转换后的行分列序次下第一个列值为1的行的行号，譬喻h(S1)=D，h(S2)=B

两个荟萃经随机分列之后获得的两个最小哈希值相称的概率便是这两个荟萃的Jaccard相似度。

题目：

对付上百万乃至数十亿的行选择一个随机分列转换极其耗损时刻，怎么办？

1. 随机选择n个哈希函数h1，h2…
2. 对每列C举办如下操纵：

　　　　a) ?假如c在第r举动0，则什么也不做；

　　　　b)?? 不然，假如c在第r举动1，那么对付每个i=1,2，…，n，将SIG（i,c）置为原本的SIG（i，c）和h(r)中的较小值

?

计较最小哈希署名矩阵：

计较Jaccard相似度：

SIM(S1，S4)=1.0；SIM(S1，S3)=1/3；SIM(S1，S2)=0

真实SIM(S1，S4)=2/3；SIM(S1，S3)=1/4；SIM(S1，S2)=0

?

相干论文：

1.《Google News Personalization: Scalable Online Collaborative Filtering》

按照用户的汗青点击数据，举办消息保举；回收最小哈希聚类的协同过滤算法

2.《The Link-Prediction Problem for Social Networks》

较量交际收集链接猜测题目的各类算法

计较挚友相似度的流程：

• 找到N个哈希函数，对每个用户挚友荟萃天生一组Minhash（N个）
• 对付一个用户，按Minhash沟通个数做排序，给出保举候选集
• 计较用户跟被备选集的Jaccard Index
• 按Jaccard功效排序，给出TopN举办保举

哈希函数天生和哈希值计较：

1. 输入向量Vector转换为bytes
   • numHashFunctions--预设天生hash函数的个数（假定为10个）

   • 

     for (int i = 0; i < numHashFunctions; i++) {
           for (Vector.Element ele : featureVector) {
             int value = (int) ele.get();
             bytesToHash[0] = (byte) (value >> 24);
             bytesToHash[1] = (byte) (value >> 16);
             bytesToHash[2] = (byte) (value >> 8);
             bytesToHash[3] = (byte) value;
             int hashIndex = hashFunction[i].hash(bytesToHash); //计较哈希函数值
             //只保存最小哈希值
             if (minHashValues[i] > hashIndex) {
               minHashValues[i] = hashIndex;
             }
           }
         }

     

     ?

2. 回收Mersenne Twister算法结构伪随机天生器
   • Random random = new MersenneTwisterRNG(new FastRandomSeedGenerator());
     • org.uncommons.maths.random. MersenneTwisterRNG.MersenneTwisterRNG( SeedGeneratorseedGenerator)
   • Mersenne Twister（马特赛特旋转演算法），是伪随机数产生器之一，其首要浸染是天生伪随机数。
     Mersenne Twister算法的道理：Mersenne Twister算法是操作线性反馈移位寄存器(LFSR)发生随机数的，LFSR的反馈函数是寄存器中某些位的简朴异或，这些位也称之为抽头序列。一个n位的LFSR可以或许在一再之前发生2^n-1位长的伪随机序列。只有具有必然抽头序列的LFSR才气通过全部2^n-1个内部状态，发生2^n - 1位长的伪随机序列，这个输出的序列就称之为m序列。为了使LFSR成为最大周期的LFSR，由抽头序列加上常数1形成的多项式必需是本原多项式。一个n阶本原多项式是不行约多项式，它能整除x^(2*n-1)+1而不能整除x^d+1，个中d能整除2^n-1。譬喻(32,7,5,3,1,0)是指本原多项式x^32+x^7+x^5+x^3+x^2+x+1，把它转化为最大周期LFSR就是在LFSR第32，7，5，2，1位抽头。操作上述两种要领发生周期为m的伪随机序列后，只必要将发生的伪随机序列除以序列的周期，就可以获得(0，1)上匀称漫衍的伪随机序列了。 Mersenne Twister有以下利益：随机性好，在计较机上轻易实现，占用内存较少(mt19937的C程式码执行仅需624个字的事变地区)，发生随机数的速率快、周期长，可到达2^19937-1，且具有623维匀称漫衍的性子，对付一样平常的应用来说，足够大了，序列关联较量小，能通过许多随机性测试。
3. 四种哈希函数天生器
   • MAX_INT_SMALLER_TWIN_PRIME = 2147482949；为什么选这个值？
     • 它是整型范畴内最大孪生素数（相差为2的两个数都是质数的环境）的较小值；哈希用素数取模斗嘴小
   • seedA、seedB、seedC是回收MersenneTwisterRNG随机天生器天生的0~11匀称漫衍的随机数
   • 第一种：LinearHash
     

     

         @Override
         public int hash(byte[] bytes) {
           long hashValue = 31;
           for (long byteVal : bytes) {
             hashValue *= seedA * byteVal;
             hashValue += seedB;
           }
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }

     

   • 第二种:PolynomialHash

     

      @Override
         public int hash(byte[] bytes) {
           long hashValue = 31;
           for (long byteVal : bytes) {
             hashValue *= seedA * (byteVal >> 4);
             hashValue += seedB * byteVal + seedC;
           }
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }

     

   • 第三种：MurmurHashWrapper

     @Override
         public int hash(byte[] bytes) {
           long hashValue = MurmurHash.hash64A(bytes,seed);
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }

   • 第四种:MurmurHash3Wrapper

     @Override
         public int hash(byte[] bytes) {
           long hashValue = MurmurHash3.murmurhash3_x86_32(bytes,bytes.length,seed);
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }?

来历：http://www.cnblogs.com/shipengzhi/articles/2826209.html

（编辑：湖南网）

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