网站设计的网站,腾讯云网站建设教学视频教程,wordpress ftp备份,徐州模板建站定制网站转载自 关联分析#xff1a;FP-Growth算法关联分析又称关联挖掘#xff0c;就是在交易数据、关系数据或其他信息载体中#xff0c;查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。关联分析的一个典型例子是购物篮分析。通过发现顾客放入购物篮中不同…转载自 关联分析FP-Growth算法关联分析又称关联挖掘就是在交易数据、关系数据或其他信息载体中查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。关联分析的一个典型例子是购物篮分析。通过发现顾客放入购物篮中不同商品之间的联系分析顾客的购买习惯。比如67%的顾客在购买尿布的同时也会购买啤酒。通过了解哪些商品频繁地被顾客同时购买可以帮助零售商制定营销策略。关联分析也可以应用于其他领域如生物信息学、医疗诊断、网页挖掘和科学数据分析等。1. 问题定义图1 购物篮数据的二元表示图1表示顾客的购物篮数据其中每一行是每位顾客的购物记录对应一个事务而每一列对应一个项。令I{i1, i2, ... , id}是购物篮数据中所有项的集合而T{t1, t2, ... , tN}是所有事务的集合。每个事务ti包含的项集都是I的子集。在关联分析中包含0个或多个项的集合被称为项集itemset。所谓的关联规则是指形如X→Y的表达式其中X和Y是不相交的项集。在关联分析中有两个重要的概念——支持度support和置信度confidence。支持度确定规则可以用于给定数据集的频繁程度而置信度确定Y在包含X的事务中出现的频繁程度。支持度s和置信度c这两种度量的形式定义如下公式1其中N是事务的总数。关联规则的支持度很低说明该规则只是偶然出现没有多大意义。另一方面置信度可以度量通过关联规则进行推理的可靠性。因此大多数关联分析算法采用的策略是
1频繁项集产生其目标是发现满足最小支持度阈值的所有项集这些项集称作频繁项集。
2规则的产生其目标是从上一步发现的频繁项集中提取所有高置信度的规则这些规则称作强规则。2. 构建FP-treeFP-growth算法通过构建FP-tree来压缩事务数据库中的信息从而更加有效地产生频繁项集。FP-tree其实是一棵前缀树按支持度降序排列支持度越高的频繁项离根节点越近从而使得更多的频繁项可以共享前缀。图2 事务型数据库图2表示用于购物篮分析的事务型数据库。其中ab...p分别表示客户购买的物品。首先对该事务型数据库进行一次扫描计算每一行记录中各种物品的支持度然后按照支持度降序排列仅保留频繁项集剔除那些低于支持度阈值的项这里支持度阈值取3从而得到(f:4)(c:4)(a:3)(b:3)(m:3(p:3)由于支持度计算公式中的N是不变的所以仅需要比较公式中的分子。图2中的第3列展示了排序后的结果。FP-tree的根节点为null不表示任何项。接下来对事务型数据库进行第二次扫描从而开始构建FP-tree第一条记录fcamp对应于FP-tree中的第一条分支(f:1)(c:1)(a:1)(m:1)(p:1)图3 第一条记录由于第二条记录fcabm与第一条记录有相同的前缀fca因此fca的支持度分别加一同时在(a:2)节点下添加节点(b:1)(m:1)。所以FP-tree中的第二条分支是(f:2)(c:2)(a:2)(h:1)(m:1)图4 第二条记录第三条记录fb与前两条记录相比只有一个共同前缀f因此只需要在(f:3)下添加节点b:1图5 第三条记录第四条记录cbp与之前所有记录都没有共同前缀因此在根节点下添加节点(c:1)(b:1)(p:1)图6 第四条记录类似地将第五条记录fcamp作为FP-tree的一个分支更新相关节点的支持度图7 第五条记录为了便于对整棵树进行遍历建立一张项的头表an item header table。这张表的第一列是按照降序排列的频繁项。第二列是指向该频繁项在FP-tree中节点位置的指针。FP-tree中每一个节点还有一个指针用于指向相同名称的节点图8 FP-tree综上FP-tree的节点可以定义为
1234567891011class TreeNode {private: String name; // 节点名称 int count; // 支持度计数 TreeNode *parent; // 父节点 VectorTreeNode * children; // 子节点 TreeNode *nextHomonym; // 指向同名节点 ...}3. 从FP-tree中挖掘频繁模式Frequent Patterns我们从头表的底部开始挖掘FP-tree中的频繁模式。在FP-tree中以p结尾的节点链共有两条分别是(f:4)(c:3)(a:3)(m:2)(p:2)和(c:1)(b:1)(p:1)。其中第一条节点链表表示客户购买的物品清单fcamp在数据库中共出现了两次。需要注意到是尽管fca在第一条节点链中出现了3次单个物品f出现了4次但是它们与p一起出现只有2次所以在条件FP-tree中将(f:4)(c:3)(a:3)(m:2)(p:2)记为(f:2)(c:2)(a:2)(m:2)(p:2)。同理第二条节点链表示客户购买的物品清单cbp在数据库中只出现了一次。我们将p的前缀节点链(f:2)(c:2)(a:2)(m:2)和(c:1)(b:1)称为p的条件模式基conditional pattern base。我们将p的条件模式基作为新的事务数据库每一行存储p的一个前缀节点链根据第二节中构建FP-tree的过程计算每一行记录中各种物品的支持度然后按照支持度降序排列仅保留频繁项集剔除那些低于支持度阈值的项建立一棵新的FP-tree这棵树被称之为p的条件FP-tree图9 p的条件FP-tree从图9可以看到p的条件FP-tree中满足支持度阈值的只剩下一个节点(c:3)所以以p结尾的频繁项集有(p:3)(cp:3)。由于c的条件模式基为空所以不需要构建c的条件FP-tree。在FP-tree中以m结尾的节点链共有两条分别是(f:4)(c:3)(a:3)(m:2)和(f:4)(c:3)(a:3)(b:1)(m:1)。所以m的条件模式基是(f:2)(c:2)(a:2)和(f:1)(c:1)(a:1)(b:1)。我们将m的条件模式基作为新的事务数据库每一行存储m的一个前缀节点链计算每一行记录中各种物品的支持度然后按照支持度降序排列仅保留频繁项集剔除那些低于支持度阈值的项建立m的条件FP-tree:图10 m的条件FP-tree与p不同m的条件FP-tree中有3个节点所以需要多次递归地挖掘频繁项集mine((f:3)(c:3)(a:3)|(m:3))。按照(a:3)(c:3)(f:3)的顺序递归调用mine((f:3)(c:3)|am)mine((f:3)|cm)mine(null|fm)。由于(m:3)满足支持度阈值要求所以以m结尾的频繁项集有{(m:3)}。图11 节点(am)的条件FP-tree从图11可以看出节点(am)的条件FP-tree有2个节点需要进一步递归调用mine((f:3)|cam)和mine(null|fam)。进一步递归mine((f:3)|cam)生成mine(null|fcam)。因此以(am)结尾的频繁项集有{(am:3)(fam:3)(cam:3)(fcam:3)}。图 12 节点(cm)的条件FP-tree从图12可以看出节点(cm)的条件FP-tree只有1个节点所以只需要递归调用mine(null|fcm)。因此以(cm)结尾的频繁项集有{(cm:3)(fcm:3)}。同理以(fm)结尾的频繁项集有{(fm:3)}。在FP-tree中以b结尾的节点链共有三条分别是(f:4)(c:3)(a:3)(b:1)(f:4)(b:1)和(c:1)(b:1)。由于节点b的条件模式基(f:1)(c:1)(a:1)(f:1)和(c:1)都不满足支持度阈值所以不需要再递归。因此以b结尾的频繁项集只有(b:3)。同理可得以a结尾的频繁项集{(fa:3)(ca:3)(fca:3)(a:3)}以c结尾的频繁项集{(fc:3)(c:4)}以f结尾的频繁项集{(f:4)}。4. 算法实现
声明FP-tree节点
class TreeNode
{//Constructors-Destructors
public:TreeNode();TreeNode(string);~TreeNode();//Member variables
private:string nodeName;int supportCount;TreeNode *parentNode;vectorTreeNode * childNodeList;TreeNode *nextHomonymNode;//Member functions
public:string getName();void setName(string);int getSupportCount() const;void setSupportCount(int);TreeNode* getParentNode() const;void setParentNode(TreeNode*);vectorTreeNode* getChildNodeList() const;void addChild(TreeNode*);TreeNode* findChildNode(string) const;void setChildren(vectorTreeNode*);void printChildrenNames() const;TreeNode* getNextHomonym() const;void setNextHomonym(TreeNode *nextHomonym);void countIncrement(int);
};构建HeaderTable
//HeaderTable存储事务数据库的数据
vectorTreeNode* FPTree::buildHeaderTable(vectorvectorstring transRecords)
{vectorTreeNode* F1; //存储满足支持度阈值的节点并按照支持度降序排列支持度相等的情况下按照字母顺序排序所以构建的FP-tree与论文有所不同但是最终生成的频繁项集是一样的if (transRecords.size() 0){mapstring, TreeNode* mp;//calculate supportCount of every transRecordsfor (vectorstring record : transRecords){for (string item : record){//if item not in map, put item into map and set supportCount oneif (mp.find(item) mp.end()){TreeNode *node new TreeNode(item);node-setSupportCount(1);mp.insert(mapstring, TreeNode*::value_type(item, node));}//if item in map, supportCount plus one else{mp.find(item)-second-countIncrement(1);}}}//put TreeNodes whose supportCount greater than minSupportThreshold into vector F1for (auto iterator mp.begin(); iterator ! mp.end(); iterator){if (iterator-second-getSupportCount() minSupportThreshold){//cout iterator-second iterator-second-getSupportCount() endl;F1.push_back(iterator-second);}}//sort vector F1 by supportCountsort(F1.begin(), F1.end(), sortBySupportCount);}return F1;
}构建FP-tree
TreeNode* FPTree::buildTree(vectorvectorstring transRecords, vectorTreeNode* F1)
{TreeNode *root new TreeNode(); //根节点rootfor (vectorstring transRecord : transRecords){//拷贝transRecord到record vectorstring record;for (auto iter transRecord.begin(); iter ! transRecord.end(); iter){record.push_back(*iter);}record sortedByF1(record, F1); //根据F1中存储的频繁项集将record按照支持度降序排列并且仅保留频繁项集剔除那些低于支持度阈值的项//顺序比较record中的节点和FP-tree中的节点如果record中的节点已经存在于FP-tree中将该节点的支持度加一继续比较下一个节点否则调用addNodes来添加剩余节点到FP-tree中TreeNode *subTreeRoot root;TreeNode *tmpRoot nullptr;if (!root-getChildNodeList().empty()){while (!record.empty() (tmpRoot subTreeRoot-findChildNode(*(record.begin()))) ! nullptr){tmpRoot-countIncrement(1);subTreeRoot tmpRoot;record.erase(record.begin());}}addNodes(subTreeRoot, record, F1);}return root;
}添加节点
void FPTree::addNodes(TreeNode *ancestor, vectorstring *record, vectorTreeNode* F1)
{if (!record-empty()){while (!record-empty()){string item *(record-begin());record-erase(record-begin());TreeNode *leafNode new TreeNode(item);leafNode-setSupportCount(1);leafNode-setParentNode(ancestor);ancestor-addChild(leafNode);for (TreeNode *f1 : F1){if (f1-getName() item){ while (f1-getNextHomonym() ! NULL){f1 f1-getNextHomonym();}f1-setNextHomonym(leafNode);break;}}addNodes(leafNode, record, F1);}}
}sortedByF1
vectorstring FPTree::sortedByF1(vectorstring transRecord, vectorTreeNode* F1)
{//如果item是频繁项则一定对应于F1中的序号按照该序号对item进行排序存储到rest中mapstring, int mp;for (string item : transRecord){for (int i 0; i F1.size(); i){TreeNode *tNode F1[i];if (tNode-getName() item){mp.insert(mapstring, int::value_type(item, i));}}}vectorpairstring, int vec;for (auto iterator mp.begin(); iterator ! mp.end(); iterator){vec.push_back(make_pair(iterator-first, iterator-second));}sort(vec.begin(), vec.end(), sortByF1);vectorstring rest;for (auto iterator vec.begin(); iterator ! vec.end(); iterator){rest.push_back((*iterator).first);}return rest;
}递归调用FP-Growth挖掘频繁项
//postPattern存储后缀比如从HeaderTable中的p节点开始挖掘频繁项时postPattern为p
void FPTree::FPGrowth(vectorvectorstring transRecords, vectorstring postPattern)
{vectorTreeNode* headerTable buildHeaderTable(transRecords); //构建headerTableTreeNode *treeRoot buildTree(transRecords, headerTable); //构建FP-tree//递归退出条件根节点没有孩子节点if (treeRoot-getChildNodeList().size() 0) {return;}
//输出频繁项集if (!postPattern.empty()){for (TreeNode *header : headerTable){cout header-getSupportCount() ends header-getName() ends;for (string str : postPattern){cout str ends;}cout endl;}}//遍历headerTablefor (TreeNode *header : headerTable){vectorstring newPostPattern;newPostPattern.push_back(header-getName());//存储原先的后缀if (!postPattern.empty()) {for (string str : postPattern){newPostPattern.push_back(str);}}
//newTransRecords存储前缀节点链vectorvectorstring newTransRecords;TreeNode *backNode header-getNextHomonym();//通过getNextHomonym遍历同名节点通过getParentNode获取前缀节点链while (backNode ! nullptr){int supportCount backNode-getSupportCount();vectorstring preNodes;TreeNode *parent backNode; while ((parent parent-getParentNode())-getName().length() ! 0){preNodes.push_back(parent-getName());} while (supportCount-- 0){newTransRecords.push_back(preNodes);}backNode backNode-getNextHomonym(); }FPGrowth(newTransRecords, newPostPattern); //递归构建条件FP-tree}
}5. 讨论在韩家炜教授提出FP-growth算法之前关联分析普遍采用Apriori及其变形算法。但是Apriori及其变形算法需要多次扫描数据库并需要生成指数级的候选项集性能并不理想。FP-growth算法提出利用了高效的数据结构FP-tree不再需要多次扫描数据库同时也不再需要生成大量的候选项。对于单路径的FP-tree其实不需要递归通过排列组合可以直接生成。韩家炜教授在其论文中提到了针对单路径的优化算法。论文中也提到了面对大数据时如何调整FP-growth算法使之适应数据量。6. 参考资料
[1] Mining Frequent Patterns without Candidate Generation. Jiawei Han, Jian Pei, and Yiwen Yin. Data Mining and Knowledge Discovery. Volume 8 Issue 1. January 2004. [PDF]
[2] Frequent Pattern 挖掘之二(FP Growth算法). yfx416. Software Engineer in NRC. 2011. [Link]
[3] FP-Tree算法的实现. Orisun. 华夏35度. 2011. [Link]
