没有合适的资源？快使用搜索试试~ 我知道了~

首页大数据算法期末复习.pdf

大数据算法期末复习.pdf

大数据算法

期末考试复习资料

黑龙江大学

相似文档识别

pagerank

需积分: 0 373 浏览量更新于2023-05-25 评论收藏 2.84MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

42页

黑龙江大学专业选修课大数据算法期末考试复习资料pdf，有需要的自取，开卷考试，这个是总结老师PPT的复习资料。总的来说这老师挺好的，就是考试太难了，对大数据算法很感兴趣的可以选，如果是混学分的话还是算了，难。

资源详情

资源评论

资源推荐

大数据算法期末复习

1. 相似文档发现

1.1 概述

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 )

Jaccard相似度:

Jaccard距离:

1.3.3.1 方法1-集合编码成位向量

许多相似性的问题都可以被形式化定义为发现交集大的子集合

用0/1 (位, 布尔)向量给集合编码

全集中的每个元素对应一维

交集操作对应于位向量的与(AND),

并集操作对应于位向量的或(OR)

例题：

已知文件C1 = 10111; C2 = 10011，求Jaccard 相似度与Jaccard 距离。

解：交集大小= 3; 并集大小= 4

Jaccard 相似度sim(C1 ,C2 )= 3/4

Jaccard 距离: d(C1 ,C2 ) = 1 – (Jaccard相似度) = 1/4

1.3.3.2 方法2-集合转换到布尔矩阵

行 = 元素 (shingles)

列 = 集合 (文档)

行e ,列 s 的值为1 当且仅当元素 e 在文档 s 中

列相似度是对应集合的Jaccard 相似度 (值为1的行)

通常，矩阵是稀疏的!

每个文档是一列

例题：

求C1，C2的Jaccard相似度sim(C1 ,C2 )与Jaccard距离d(C1 ,C2 ) 。

解：交集大小= 3; 并集大小= 6

Jaccard相似度：

sim(C1 ,C2 )= 3/6

Jaccard距离：

d(C1 ,C2 ) = 1 – (Jaccard 相似度) = 3/6

1.4 最小哈希

1.4.1 定义

将大集合转化成小的签名, 同时保留相似度

签名是对列的哈希

基本思想

将每一列 C “哈希” 成一个小的签名 h(C)

使得:sim(C1 , C2 ) 等于签名 h(C1 ) 和 h(C2 )的”相似度”

将文档哈希到桶里. 期望”绝大多数”近似冗余的文档被哈希到同一桶!

目标

找到一个哈希函数 h(·) 使得:

如果 sim(C1 ,C2 ) 大, 则h(C1 ) = h(C2 )的概率大

如果 sim(C1 ,C2 ) 小, 则h(C1 ) ≠ h(C2 )的概率大

显然, 该哈希函数依赖于此相似性测度:

不是所有的相似性测度都有一个适合的哈希函数

C1 C2

0 0

1 1

0 0

0 1

1 0

定义：对于Jaccard相似性，存在合适的哈希函数: 被称为最小哈希(Min-Hashing)

1.4.2 求最小哈希的方法

方法一：对布尔矩阵的行进行排列 (不现实)

方法二：

1. 定义一个“哈希” 函数:

列 C 中值为 1 第一行(根据排列 )的索引值:

2. 对所有列进行应用几个随机挑选的排列，从而对每个列构建一个签名

3. 输出结果是一个签名矩阵:

列 = 集合(文档)

行 = 是该列的若干最小哈希值

1.4.3 属性与定理

选择一个随机排列

定理:

推导过程看不懂

1.4.4 四种行

给定列 C1和列C2:

行被分为如下四类:

剩余41页未读，继续阅读

卖烤麸烤饼儿

粉丝: 432
资源: 4

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

大数据算法期末复习.pdf

评论0

会员权益专享

最新资源

大数据算法期末复习.pdf

评论0

shor算法详细分析.pdf

C语言经典算法100例.pdf

粒子群优化算法(详细易懂-很多例子).pdf

2019中科大算法设计与分析期末复习重点.pdf

写一篇关于大数据算法与工程应用的论文

《编译原理》——期末复习.docx

AI算法工程师手册.pdf

数据结构考研必背算法5星.pdf

美团大数据算法分析用户的优缺点

卡尔曼滤波算法C语言实现.pdf

Geatpy遗传算法使用手册.pdf

非定常流动计算的PISO算法_王彤.pdf

.1_编程的灵魂——数据结构+算法=程序.ppt.1_编程的灵魂——数据结构+算法=程序.ppt

一种聚类隐马尔可夫模型的时空轨迹预测算法_孙红.pdf

基于小生境粒子群的多峰函数全局优化算法的研究.pdf

论文研究-FP_growth与Apriori算法比较应用 .pdf

开源OpenSSL的国密算法整理分析.pdf

会员权益专享

最新资源