web挖掘经典算法

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