基于数据挖掘技术的保险行业决策分析研究(2)
2015-12-22 01:02
导读：由于Apriori算法存在时间空间复杂度高及产生大量冗余规则两大缺陷。因此本项目通过利用一个模式树结构来降低Apriori算法的存储复杂度,并同时减少冗余规
由于Apriori算法存在时间空间复杂度高及产生大量冗余规则两大缺陷。因此本项目通过利用一个模式树结构来降低Apriori算法的存储复杂度,并同时减少冗余规则的出现。
3.1 一个模式树的结构
root是一个标为“null”的根结点,root以下是作为根结点的孩子的项目前缀子树集合,以及项目头表组成;树中的每一结点包含四个域user_id,count,node_link,node_next。其中,user_id为user的标记(唯一标识一个user),count为该父结点到达该结点的路径的数目,node_link指向树中具有相同的user_id的下一个结点的下一结点,当下一个结点不存在时,node_link为null,node_next指向树中其子结点;项目头表的每一表项包含三个域:user_id,count,head of node,user_id与树中的定义相同,count为树中所有相同user_id之和,head of node指向树中具有相同user_id值的首结点的指针。
3.2 建立模式树
算法如下:
设事务数据库为A,其中的一个项集为Ai。
算法:Patterntree(tree,p),构造模式树
输入:用户事务数据库A
输出:用户模式树
Procedure Patterntree(T,p)
{create_ tree (T);//创建Pattern-Tree的根节点,以“null”标记
t=T; //t为当前结点
While A<>null do
{读入一个事务数据库项集Ai
while p !=null
do
{if p.user_id==t的祖先n.user_id
then
{ n.count=n.count+l;
t=n;
}
Elseif p.user_id==T的孩子c.user_id
then
{ c.count=c.count+ l;
t=c ;
}
else
insert_Patterntree(T,p) ;//把p作为新结点插入树中,作为当前结点的孩子结点
p=p.next;
}
}
}
（转载自http://www.ＮＳＥＡＣ.com中国科教评价网）
3.3 对模式树进行剪枝
模式树建立后,可能存在大量的冗余的分枝,为了保证数据挖掘结果不被这些冗余分枝产生的噪声所影响,因此需要对树进行剪枝,剔除噪声信息。
算法:SPT(Tree,a),通过调用此算法对模式树进行剪枝
//SPT为支持度模式树,即Supported Access Pattern Tree;a为项目头表
输入:模式树PatternTree,Min_Sup(模式树的最小支持度)
输出:经过修剪后的支持度模式树SPT,模式B={bi|i=1,2,3……n｝
SPT(Tree,a)
