树,即supported access pattern tree;a为项目头表
输入:模式树patterntree,min_sup(模式树的最小支持度)
输出:经过修剪后的支持度模式树spt,模式b={bi|i=1,2,3……n｝
spt(tree,a)
{ i=1;
while(ai!= null) // 为项目头表的某一项
{
if(ai.count>= min_sup)
then
{
模式bi= ai.head of node ;

p= ai.head of node ;//p指向ai在模式树中
的位置
while (p!= null and ai.count>= min_sup)
{
查找p的前缀基,将p的前缀基和p连接,构
成模式b;
if (bi.count>= min_sup)
then
{
//bi.count 为模式b中p与p的前缀基中
的最小计数
在模式bi中保留p及其前缀基;
bi = bi. node_link
}
else
{
根据模式b中的p及其前缀基删除
patterntree中的相应节点,重构子节点
与父节点,同时修改项目头表中的ai;
p=p. node_next//p指向 在模式树中的
下一个位置;
}
}
}
else
{
修改项目头结点的ai值;
删除模式树中相应的节点及其前缀基,重构父子
节点;
i++;
}
}
}
通过模式树的建立可以避免多次扫描事务数据库;同时利用count域有效的保留了项集的数目,避免大量产生频繁项集,对于减小空间时间复杂度起到了一定的作用。通过树形结构可以避免产生大量冗余规则。
通过对模式树的剪枝,可以减除在模式树产生过程中产生的大量冗余分枝,起到了减小空间复杂度的作用,同时可以利用输出模式b产生规则,避免了多项集的频繁出现,减小了时间复杂度。

4 结束语
本项目中通过模式树结构改进了apriori算法,弥补了apriori算法存在的缺陷。此种方法既能够对apriori算法从时间复杂度和空间复杂度上进行改进,同时又避免了中间规则的产生。本研究表明,通过利用一个模式树结构来降低apriori算法的存储复杂度,并同时减少冗余规则的出现,这对于apriori算法的改进是一种有效的措施。

参考文献
[1]邓纳姆.数据挖掘教程[m].郭崇慧,田凤占,靳晓明,等译.北京:清华大学出版社,2005.
[2]苏新宁,杨建林,江念南,等.数据仓库和数据挖掘[m].北京:清华大学出版社,2006.
[3]gal c s, kantor p b, shapira b. security informatics and terrorism: patrolling the web. amsterdam: ios press,2008.
[4]borges j, levene m. evaluating variable length markov chain models for analysis of user web navigation sessions.ieee transactions on knowledge and data engineering.2007,19(4): 441-452.

上一页  [1] [2]