相似项发现.PPT

数据挖掘与决策支持 教师：徐硕 电话Email: xush@ OR pzczxs@ 微信号：pzczxs 课程网址： 13/dmwiki/index.php?id=course:datamining16 课程主要内容 绪论（Introduction） 关联规则挖掘（Association Rule Mining） 相似项发现（Similar Item Finding） 分类及预测（Classification Prediction） 支持向量机及其他（SVM and Beyond） 序列标注方法（Sequence Labeling） 聚类分析（Clustering） 概率主题模型（Probabilistic Topic Model） 调查问卷分析方法（Questionnaire Analysis） 局部敏感哈希（LSH） 对于每条带（band），把它的每个列哈希到K个桶（bucket）中，K通常很大 哈希到同一个桶中的项对被视为侯选项对 调整b和r的值，使得真正率尽可能高（TP/(TP + FP)），假负率（FN/(TN + FN)）尽可能低 签名矩阵 r 行 0 2 1 3 0 2 1 3 4 0 0 3 3 0 2 0 0 0 2 1 0 0 2 2 3 0 2 0 桶 b 个带 D1, D5 D2,D6 D1 D2 D3 D4 D5 D6 D7 候选对 D4, D7 相似 相异 相似 True Positive （TP）真正 False Positive（FP）假正 相异 False Negative （FN）假负 True Negative（TN）真负 估计 真实 局部敏感哈希（LSH）分析 记签名矩阵中某一对值相等的概率为s 某一个带（band）完全相等的概率为：sr 某一个带（band）不完全相等的概率为：1 ? sr 所有带（band）不完全相等的概率为： (1? sr)b 至少有一个带（band）完全相等的概率为：P = 1 ? (1? sr)b P即为成为候选对的概率 局部敏感哈希（LSH）分析实例 s 1-(1-sr)b 0.2 0.006 0.3 0.047 0.4 0.186 0.5 0.470 0.6 0.802 0.7 0.975 0.8 0.9996 b = 20, r = 5 相似度阈值为s 第三章：相似项发现技术 引言 基于LSH的文档相似性检测 SpotSigs相似性检测 案例一：同源新闻稿检测 案例二：海量词典相似词条匹配 本章小结 SpotSigs相似性检测 Shingling表示 文档长度 划分区间 倒排索引 将文档表示成 Shingling的集合 侯选项对 进一步减少侯选 项对的假正率 Shingling表示 At a rally to kick off a weeklong campaign for the South Carolina primary, Obama tried to set the record straight from an attach circulating widely on the Internet that is designed to play into prejudice against Muslims and fears of terrorism. 红色下划线的词为引导词（antecedent） 引导词通常为停用词，但一般不是全部停用词 令距离为1，链长度为2，则Shingling集合为：{a:rally:kick, a:weeklong:campain, the:south:carolina, the:record:straight, an:attack:circulating, the:internet:designed, is:designed:play} 每个引导词的距离和链长度可以不同 第三章：相似项发现技术 引言 基于LSH的文档相似性检测 SpotSigs相似性检测 案例一：同源新闻稿检测 案例二：海量词典相似词条匹配 本章小结 场景完成问题（1/2） 场景完成问题（2/2） 200百万图像中最相似的10张图像 相似项发现应用：抄袭检测（1/3） 文档抄袭检测问题，非常考验文本相似度发现的能力 抄袭者可能会从其他文档中，将某些部分的文本据为已用 也可能对某些词语，或者原始文本中的句序进行改变 尽管如此，最终的文档中可能仍然有50%，基至更多的内容来自别人的原始文档 当然，一个复杂的抄袭文档，很难通过简单的字面比较来发现 相似项发现应用：抄袭检测（2/3） 相似项发现应用：抄袭检测（3/3） 相似项