信息检索与数据挖掘

Transcription

1 2018/5/6 1 5 月 20 日 12:00 前, 提交文献阅读相关素材 5 月 28 日 12:00 前, 提交实验报告及相关素材 信息检索与数据挖掘 补充 : 数据挖掘经典算法概述 (2) 4 月 28 日, 补充 : 概率图及主题模型 5 月 4 日, 补充 : 数据挖掘经典算法概述 (1) 5 月 7 日, 补充 : 数据挖掘经典算法概述 (2) 5 月 11 日, 第 12 章 Web 搜索 5 月 14 日, 第 13 章多媒体信息检索 5 月 18 日, 复习 5 月 21 日, 同学们文献阅读报告 5 月 25 日, 同学们文献阅读报告 5 月 28 日, 期末考试 暂定

2 2018/5/6 2 数据挖掘十大经典算法 Naive Bayes knn k-means SVM EM C4.5 CART AdaBoost Apriori Pagerank 第 12 章 Web 搜索 [1] Xindong Wu, Vipin Kumar, J. Ross Quinlan, et al. Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1):1 37, 4 December 2007.

3 2018/5/6 3 回顾 : 朴素贝叶斯分类器 概率图 E1(outlook): sunny, overcast, rainy E2(temperature): hot, mild, cool E3(humidity): high, normal E4(windy): FALSE, TRUE C(play): no, yes 独立性的假设 P(C,E1,E2,E3,E4)=P(C)P(E1 C)P(E2 C)P(E3 C)P(E4 C) Graphical Model C E4 E1 E2 E3

4 关于朴素贝叶斯分类器的思考 All models are wrong, but some are useful 2018/5/6 4 George Edward Pelham Box FRS (18 October March 2013) was a statistician, who worked in the areas of quality control, time-series analysis, design of experiments, and Bayesian inference. He has been called "one of the great statistical minds of the 20th century". All models are wrong is a common aphorism in statistics. It is generally attributed to the statistician George Box. The first record of Box saying all models are wrong is in a 1976 paper published in the Journal of the American Statistical Association. The paragraph containing the aphorism is below. Since all models are wrong the scientist cannot obtain a "correct" one by excessive elaboration. On the contrary following William of Occam he should seek an economical description of natural phenomena. Just as the ability to devise simple but evocative models is the signature of the great scientist so overelaboration and overparameterization is often the mark of mediocrity.

5 2018/5/6 5 EM 算法示例 : 求两个硬币随机抛出后正反面的概率迭代过程分析 x = (x1, x2,, x5), x i {0,1,,10} 第 i 次抛硬币试验中正面 (head) 朝上的次数 z = (z 1, z 2,, z 5 ), z i {A,B} 第 i 次抛硬币试验中被抛掷的硬币是 A 还是 B x=(x 1 =5,x 2 =9,x 3 =8,x 4 =4,x 5 =7) Z 是隐变量 2 求隐变量 Z 的后验概率 P(z i = A x i ; θ A (0) ) P(z i = B x i ; θ B (0) ) X 和 Z 的联合概率 P(x i, z i = A x i ; θ A (0) ) P(x i, z i = B x i ; θ B (0) ) 3 从联合概率求边缘概率 θ A (1) = P(zi = A x i ; θ A (0) ) θ B (1) = P(zi = B x i ; θ B (0) ) C. B. Do and S. Batzoglou, "What is the expectation maximization algorithm?," Nature Biotechnology, vol. 26, p. 897, 08/01/online 2008.

6 2018/5/6 6 p X ; θ = σ Z p X, Z ; θ 从联合概率计算边缘概率 p X, Z ; θ p(x ; θ) = q Z, q Z = p(z X ; θ t ), 构造的先验分布 q(z) Z log p(x ; θ) = log q Z Z p X, Z ; θ q(z) log p(x ; θ) q Z ; መθ t log p(x ; θ) p Z X ; መθ t log p(x ; θ) p Z X ; መθ t log p(x ; θ) p Z X ; መθ t EM 算法 : 迭代逼近最优解过程分析 Z Z Z Z q Z log Z log p X, Z ; መθ t q Z; መθ t log p X, Z ; መθ t p Z X ; መθ t log p X, Z ; መθ t p Z X ; መθ log p X, Z ; መθ t p Z X ; መθ p X, Z ; θ q Z log p X θ L q, θ + KL(q p) p Z X ; መθ p Z X ; መθ t Jensen s inequality + p Z X ; መθ t Z log p Z X ; መθ p Z X ; መθ t

7 2018/5/6 7 小结 :EM (Expectation Maximization) 参数估计的两种情形 完全信息下的 MLE 估计 不完全信息下的参数估计 EM 算法是一种解决存在隐含变量优化问题的方法 E-Step: 根据已经估计的参数计算隐藏变量的后验概率 ( 即根据参数计算似然函数的期望 ) M-Step: 根据已经计算的后验概率更新参数 ( 选择参数使似然最大化 ) 特点 通过不断构造下界逐步向最优逼近 K-means 算法是一种 Hard EM 算法 估计参数的初值影响到是否落入局部最优点 C. B. Do and S. Batzoglou, "What is the expectation maximization algorithm?," Nature Biotechnology, vol. 26, p. 897, 08/01/online 关于 EM 算法的九层境界的浅薄介绍

8 2018/5/6 8 Decision Graphs 示例决策树 (decision tree) 决策问题 : 使效用函数最大化 Maximum Expected Utility Principle 决策树最早的决策图 (Decision Graphs) 之一, 是决策问题 (decision problem) 的图形化表示 (representation), 三要素为 : A decision node is depicted as a rectangle. An event node is depicted as a circle. The results are annotated with the utility. Advances in Computer Vision and Pattern Recognition Luis Enrique Sucar, Probabilistic Graphical Models (Principles and Applications), 2015

9 2018/5/6 9 两种不同的决策树 用什么样的规则构造决策树?

10 2018/5/6 10 构建决策树的思路 构建决策树时通常采用自上而下的方法, 在每一步选择一个最好的属性来分裂 最好 的定义是使得子节点中的训练集尽量的纯 最好 也可以定义为 不纯度 尽量小 在数据挖掘中, 决策树主要有两种类型 : 分类树 : 输出是样本的类别标签 (label) 回归树 : 输出是一个实数 回归, 为什么称之为回归? Galton: y= x

11 2018/5/6 11 C4.5(1992): 对 ID3(1992) 的改进 ID3 算法中的信息增益 ( 其实就是互信息量 ) Gain(E1) = H(C) H(C E1) Gain(E3, e1=sunny) = H(C) - H(C E3, e1=sunny) C4.5 算法的信息增益率 IGR(E1) = Gain(E1) / H(E1) IGR(E1) = [H(C) H[C E1]] / H(E1) 罗斯. 昆兰 (Ross Quinlan)

12 2018/5/6 12 C4.5(1992): 对 ID3 的扩展 C4.5 算法在以下几方面对 ID3 算法进行了改进 : 1) 用信息增益率来选择属性, 克服了用信息增益选择属性时偏向选择取值多的属性的不足 ; 2) 在树构造过程中进行剪枝 ; 一些分枝反映的是训练数据中的异常 ( 数据中的噪声和离群点 ) 剪枝方法是用来处理这种过分拟合数据的问题 3) 能够完成对连续属性的离散化处理 ; 4) 能够对不完整数据进行处理 C4.5 算法优点 产生的分类规则易于理解, 准确率较高 C4.5 算法缺点 在构造树的过程中, 需要对数据集进行多次的顺序扫描和排序, 因而导致算法的低效 此外,C4.5 只适合于能够驻留于内存的数据集, 当训练集大得无法在内存容纳时程序无法运行 C5.0 是决策树 C4.5 的商用算法, 在内存管理等方面, 给出了改进 比如在商用软件 SPSS 中, 就有该算法

13 2018/5/6 13 小结 : 决策树算法 ID3, 信息增益,1979 Gain(E1) = H(C) H(C E1) Gain(E3, e1=sunny) = H(C) - H(C E3, e1=sunny) C4.5, 信息增益率,1992 IGR(E1) = Gain(E1) / H(E1) IGR(E1) = [H(C) H[C E1]] / H(E1) CART, 基尼指数,1985 K GINI D = p k (1 p k ) = 1 p 2 k = 1 k=1 K k=1 一些问题 分枝有限个, 如何处理连续值属性? 误入歧途, 如何处理过拟合问题? 信息不完整, 如何处理部分样本属性缺失的问题? K k=1 C k D 2 CART(Classification And Regression Tree, 1984) 算法是一种二分递归分割技术,CART 生成的决策树是结构简洁的二叉树

14 2018/5/ 月 20 日 12:00 前, 提交文献阅读相关素材 5 月 28 日 12:00 前, 提交实验报告及相关素材 信息检索与数据挖掘 补充 : 数据挖掘经典算法概述 (2) 4 月 28 日, 补充 : 概率图及主题模型 5 月 4 日, 补充 : 数据挖掘经典算法概述 (1) 5 月 7 日, 补充 : 数据挖掘经典算法概述 (2) 5 月 11 日, 第 12 章 Web 搜索 5 月 14 日, 第 13 章多媒体信息检索 5 月 18 日, 复习 5 月 21 日, 同学们文献阅读报告 5 月 25 日, 同学们文献阅读报告 5 月 28 日, 期末考试 暂定

15 2018/5/6 15 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

16 2018/5/6 16 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

17 2018/5/6 17 分类器的组合 Combining Models It is often found that improved performance can be obtained by combining multiple models together in some way, instead of just using a single model in isolation. 多个分类器组合效果优于单个分类器 For instance, we might train L different models and then make predictions using the average of the predictions made by each model. Such combinations of models are sometimes called committees. 多个分类器组合的权重通过投票机制 ( 委员会 ) 实现 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

18 2018/5/6 18 组合多个分类器的一般性问题 弱分类器 : 组合前的每一个分类器 强分类器 : 组合后最后的分类器 每个弱分类器的训练样本集? 相同还是不同, 如果不同如何选取? 每个弱分类器的学习方法? 相同还是不同, 如果不同选取的原则? 各个弱分类器是否相关? 训练样本是相关的? 学习方法是相关的? 如何将训练得到的各弱分类器组合成强分类器?

19 2018/5/6 19 Bagging(Bootstrap aggregating) 思路 bagging 技术的过程 : 假设有一个大小为 n 的训练集 D,bagging 会从 D 中有放回的均匀抽样, 假设用 bagging 生成了 m 个新的训练集 Di, 每个 Di 的大小为 j 由于有放回的进行抽样, 那么在 Di 中的样本有可能是重复的 如果 j=n, 这种取样称为 bootstrap 取样 现在, 可以用上面的 m 个训练集来拟合 m 个模型, 然后结合这些模型进行预测 对于回归问题来说, 我们平均这些模型的输出 ; 对于分类问题来说, 我们进行投票 (voting) bagging 能提升机器学习算法的稳定性和准确性, 它可以减少模型的方差从而避免 overfitting

20 Bagging(Bootstrap aggregating) 思路示意图 2018/5/6 20 首先创建随机训练数据集样本 ( 训练数据集的子集 ) 然后为每个样本建立分类器 最后, 这些多分类器的结果将结合起来, 使用平均或多数投票

21 2018/5/6 21 Bagging(Bootstrap aggregating) 有放回的随机抽样示例 假设有一个训练集 D 的大小为 7, 用 bagging 生成 3 个新的训练集 Di, 每个 Di 的大小为 7, 结果如下表 : 样本索引 Bagging(D1) Bagging(D2) Bagging(D3)

22 2018/5/6 22 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

23 2018/5/6 23 Boosting, 思路 Boosting 是一个迭代的过程, 用来自适应的改变训练样本的分布, 使分类器聚焦在那些很难分的样本上 在 Bagging 的过程中, 抽取自主样本集的时候是简单随机抽样, 每个样本被抽到的概率是一样的, 但是 Boosting 算法中给每一个样本赋予一个权值, 每一轮在抽取自助样本集 训练完基分类器之后会对原始样本集做一个分类, 然后跟效果比对, 然后对分错的训练样本, 自动的调节该样本的权值 权值可以用在以下方面 : (1) 可以用作抽样分布, 从原始数据集中选出自助样本集 ( 注意,Bagging 抽样时样本是均匀分布的 ) (2) 基分类器训练时更倾向于用高权值的样本进行训练 分类器组合方法 Bootstrap, Boosting, Bagging, 随机森林 ( 一 ) Retieved:

24 2018/5/6 24 Boosting, 示例 例, 有 10 个样本, 开始时简单随机抽样, 每个样本被抽到的概率是一样的, 都是 1/10, 然后第一轮结束后用得到的模型对该轮数据集中的样本分类, 发现样本 4 被分错了, 就增加它的权值, 这样, 第二轮抽取的时候 4 被抽到的概率增加了, 第三轮也是一样 这样做, 就可以让基分类器聚焦于难被分类的样本 4, 增加 4 被正确分类的几率 分类器组合方法 Bootstrap, Boosting, Bagging, 随机森林 ( 一 ) Retieved:

25 2018/5/6 25 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

26 2018/5/6 26 AdaBoost (Adaptive boosting), 1995 Adaboost 结构 : 最后的分类器 Y M 是由数个弱分类器 (weak classifier) 组合而成的, 相当于最后 m 个弱分类器来投票决定分类, 而且每个弱分类器的 话语权 α 不一样 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

27 2018/5/6 27 初始化样本权重系数 w n (1) AdaBoost 训练数据 :x 1,, x N 对应类别 :t 1,, t N t n { 1, 1} 分类器 :y 1,, y M 第 m 个分类器的误差 J m 第 n 个样本在第 m 个分类器 y m 中的权重 :w (m) n 示性函数 I() 第 m 个分类器的归一化误差 ε m 分类器 y m 归一化误差 ε m 分类器 y m 权重 α m 第 m 个分类器的权重 α m 样本权重系数 w n (1) 更新 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

28 2018/5/6 28 AdaBoost 弱分类器示例 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

29 2018/5/6 29 随机森林 (Random Forest,1995) 随机森林利用随机的方式将许多决策树组合成一个森林, 每个决策树在分类的时候投票决定测试样本的最终类别 随机森林主要包括下 4 个部分 : 1. 随机选择样本 给定一个训练样本集, 数量为 N, 我们使用有放回采样到 N 个样本, 构成一个新的训练集 2. 随机选择特征 在随机森林中, 不计算所有特征的增益, 而是从总量为 M 的特征向量中, 随机选择 m 个特征,m 可以等于 sqrt(m), 然后计算 m 个特征的增益, 选择最优特征 3. 构建决策树 在随机产生的样本集上使用一般决策树的构建方法, 得到一棵决策树 4. 随机森林投票分类 通过上面的三步走, 得到一棵决策树, 我们可以重复这样的过程 H 次, 就得到了 H 棵决策树 然后来了一个测试样本, 我们就可以用每一棵决策树都对它分类一遍, 得到了 H 个分类结果 这时, 我们可以使用简单的投票机制, 或者该测试样本的最终分类结果

30 2018/5/6 30 小结 : 分类器的组合 多分类器进行组合的目的是为了将单个分类器 ( 也叫基分类器 base classifier) 进行组合, 提升对未知样本的分类准确率,( 依赖于基分类器的分类性能和基分类器之间的独立性 ) 提到组合方法 (classifier combination), 有很多的名字涌现, 如 bootstraping, boosting, adaboost, bagging, random forest 等等 那么它们之间的关系如图 : 注意 :Boosting 中组合在一起的多个分类器是有关联的 : 后一个分类器依赖于前一个分类器 分类器组合方法 Bootstrap, Boosting, Bagging, 随机森林 ( 一 ) Retieved:

31 2018/5/6 31 Do we Need Hundreds of classifiers to Solve Real World Classification Problems? We evaluate 179 classifiers arising from 17 families (discriminant analysis, Bayesian, neural networks, SVM, decision trees, rule-based classifiers, boosting, bagging, stacking, random forests and other ensembles, generalized linear models, nearest neighbors, partial least squares and principal component regression, logistic and multinomial regression, multiple adaptive regression splines and other methods), implemented in Weka, R, C and Matlab, including all the relevant classifiers available today. We use 121 data sets. The classifiers most likely to be the bests are the random forest (RF) versions, the best of which (implemented in R and accessed via caret) achieves 94.1% of the maximum accuracy overcoming 90% in the 84.3% of the data sets. However, the difference is not statistically significant with the second best, the SVM with Gaussian kernel implemented in C using LibSVM, which achieves 92.3% of the maximum accuracy.. Manuel Fern andez-delgado et.al. Do we Need Hundreds of classifiers to Solve Real World Classication Problems?, Journal of Machine Learning Research 15 (2014)

32 2018/5/6 32 The Top 10 Topics in Machine Learning Revisited: A Quantitative Meta-Study, The Top 10 Topics in Machine Learning Revisited: A Quantitative Meta-Study, 2017 In our study, we use machine learning in order to find the top 10 topics in machine learning from about 54K abstracts of papers published between 2007 and 2016 in leading machine learning journals and conferences.

33 C4.5 k-means SVM Apriori EM PageRank AdaBoost knn Naive Bayes CART 2007 算法原理 2017 算法实现 Weka, R, C, Matlab 2018/5/6 33 Support vector machine Neural network Data set Objective function Markov random field Feature space Generative model Linear matrix inequality Gaussian mixture model Principal component analysis Hidden Markov model Conditional random field Graphical model Maximum likelihood estimation Clustering algorithm Nearest neighbors Genetic algorithm Latent Dirichlet allocation Gaussian process Markov chain Monte Carlo Top 10 algorithms in data mining Do we Need Hundreds of classifiers to Solve Real World Classication Problems? 2014 The Top 10 Topics in Machine Learning Revisited: A Quantitative Meta-Study. 2017

34 2018/5/6 34 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

35 2018/5/6 35 频繁模式挖掘的内容 Frequent Pattern Mining Frequent Item Set Mining and Association Rule Induction Frequent Sequence Mining Frequent Tree Mining Frequent Graph Mining 频繁模式 频繁项集 频繁子序列本节仅覆盖频繁项集的挖掘 频繁子结构

36 2018/5/6 36 关联规则 (association rules ) 分析 令 I = {i 1, i 2,, i n } 为 items 的集合 ( 成为项集 ), 例如 I={milk, bread, butter, beer, diapers} 令 T = {t, t 2,, t n } 为 transaction 的集合 ( 称为 database), 例如上表 database 含有 5 个 transaction 规则 (rule) 定义为 :X Y, X, Y I, 例如规则 butter, bread {milk} 例如, 项集 (itemset) X={beer, dispers} 的支持度是 0.2 规则 butter, bread {milk} 的置信度是 0.2/0.2=1 规则 milk, bread butter 的 lift 是 0.2/(0.4*0.4)=1.25 规则 milk, bread butter 的 Conviction 是 (1-0.4)/(1-0.5)=1.2 关联规则分析 (Association Rules, 又称 Basket Analysis) 用于从大量数据中挖掘出有价值的数据项之间的相关关系 支持度 Support: supp(x) = {t T; X t} / T 置信度 Confidence conf(x Y) = supp(x Y)/supp(X) 提升度 Lift: lift(x) = supp(x Y)/supp(X) supp(y) 确信度 Conviction: conv X Y = (1 supp(y))/(1 conf(x Y)) Transaction ID milk bread butter beer diapers

37 2018/5/6 37 频繁项集分析 Frequent Item Set Mining 几个定义 频繁项 : 在多个集合中, 频繁出现的元素 / 项, 就是频繁项 频繁项集 : 有一系列集合, 这些集合有些相同的元素, 集合中同时出现频率高的元素形成一个子集, 满足一定阈值条件, 就是频繁项集 极大频繁项集 : 元素个数最多的频繁项集合, 即其任何超集都是非频繁项集 相似性分析 vs. 频繁项集分析 频繁项集分析是关联规则分析的一部分 相似性分析, 研究的对象是集合之间的相似性关系 而频繁项集分析, 研究的集合间重复性高的元素子集 频繁项集的应用 : 真实超市购物篮的分析, 文档或网页的关联程序分析, 文档的抄袭分析, 生物标志物 ( 疾病与某人生物生理信息的关系 )

38 2018/5/6 38 频繁项集分析 : 频繁项示例 I={a, b, c, d, e} 上可能有 2 5 个项集合 (item set) 本例中最小支持度 support 是 3, 归一化的 support 是 0.3 如右表所示, 共有 16 个频繁项

39 2018/5/6 40 频繁项集分析 : 购物篮 支持度示例 eight baskets, each consisting of items that are words Among the singleton sets, obviously {cat} and {dog} are quite frequent. Dog appears in all but basket (5), so its support is 7, while cat appears in all but (4) and (8), so its support is 6. The word and is also quite frequent; it appears in (1), (2), (5), (7), and (8), so its support is 5. The words a and training appear in three sets, while for and is appear in two each. No other word appears more than once. Suppose that we set our threshold at s = 3. Then there are five frequent singleton itemsets: {dog}, {cat}, {and}, {a}, and {training}.

40 2018/5/6 41 频繁项集分析 : 双元素频繁集合 Occurrences of doubleton Now, let us look at the doubletons. A doubleton cannot be frequent unless both items in the set are frequent by themselves. Thus, there are only ten possible frequent doubletons. There are five frequent doubletons if s = 3; they are {dog, a} {dog, and} {dog, cat} {cat, a} {cat, and} Each appears exactly three times, except for {dog, cat}, which appears five times.

41 2018/5/6 42 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

42 确定性数据中频繁项集挖掘的相关算法 A-Priori 算法, [Agrawal and Srikant 1994] 2018/5/6 43 频繁项子集定理 : 频繁项集的子集都是频繁项集, 而非频繁项的超集都是非频繁项集 A-Priori 算法是基于先验的算法, 在挖掘过程中首先产生候选项集, 然后到原数据库中检验这些候选项集是否是频繁的 釆用的是自底向上的产生 - 检验的模式来搜索所有的频繁项集 首先, 产生长度为 1 的候选项集 C 1, 计算 C 1 中所有候选项的支持度来确定哪些是频繁的, 这些频繁的长度为 1 的候选项保存在 L 1 中 ; 然后从 L 1 中产生出所有长度为 2 的候选项集, 保存在 C 2 中, 计算 C 2 中所有候选项的支持度来确定哪些是频繁的, 保存在 L 2 中 ; 以此类推, 直到没有产生新的候选项集, 即 C k 为空 (k>1) 这样, 算法就可以输出所有的频繁项集 由于算法是基于产生 - 检验的, 在挖掘过程中要经常回到原数据库中检验候选项集是否频繁, 因此当数据库比较大时, 该方法效率不高

43 2018/5/6 44 A-Priori 算法示例 原始数据 TID T100 T200 T300 T400 T500 T600 T700 T800 T900 List of item_id s I1,I2,I5 I2,I4 I2,I3 I1,I2,I4 I1,I3 I2,I3 I1,I3 I1,I2,I3,I5 I1,I2,I3 A-Priori 算法步骤 频繁项集挖掘算法 FP-Growth Retrieved:

44 2018/5/6 45 广度优先搜索 Prefix Trees 考虑支持度不小于 3 的频繁项集 Apriori 执行 Breadth-first, 每次搜索的是同一层的 item 1 第 1 层 :{a, b, c, d, e} 2 第 2 层 :{ab, ac, ad, ae, bc, bd, be, de, ce, de} 3 第 3 层 :{acd, ace, ade, bcd, bce, cde} 4 第 4 层 :{acde}

45 2018/5/6 46 频繁项的其他查找思路 : 深度优先搜索 Prefix Trees 深度优先搜索 : 可分解为子问题 Frequent Pattern Mining, retrieved:

46 2018/5/6 47 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

47 2018/5/6 50 Eclat 算法 [Zaki, Parthasarathy, Ogihara, and Li 1997] 示例 找出支持度 >=3 的频繁项集 先处理支持度最高的频繁项 a: (1) 找出频繁项 ab, ac, ad, ae; 删除支持度 <3 的项 ab (2) 找出频繁项 acd, ace (3) 找出频繁项 acde; 删除支持度 <3 的项 acde 购物篮按照字母顺序排序 Frequent Pattern Mining, retrieved:

48 2018/5/6 51 Frequent Pattern Mining, retrieved:

49 2018/5/6 52 Eclat 算法 [Zaki, Parthasarathy, Ogihara, and Li 1997] 示例 找出支持度不小于 3 的频繁项集目前还留在图上的频繁项就是所有支持度不小于 3 的频繁项集 {acd, ace, ade, ae, bc, cd, ce, de} 购物篮按照字母顺序排序 Frequent Pattern Mining, retrieved:

50 2018/5/6 53 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

51 2018/5/6 54 FP-growth (Frequent Pattern growth) 算法, [Han, Pei, and Yin 2000] 与 Apriori 不同的是, 该算法不用产生候选项集, 只需要测试支持度计数, 因此其效率是高于 Apriori 算法的 该算法主要由两步操作组成 :(1) 构造 FP-tree;(2) 挖掘频繁项集 主要操作如下 : 首先, 对数据库进行第一次扫描检验每个项的支持度来得到频繁项集, 然后对数据库进行第二次扫描来建立 FP-tree 在建树过程中, 所有项的支持度按降序排列, 插入到树中, 这样支持度大的项可以共享, 从而建立一棵最小的树, 这棵树中包含的是数据库中长度为 1 的频繁项集 然后从该树的最后一个结点 x( 叶子结点 ) 开始, 从下向上依次产生这些结点的子数据库 ( 即以该结点 x 为前缀的项集 ), 将该子数据库中每个项集的支持度与用户指定的阈值比较即可知该项集是否频繁 ; 对于 x 的子数据库中的项 y 可以产生 {x, y} 的子数据库, 将这种方法运用到 FP-tree 的每个结点中, 就可以得到所有的频繁项集

52 2018/5/6 55 FP-growth 算法, [Han, Pei, and Yin 2000] 示例 找出支持度 >=3 的频繁项集 1 原始 database 2 database 中 item 的支持度降序排列 3 item set 根据 item 的支持度降序排列生成 FP Tree 根节点 依次产生以节点 x 为前缀的子树 直至完成整棵树的建立

53 2018/5/6 57 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

54 2018/5/6 58 不确定数据频繁项集挖掘 不确定数据广泛存在 ( 动态数据 流数据 ) 用户位置数据如来自 GPS 数据的位置信息 用户兴趣 热点信息 产品 实时路况 物联网中各类传感器的数据

55 2018/5/6 59 基于不确定数据的频繁项集的挖掘方法 在传统的数据库中, 如果 X 是一个频繁项集, 那么它的支持度 sup(x) 必须大于用户给定的最小支持度 min_sup 在不确定性数据库中, 由于项集以概率形式存在, 所以用期望支持度 esup(x ) 代替项集 x 在不确定性数据库中的支持度 最为经典的算法是基于先验的 Apriori 算法和基于树结构的 FP_Growth 算法均已有改进算法 A-priori U-Apriori FP-growth UF-growth

56 2018/5/6 60 数据流中的频繁项集分析 面临的问题 : 1) 数据流可能速率很高, 无法存储整个流进行分析 2) 随时间的推移, 频繁项集也会发生变化 解决方法 : 1) 抽样技术 抽样 : 定期收集数据流, 存为文件后, 再分析 分析期间, 不再将数据流放入正在分析的文件 不过, 可以存储为另一个文件, 供下次分析 2) 窗口的衰减模型 窗口衰减模型 : 可以将倒数第 i 个出现的购物篮赋予 (1-c) i 的权值 这样就形成了流中的一个衰减窗口 当某个项集出现在当前购物篮中, 并且其所有真子集已经开始计数, 那么此时开始对此项集开始计数 这样需要计数的项集的规模就不会太大 由于窗口不断衰减, 将所有计数值都乘以 (1-c), 并去掉计数低于 1/2 的项集

57 2018/5/6 61 小结 : 频繁项集挖掘 确定数据的频繁项集的挖掘 A-Priori [1994] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 支持度为概率值 期望支持度 esup(x ) A-priori U-Apriori FP-growth UF-growth 1) 抽样技术 2) 窗口的衰减模型

58 2018/5/6 62 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

59 2018/5/6 63 哈希函数 : 定义 散列函数 H 是一个公开的函数, 它将任意长度的消息 M 变换为固定长度的散列码 h h=h (M) M: 变长消息,H(M): 定长的散列值 散列函数是一种算法, 算法的输出内容称为散列码或者消息摘要 散列函数又称为 : 哈希 ( Hash ) 函数 数字指纹 (Digital fingerprint) 压缩 (Compression) 函数 数据认证码 (Data Authentication Code) 等

60 2018/5/6 64 哈希函数 : 哈希的常用算法 将一个消息串映射为一个整数的简单思路 h(k) = k mod m h(k) = k(k+3) mod m 著名的 Hash 算法 MD5 和 SHA1 应用最广泛, 它们都是以 MD4 为基础设计 MD4 (RFC 1320) 是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写 它适用在 32 位字长的处理器上用高速软件实现 -- 它是基于 32 位操作数的位操作来实现的 MD5 (RFC 1321) 是 Rivest 于 1991 年对 MD4 的改进版本 它对输入仍以 512 位分组, 其输出是 4 个 32 位字的级联, 与 MD4 相同 MD5 比 MD4 来得复杂, 并且速度较之要慢一点, 但更安全, 在抗分析和抗差分方面表现更好 SHA1 是由 NIST NSA 设计为同 DSA 一起使用的, 它对长度小于 2^64 位的输入, 产生长度为 160bit 的散列值, 因此抗穷举 (brute-force) 性更好 SHA-1 设计时基于和 MD4 相同原理, 并且模仿了该算法

61 2018/5/6 65 为什么要使用哈希函数 %A2%E7%A0%81&rsv_spt=1&rsv_iqid=0xcb f78&issp=1&f=8&rsv_bp =1&rsv_idx=2&ie=utf- 8&rqlang=cn&tn= _5_dg&rsv_enter=1&oq=%25E5%2590%2588%25E8%25 82%25A5%25E6%2591%25A9%25E6%258B%259C%2520%25E5%2585%2591%25 E6%258D%25A2%25E7%25A0%2581&rsv_t=41b0PNbxN9XytGpnTAti%2F17a8oud rvsikypbtyrkmjjwqpq9xaxs3wrzgghzt4%2bwvxrtrw&inputt=223&rsv_pq=d56 7c fc9e&rsv_sug3=135&rsv_sug2=0&rsv_sug4=223

62 2018/5/6 66 哈希函数应用示例 : 信息指纹 任何一段信息文字, 都可以对应一个不太长的随机数, 作为区别它和其它信息的指纹 (Fingerprint) 只要算法设计的好, 任何两段信息的指纹都很难重复, 就如同人类的指纹一样 信息指纹在加密 信息压缩和处理中有着广泛的应用 URL 的信息指纹 :( 网络爬虫需要存储 URL) 假定网址的平均长度为一百个字符, 那么存贮 200 亿个网址本身至少需要 2 TB, 即两千 GB 的容量 如果能够找到一个函数, 将这 200 亿个网址随机地映射到 128 二进位即 16 个字节的整数空间, 这样每个网址只需要占用 16 个字节 吴军 数学之美 第 16 章信息指纹及其应用

63 2018/5/6 67 哈希函数应用示例 百度面试题 一个大的含有 50M 个 URL 的记录, 一个小的含有 500 个 URL 的记录, 找出两个记录里相同的 URL 先用包含 500 个 URL 的文件创建一个 hash_set 然后遍历 50M 的 URL 记录, 如果 URL 在 hash_set 中, 则输出此 URL 并从 hash_set 中删除这个 URL 所有输出的 URL 就是两个记录里相同的 url

64 2018/5/6 68 数据的存储 : 数组 链表 哈希表 数组 : 存储区间是连续的, 占用内存严重, 故空间复杂的很大 但数组的二分查找时间复杂度小, 为 O(1); 数组的特点是 : 寻址容易, 插入和删除困难 ; 链表 : 存储区间离散, 占用内存比较宽松, 故空间复杂度很小, 但时间复杂度很大, 达 O(N) 链表的特点是 : 寻址困难, 插入和删除容易 哈希表 : 能否综合两者的特性, 做出一种寻址容易, 插入删除也容易的数据结构? 答案是肯定的, 这就是哈希表 哈希表 ((Hash table) 既满足了数据的查找方便, 同时不占用太多的内容空间, 使用也十分方便

65 2018/5/6 69 哈希表 (Hash table) 散列表 (Hash table, 也叫哈希表 ), 是根据关键码值 (Key value) 而直接进行访问的数据结构 它通过把关键码值映射到表中一个位置来访问记录, 以加快查找的速度 哈希法又称散列法 杂凑法以及关键字地址计算法等, 相应的表称为哈希表 这种方法的基本思想是 : 首先在元素的关键字 k 和元素的存储位置 p 之间建立一个对应关系 f, 使得 p=f(k),f 称为哈希函数 创建哈希表时, 把关键字为 k 的元素直接存入地址为 f(k) 的单元 ; 以后当查找关键字为 k 的元素时, 再利用哈希函数计算出该元素的存储位置 p=f(k), 从而达到按关键字直接存取元素的目的 当关键字集合很大时, 关键字值不同的元素可能会映象到哈希表的同一地址上, 即 k1 k2, 但 H(k1)=H(k2), 这种现象称为冲突, 此时称 k1 和 k2 为同义词

66 2018/5/6 70 哈希表 (Hash table): 哈希函数构造 构造原则 :1 函数本身便于计算 ;2 计算出来的地址分布均匀, 即对任一关键字 k,f(k) 对应不同地址的概率相等, 目的是尽量减少冲突 1. 直接寻址法 : 取关键字或关键字的某个线性函数值为散列地址 即 H(key)=key 或 H(key) = a key + b, 其中 a 和 b 为常数 2. 数字分析法 : 如果事先知道关键字集合, 可以从关键字中选出分布较均匀的若干位, 构成哈希地址 3. 平方取中法 : 当无法确定关键字中哪几位分布较均匀时, 可以先求出关键字的平方值, 然后按需要取平方值的中间几位作为哈希地址 4. 折叠法 : 将关键字分割成位数相同的几部分, 最后一部分位数可以不同, 然后取这几部分的叠加和 ( 去除进位 ) 作为散列地址 5. 随机数法 : 选择一随机函数, 取关键字的随机值作为散列地址, 通常用于关键字长度不同的场合 6. 除留余数法 : 取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址 即 H(key) = key MOD p, p<=m

67 2018/5/6 71 哈希表 (Hash table): 冲突处理 1. 开放定址法 也称再散列法, 当关键字 key 的哈希地址 p=h(key) 出现冲突时, 以 p 为基础, 产生另一个哈希地址 p1, 如果 p1 仍然冲突, 再以 p1 为基础, 产生另一个哈希地址 p2,, 直到找出一个不冲突的哈希地址 pi 2. 再哈希法 同时构造多个不同的哈希函数 :H i =RH 1 (key) i=1,2,,k 当哈希地址 H i =RH 1 (key) 发生冲突时, 再计算 H i =RH 2 (key), 直到冲突不再产生 3. 链地址法 将所有哈希地址为 i 的元素构成一个称为同义词链的单链表, 并将单链表的头指针存在哈希表的第 i 个单元中, 因而查找 插入和删除主要在同义词链中进行 链地址法适用于经常进行插入和删除的情况 4. 建立公共溢出区 将哈希表分为基本表和溢出表两部分, 凡是和基本表发生冲突的元素, 一律填入溢出表

68 2018/5/6 72 哈希表应用示例 百度面试题 : 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来, 每个查询串的长度为 字节 假设目前有一千万个记录 ( 这些查询串的重复度比较高, 虽然总数是 1 千万, 但如果除去重复, 不超过 3 百万个 一个查询串的重复度越高, 说明查询它的用户越多, 也就是越热门 请统计最热门的 10 个查询串, 要求使用的内存不能超过 1G 虽然有一千万个 Query, 但是由于重复度比较高, 因此事实上只有 300 万的 Query, 每个 Query255Byte, 因此我们可以考虑把他们都放进内存中去, 而现在只是需要一个合适的数据结构,Hash Table 是一种可能的选择, 因为 Hash Table 的查询速度非常的快, 几乎是 O(1) 的时间复杂度 那么, 我们的算法就有了 : 维护一个 Key 为 Query 字串,Value 为该 Query 出现次数的 HashTable, 每次读取一个 Query, 如果该字串不在 Table 中, 那么加入该字串, 并且将 Value 值设为 1; 如果该字串在 Table 中, 那么将该字串的计数加一即可

69 2018/5/6 73 小结 :Hash function Hash table Hash function 又称为 : 哈希 ( Hash ) 函数 数字指纹 (Digital fingerprint) 压缩 (Compression) 函数 数据认证码 ( Data Authentication Code) 等 h=h (M), M: 变长消息,H(M): 定长的散列值 MD5 和 SHA1 Hash table 创建哈希表时, 把关键字为 k 的元素直接存入地址为 f(k) 的单元 ; 以后当查找关键字为 k 的元素时, 再利用哈希函数计算出该元素的存储位置 p=f(k), 从而达到按关键字直接存取元素的目的 冲突 :k1 k2, 但 H(k1)=H(k2)

70 2018/5/6 74 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

71 2018/5/6 75 需求 : 判断一个元素是否在一个集合中 在日常生活中, 包括在设计计算机软件时, 我们经常要判断一个元素是否在一个集合中 比如在字处理软件中, 需要检查一个英语单词是否拼写正确 ( 也就是要判断它是否在已知的字典中 ); 在 FBI, 一个嫌疑人的名字是否已经在嫌疑名单上 ; 电子邮件系统中, 判断 地址是否在黑名单中 ; 在网络爬虫里, 一个网址是否被访问过等等 最直接的方法就是将集合中全部的元素存在计算机中, 遇到一个新元素时, 将它和集合中的元素直接比较即可 吴军 数学之美 第 23 章布隆过滤器

72 2018/5/6 76 集合巨大时哈希表效率低 集合巨大 : 如一个象 yahoo, Hotmail 和 Gmail 那样的 提供商, 总是需要过滤来自发送垃圾邮件的人 (spamer) 的垃圾邮件 一个办法就是记录下那些发垃圾邮件的 地址 由于那些发送者不停地在注册新的地址, 全世界少说也有几十亿个发垃圾邮件的地址, 将他们都存起来则需要大量的网络服务器 一般来讲, 计算机中的集合是用哈希表来存储的 好处是快速准确, 缺点是费存储空间 当集合比较小时, 问题不显著, 但是当集合巨大时, 哈希表存储效率低的问题就显现出来了 如果用哈希表, 每存储一亿个 地址, 就需要 1.6GB 的内存 ( 用哈希表实现的具体办法是将每一个 地址对应成一个八字节的信息指纹, 然后将这些信息指纹存入哈希表, 由于哈希表的存储效率一般只有 50%, 因此一个 地址需要占用十六个字节 一亿个地址大约要 1.6GB, 即十六亿字节的内存 ) 因此存贮几十亿个邮件地址可能需要上百 GB 的内存 吴军 数学之美 第 23 章布隆过滤器

73 2018/5/6 77 布隆过滤器 (Bloom Filter) 布隆过滤器是由布隆 (Burton Howard Bloom) 在 1970 年提出的 它实际上是由一个很长的二进制向量和一系列随机映射函数组成, 布隆过滤器可以用于检索一个元素是否在一个集合中 它的优点是空间效率和查询时间都远远超过一般的算法, 缺点是有一定的误识别率 ( 假正例 False positives, 即 Bloom Filter 报告某一元素存在于某集合中, 但是实际上该元素并不在集合中 ) 和删除困难, 但是没有识别错误的情形 ( 即假反例 False negatives, 如果某个元素确实没有在该集合中, 那么 Bloom Filter 是不会报告该元素存在于集合中的, 所以不会漏报 ) 吴军 数学之美 第 23 章布隆过滤器

74 2018/5/6 78 布隆过滤器工作原理布隆过滤器的建立 假定我们存储一亿个电子邮件地址, 我们先建立一个十六亿二进制 ( 比特 ), 即两亿字节的向量, 然后将这十六亿个二进制全部设置为零 对于每一个电子邮件地址 X, 我们用八个不同的随机数产生器 (F1,F2,...,F8) 产生八个信息指纹 (f1, f2,..., f8)

75 2018/5/6 79 布隆过滤器工作原理布隆过滤器的建立 再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2,...,g8 现在我们把这八个位置的二进制全部设置为一 当我们对这一亿个 地址都进行这样的处理后 一个针对这些 地址的布隆过滤器就建成了

76 布隆过滤器原理检测一个可疑的电子邮件地址 2018/5/6 80 现在, 让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中 我们用相同的八个随机数产生器 (F1, F2,..., F8) 对这个地址产生八个信息指纹 s1,s2,...,s8, 然后将这八个指纹对应到布隆过滤器的八个二进制位, 分别是 t1,t2,...,t8 如果 Y 在黑名单中, 显然,t1,t2,..,t8 对应的八个二进制一定是一 这样在遇到任何在黑名单中的电子邮件地址, 我们都能准确地发现 布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址 但是, 它有一条不足之处 也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中, 因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位 好在这种可能性很小 我们把它称为误识概率 在上面的例子中, 误识概率在万分之一以下

77 2018/5/6 81 布隆过滤器思想应用示例 百度面试题 2.5 亿个 int 数, 可能有相同的 统计出这里头不同的数有多少个? 只有 2g 内存 百度面试题 给 40 亿个不重复的 unsigned int 的整数, 没排过序的, 然后再给几个数, 如何快速判断这几个数是否在那 40 亿个数当中?

78 布隆过滤器 (Bloom Filter) 详解 /5/6 82 小结 : Bloom Filter Bloom Filter 优点 相比于其它的数据结构, 布隆过滤器在空间和时间方面都有巨大的优势 布隆过滤器存储空间和插入 / 查询时间都是常数 另外, Hash 函数相互之间没有关系, 方便由硬件并行实现 布隆过滤器不需要存储元素本身, 在某些对保密要求非常严格的场合有优势 Bloom Filter 缺点 误算率 (False Positive) 随着存入的元素数量增加, 误算率随之增加 但是如果元素数量太少, 则使用散列表足矣 Bloom Filter 用例 Google 著名的分布式数据库 Bigtable 用布隆过滤器来查找不存在的行或列, 以减少磁盘查找的 IO 次数 Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器 Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据 SPIN 模型检测器用布隆过滤器在大规模验证问题时跟踪可达状态空间 Google Chrome 浏览器使用了布隆过滤器加速安全浏览服务

79 2018/5/6 83 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

80 2018/5/6 84 重复文档 / 近似重复文档 网上到处都是相同的内容 完全复制 Duplication 可以通过指纹 (fingerprints) 来检测精确匹配 大多数情况是近似重复 Near-Duplication E.g., 两份文本仅仅是日期不同 通过编辑距离计算语法上的相似性 通过一定的阈值来检测近似复制 E.g., Similarity > 80% => 文档近似复制 通过阈值来检测是不可传递的 (AB 近似,BC 近似不能推断 AC 近似 )

81 2018/5/6 85 相似性计算 特征 对文档进行分割 ( 自然或人造的断点来断开 ) 搭叠 Shingles (N 元词 Word N-Grams) a rose is a rose is a rose a_rose_is_a rose_is_a_rose is_a_rose_is a_rose_is_a 文档 ( 即 Shingles 集合 ) 间相似性 交集 Set intersection 交集的大小 / 并集的大小 给定正整数 k 及文档 d 的一个词项序列, 可以定义文档 d 的 k-shingle 为 d 中所有 k 个连续词项构成的序列 直观上看, 如果两个文档的 shingle 集合几乎一样, 那么它们就满足近似重复 Jaccard 系数 : 衡量重复度

82 2018/5/6 86 搭叠 + 交集 计算所有文档对之间搭叠的精确交集是非常费时而且难以处理的 使用一种聪明的方式从 Shingles 中选出一个子集 ( 素描 sketch) 来近似计算 在素描 Sketch 上计算交集大小 / 并集大小 Doc A Doc B Shingle set A Shingle set B Sketch A Sketch B Jaccard

83 2018/5/6 87 文档的素描 (Sketch) 为每篇文档生成一个素描向量 sketch vector ( 大小约为 ~200) 相同向量个数 t ( 一般 80%) 判定为近似 near duplicates 对文档 D, sketch D [ i ] 如下 : f 把所有的搭叠 shingles 映射到 {0..2 m }(e.g., f = fingerprinting 计算一个 m 位的摘要 ) p i 是 {0.. 2 m } 的随机置换 ( 集合对象随机排序 ) 对 D 中所有 singles s 选择 MIN {p i (f(s))}

84 2018/5/6 88 计算 Sketch[i] for Doc1 Document bit f(shingles) 随机置换 选最小值

85 2018/5/6 89 测试 if Doc1.Sketch[i] = Doc2.Sketch[i] Document 1 Document A 2 64 B 2 64 是否相等? 进行 200 次随机置换 : p 1, p 2, p 200

86 2018/5/6 90 本质上是对 shingle 集合进行抽样 Document 1 Document A B A = B iff the shingle with the MIN value in the union of Doc1 and Doc2 is common to both (i.e., lies in the intersection) 定理 19-1: A = B 发生的概率 = 交集大小 / 并集大小 (Size_of_intersection / Size_of_union)

87 2018/5/6 91 小结 : 近似重复检测 Shingle 算法的核心思想是将文件相似性问题转换为集合的相似性问题 数量较大时, 对 shingle 集合进行抽样, 以降低空间和时间计算复杂性 shingle 取样主要有三种方法, 即 Min-Wise,Modm, 和 Mins Mins 技术先将 shingle 和整数集进行映射, 然后从中选择最小 s 个元素组成取样集合 此外, 还可以使用 shingle 的 hash 值代表 shingle 进行相似性计算, 能够节省一定计算开销

88 2018/5/6 92 今日内容 : 数据挖掘经典算法概述 (2) 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

89 2018/5/6 93 谢谢大家!