Feature hashing相关 - 2

  1. Bloom filter

 
 

Feature hashing相关 - 2

思路 用多个不同hash 来记录,比如遇到一个 love 有4个hash function 映射到4个bit位置,如果所有位置都是1 那么认为之前已经遇到love这个词(有一定错误概率),如果有任何一个位置是0,那么表明love这个词之前没有遇到(100%这样)

 
 

  1. Count Min Sketch

    思路类似。。 考虑一个近似的(允许一定错误)的类似 hash table的 <key,value>更新查询操作

     
     

Feature hashing相关 - 2

论文 :An Improved Data Stream Summary: The Count-Min Sketch and its Applications

 
 

将输入的i 映射到 1-w , 采用d个hash function,开辟 w*d的空间

Feature hashing相关 - 2

Feature hashing相关 - 2

执行

Feature hashing相关 - 2

 
 

查询i的时候,取最小值!

Feature hashing相关 - 2

 
 

对于类似文本分类,线性svm这样我们关注的 dot(inner product点积)操作:

只给出结论

Feature hashing相关 - 2

也就是说只要按照w长度的空间向量进行点积即可,然后对应d个hash function取其中的最小值,算法复杂度O(w+d)

 
 

上一篇:Python cumsums和cumprod函数


下一篇:Web前端新人笔记之了解Jquery