《web挖掘经典算法》由会员分享，可在线阅读，更多相关《web挖掘经典算法（4页珍藏版）》请在金锄头文库上搜索。
1、web 挖掘一些经典算法总结l、Apriori 算法Apriori 算法是 1994 年由 R.Agrawal 等人提出来的 ,APriori 算法是关联规则挖掘的经典算法,后来的许多算法的思想都源于该算法。该算法的名字来源于算法中应用了频繁项集的先验知识,它有如下两个基本性质。(l)频繁模式的下闭包特性:频繁项集的任何非空子集也都是频繁的,例如: 若beer,diaPer,nuts是频繁的,则beer,di 即 er、diaPer,nuts和beer,nuts等也是频繁的。(2)Apriori 剪枝原理:如果一个项集是非频繁的 ,它的任一超集一定是非频繁的 ,故就不必再被产生和测试了。该算法
2、的基本思想:算法首先扫描一遍数据库计算各个 1-项集的支持度,从而得到频繁 1-项集 Ll,然后采用迭代合并的方式,生成 2 一项集,再次扫描数据库,计算 2-项集的支持度,得到频繁 2-项集玩,依次类推,分别找出频繁 3 一项集,直至不再产生新的频繁项集为止。在计算频繁卜项集 Lk(k=2,3,)时,先通过Lt-;自连接产生候选集 Ck,利用一定的剪枝策略缩减 Ck;在通过扫描数据库来计算候选集的出现频度,消除非频繁项,从而得到玩。Apriori 算法能够有效地产生所有关联规则,但该算法存在以下问题:(l)数据库扫描次数太多 ,每计算一次频繁 k 一项集,都需要扫描一次数据库。(2)产生的候
3、选集过大,虽然采取了一定的剪枝策略,但候选集仍较大。(3)计算候选集的支持度的工作量巨大。2、FP 一 Growth 算法FP 一 Growth 算法是由 Han 等人提出的基于频繁模式树(FP 一树)的频繁模式挖掘算法。FP 一树是一种高压缩比的存储结构,它将每个事物的频繁项按其频度从大到小排列,树中的每个节点都保存着该结点的频度计数,并将所有相同结点都连到头指针指向的链中。与 APriori 算法相比,该算法具有以下的特点:(1)采用 FP 一树存放数据库的主要信息、算法只需扫描数据库两次,然后将Markov 链和关联规则的用户访问预测算法信息以 FP 一树的形式存放在内存中,避免了多次扫
4、描数据库。(2)不需要产生候选集,从而减少了由于产生和测试候选集耗费的时间。对 FP 一树的挖掘是一个分而治之的过程:按照头指针表,沿着各个频繁项 p 的指针链遍历FP 一树,收集项 p 的所有不同前缀路径 (transformedprefixPaths),形成 p 的条件模式基,构造条件模式库和条件 FP 一树,如果条件 FP 一树只有一个分支,则将其结点进行合并得到频繁项集;否则继续递归挖掘直至得到条件 FP 一树。3、预测替换算法 PUR-SNS该算法的步骤如下1）初始化预测模型先根据用户的中心度，计算出每个用户的中心性2）构建预测模型根据用户的中心度，对每个用户发布的信息进行预测价值判
5、断，构建预测对象集 Q3）寻找替换对象由原有的替换算法在替换候选集中选出缓存对象中键值最小的对象 Rx4）若 RxQ，则该对象不被替换，退出替换候选集重复步骤）直至找到合适的替换对象，使缓存具有足够空间容纳新的请求5）将 Rx 替换掉，缓存新的请求算法 1预测模型（PURM）初始化PURM 的初始化过程为：根据计算每个用户的中心性，形成一张映射表，算法伪码如下输入：SNS 网络结构输出：网站用户中心性映射表步骤 1将网络中各点依次编号为 1，2，n；步骤 2for 网络结构中的点数 n根据网络结构，获取当前点 x 的度数 d x ，计算 Cx d（x）/n；将节点编号 x，Cx 插入中心性映射
6、表；步骤 3return 网站用户中心性映射表算法 2构建预测对象集预测对象集的构建过程为：预测对象集中记录的是作为预测对象的集合，该集合具有一定的阈值对于每个用户发布的信息均进行预测价值判断，当已存储的预测对象超过阈值时，若新页面信息发布者的中心性高于预测对象集中信息的发布者，则将中心性最小发布者的信息替换出来，将新页面信息加入预测对象集算法伪码如下输入：用户中心性映射表；用户新发布的信息队列 new_page；阈值输出：预测对象集 Q步骤 1设置当前 Q 中最小中心性 Cmin=0；步骤 2new_page p1， p2，pn ，for 每个 pj用户 x查中心性映射表，得 Cx；if（C
7、xCmin） if（sizeof（Q）阈值）预测对象集 Q：Qpj；elsepj 随机替换掉 Q 中具有最小中心性用户发布的信息 pmin；重置 Cmin；步骤 3return Q算法 3PUR-SNS经过的初始化和预测对象集的构建，-算法初始化工作已完成，算法伪码如下输入：系统的缓存容量；预测对象集 Q；用户访问请求队列R R， R，Rn 输出：缓存对象集 S步骤 1for 访问请求队列 RR1，R2，Rnif（SRi 系统的缓存容量）S：SRi；else选出 S 中键值最小的缓存对象 Rx；while（RxQ） Rx S 中其余键值最小的对象；S： SRx；S： SRj；步骤 2retur
8、n 缓存对象集 S4、隐马尔可夫模型（HMM）马尔可夫（Markov ）过程是指在事件的发展过程中，若每次状态的转移都仅与前一时刻的状态有关，而与过去的状态无关，或者说状态转移过程是无后效性的，则这样的状态转移过程就称为马尔可夫过程。马尔可夫预测法就是一种预测事件发生的概率的方法，它是基于马尔可夫链，根据事件的目前状况预测其将来各个时刻 （或时期）变动状况的一种预测方法。隐马尔可夫模型的状态则不是确定可测的，而是有一定的观测概率分布，因此根据观测量无法确定具体是哪个状态，隐马尔可夫模型（HMM）可以用五个元素来描述，包括 2 个状态集合和 3 个概率矩阵：1. 隐含状态 S，这些状态之间满足马
9、尔可夫性质，是马尔可夫模型中实际所隐含的状态。这些状态通常无法通过直接观测而得到。 （例如 S1、S2 、S3 等等)2. 可观测状态 O，在模型中与隐含状态相关联，可通过直接观测而得到。(例如 O1、O2 、O3 等等，可观测状态的数目不一定要和隐含状态的数目一致。）3. 初始状态概率矩阵 ，表示隐含状态在初始时刻 t=1 的概率矩阵，(例如t=1 时， P(S1)=p1、P(S2)=P2 、P(S3)=p3，则初始状态概率矩阵 = p1 p2 p3 .4. 隐含状态转移概率矩阵 A。描述了 HMM 模型中各个状态之间的转移概率。其中 Aij = P( Sj | Si ),1i,jN.表示在 t 时刻、状态为 Si 的条件下，在 t+1 时刻状态是 Sj 的概率。5. 观测状态转移概率矩阵 B （英文名为 Confusion Matrix，直译为混淆矩阵不太易于从字面理解） 。令 N 代表隐含状态数目， M 代表可观测状态数目，则：Bij = P( Oi | Sj ), 1iM,1jN.表示在 t 时刻、隐含状态是 Sj 条件下，观察状态为 Oi 的概率。总结：一般的，可以用 =(A,B,)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这些状态与隐含状态之间的概率关系。
