2024年4月28日发(作者：)

web挖掘一些经典算法总结

l、Apriori算法

Apriori算法是1994年由l等人提出来的,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；

步骤2 for 网络结构中的点数n｛根据网络结构，获取当前点x的度数d x ，

计算Cx ＝d（x）/n－１；将＜节点编号x，Cx ＞插入中心性映射表；｝

步骤3 return网站用户中心性映射表．

算法2 构建预测对象集

预测对象集的构建过程为：预测对象集中记录的是作为预测对象的集合，该

集合具有一定的阈值．对于每个用户发布的信息均进行预测价值判断，当已存储

的预测对象超过阈值时，若新页面信息发布者的中心性高于预测对象集中信息的

发布者，则将中心性最小发布者的信息替换出来，将新页面信息加入预测对象

集．算法伪码如下．

输入：用户中心性映射表；用户新发布的信息

队列new_page；阈值．

输出：预测对象集Q．

步骤1 设置当前Q中最小中心性Cmin=0；

步骤2 new_page｛p1，p2，…，pn｝，

for每个pj∈用户x

｛ 查中心性映射表，得Cx；

if（Cx≥Cmin）｛

if（sizeof（Q）＜阈值）

预测对象集Q＝：Q＋pj；

else｛

pj 随机替换掉Q中具有最小中心

性用户发布的信息pmin；

重置Cmin；｝

｝

｝

步骤3 return Q．

算法3 PUR-SNS

经过ＰＵＲＭ的初始化和预测对象集的构建，ＰＵＲ-ＳＮＳ算法初始化工作已

完成，算法伪码如下．

输入：系统的缓存容量；预测对象集Q；用户访问请求队列R＝｛R１，R２，…，

Rn｝．

输出：缓存对象集S．

步骤1 for访问请求队列R＝｛R1，R2，…，Rn｝

｛ if（S＋Ri ＜系统的缓存容量）

S：＝S＋Ri；

else｛

选出S中键值最小的缓存对象Rx；

while（Rx∈Q）｛Rx ＝S中其余键值最小的对象；｝

S：＝S－Rx；

S：＝S＋Rj；

｝

｝

步骤2 return缓存对象集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，则初始状态概率矩阵 π=[ p1 p2 p3 ].

4. 隐含状态转移概率矩阵 A。描述了HMM模型中各个状态之间的转移概

率。其中Aij = P( Sj | Si ),1≤i,,j≤N.表示在 t 时刻、状态为 Si 的条件下，在 t+1 时

刻状态是 Sj 的概率。

5. 观测状态转移概率矩阵 B （英文名为Confusion Matrix，直译为混淆矩阵

不太易于从字面理解）。令N代表隐含状态数目，M代表可观测状态数目，则：

Bij = P( Oi | Sj ), 1≤i≤M,1≤j≤N.表示在 t 时刻、隐含状态是 Sj 条件下，观察状态

为 Oi 的概率。

总结：一般的，可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型。

隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这

些状态与隐含状态之间的概率关系。

⎟

⎠

⎞

⎜

⎜

⎜

⎝

⎛