| 失效链接处理 |
|
大数据算法期末复习 PDF 下载
本站整理下载：
相关截图：
主要内容：
1.1.1 一些定义
LSH实际指代一类相关的技术
是高维数据的一种处理方法
高维数据的常用处理方法有：
局部敏感散列
聚类
降维
1.1.2 基本思想
利用若干”哈希函数”将项(对象) 扔到桶里，
你只需要检查那些至少在一个哈希函数上共 享同一桶的元素对。
1.1.3优缺点
好处:
设计的合理的话, 只有很小比例的元素 对需要被检查
坏处:
有假阴性
没有发现的相似对(即相似的 元素对但是没有出现在同一桶中)
1.2 基本步骤
1. Shingling:
将文档转化成集合
使用哈希给每个shingle分配一个 ID
2. 最小哈希(Min-Hashing):
将大集合转化成小的签名, 同时保留相似度
使用保留相似度的哈希来生成签名，满足如下性质：
使用哈希来避免生成随机排列
3. 局部敏感哈希(Locality-Sensitive Hashing):
关注于发现可能会是相似文档的签名对（候选对）
采用哈希技术来发现相似度 s的候选对
1.3 Shingling
1.3.1 定义
将每个文档转化成一个集合
一个文档的一个 k-shingle (或 k-gram) 是出现 在该文档中的k个tokens构成的序
列
Tokens可以是字符, 单词或其他, 取决于具体的应用
我们假设 tokens = 例子中的字符
为了对长的shingles压缩, 我们可以对它们做哈希，哈希成 一个整数
比如4 个字节
用一个文档的所有k-shingles的哈希值构成集 合来表示该文档
例如：
k=2; 文档 D1= abcab
2-shingles的集合: S(D1 ) = {ab, bc, ca}
对shingles做哈希: h(D1 ) = {1, 5, 7}
实际中 k 常常是 8, 9, 或 10
1.3.2 Shingles的好处
相似的文档往往有很多共同的shingles
改变一个单词往往只会影响和这个单词距离不 超过k-1的k-shingles
1.3.3 Shingles的相似性测试
文档 D1 是它的k-shingles的集合 C1=S(D1 )
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
