轉(zhuǎn)載自??關(guān)聯(lián)分析：FP-Growth算法

關(guān)聯(lián)分析又稱關(guān)聯(lián)挖掘，就是在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性或因果結(jié)構(gòu)。關(guān)聯(lián)分析的一個(gè)典型例子是購(gòu)物籃分析。通過(guò)發(fā)現(xiàn)顧客放入購(gòu)物籃中不同商品之間的聯(lián)系，分析顧客的購(gòu)買習(xí)慣。比如，67%的顧客在購(gòu)買尿布的同時(shí)也會(huì)購(gòu)買啤酒。通過(guò)了解哪些商品頻繁地被顧客同時(shí)購(gòu)買，可以幫助零售商制定營(yíng)銷策略。關(guān)聯(lián)分析也可以應(yīng)用于其他領(lǐng)域，如生物信息學(xué)、醫(yī)療診斷、網(wǎng)頁(yè)挖掘和科學(xué)數(shù)據(jù)分析等。

?

1. 問(wèn)題定義

圖1 購(gòu)物籃數(shù)據(jù)的二元表示

　　圖1表示顧客的購(gòu)物籃數(shù)據(jù)，其中每一行是每位顧客的購(gòu)物記錄，對(duì)應(yīng)一個(gè)事務(wù)，而每一列對(duì)應(yīng)一個(gè)項(xiàng)。令I(lǐng)={i₁, i₂, ... , i_d}是購(gòu)物籃數(shù)據(jù)中所有項(xiàng)的集合，而T={t₁, t₂, ... , t_N}是所有事務(wù)的集合。每個(gè)事務(wù)t_i包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)分析中，包含0個(gè)或多個(gè)項(xiàng)的集合被稱為項(xiàng)集（itemset）。所謂的關(guān)聯(lián)規(guī)則是指形如X→Y的表達(dá)式，其中X和Y是不相交的項(xiàng)集。在關(guān)聯(lián)分析中，有兩個(gè)重要的概念——支持度（support）和置信度（confidence）。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。支持度（s）和置信度（c）這兩種度量的形式定義如下：

公式1

　　其中，N是事務(wù)的總數(shù)。關(guān)聯(lián)規(guī)則的支持度很低，說(shuō)明該規(guī)則只是偶然出現(xiàn)，沒(méi)有多大意義。另一方面，置信度可以度量通過(guò)關(guān)聯(lián)規(guī)則進(jìn)行推理的可靠性。因此，大多數(shù)關(guān)聯(lián)分析算法采用的策略是：

（1）頻繁項(xiàng)集產(chǎn)生：其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，這些項(xiàng)集稱作頻繁項(xiàng)集。

（2）規(guī)則的產(chǎn)生：其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強(qiáng)規(guī)則。

?

2. 構(gòu)建FP-tree

　　FP-growth算法通過(guò)構(gòu)建FP-tree來(lái)壓縮事務(wù)數(shù)據(jù)庫(kù)中的信息，從而更加有效地產(chǎn)生頻繁項(xiàng)集。FP-tree其實(shí)是一棵前綴樹(shù)，按支持度降序排列，支持度越高的頻繁項(xiàng)離根節(jié)點(diǎn)越近，從而使得更多的頻繁項(xiàng)可以共享前綴。

圖2 事務(wù)型數(shù)據(jù)庫(kù)

　　圖2表示用于購(gòu)物籃分析的事務(wù)型數(shù)據(jù)庫(kù)。其中，a，b，...，p分別表示客戶購(gòu)買的物品。首先，對(duì)該事務(wù)型數(shù)據(jù)庫(kù)進(jìn)行一次掃描，計(jì)算每一行記錄中各種物品的支持度，然后按照支持度降序排列，僅保留頻繁項(xiàng)集，剔除那些低于支持度閾值的項(xiàng)，這里支持度閾值取3，從而得到<(f:4)，(c:4)，(a:3)，(b:3)，(m:3，(p:3)>（由于支持度計(jì)算公式中的N是不變的，所以僅需要比較公式中的分子）。圖2中的第3列展示了排序后的結(jié)果。

　　FP-tree的根節(jié)點(diǎn)為null，不表示任何項(xiàng)。接下來(lái)，對(duì)事務(wù)型數(shù)據(jù)庫(kù)進(jìn)行第二次掃描，從而開(kāi)始構(gòu)建FP-tree：

　　第一條記錄<f，c，a，m，p>對(duì)應(yīng)于FP-tree中的第一條分支<(f:1)，(c:1)，(a:1)，(m:1)，(p:1)>：

圖3 第一條記錄

　　由于第二條記錄<f，c，a，b，m>與第一條記錄有相同的前綴<f，c，a>，因此<f，c，a>的支持度分別加一，同時(shí)在(a:2)節(jié)點(diǎn)下添加節(jié)點(diǎn)(b:1)，(m:1)。所以，FP-tree中的第二條分支是<(f:2)，(c:2)，(a:2)，(h:1)，(m:1)>：

圖4 第二條記錄

　　第三條記錄<f，b>與前兩條記錄相比，只有一個(gè)共同前綴<f>，因此，只需要在(f:3)下添加節(jié)點(diǎn)<b:1>：

圖5 第三條記錄

　　第四條記錄<c，b，p>與之前所有記錄都沒(méi)有共同前綴，因此在根節(jié)點(diǎn)下添加節(jié)點(diǎn)(c:1)，(b:1)，(p:1)：

圖6 第四條記錄

　　類似地，將第五條記錄<f，c，a，m，p>作為FP-tree的一個(gè)分支，更新相關(guān)節(jié)點(diǎn)的支持度：

圖7 第五條記錄

?　　為了便于對(duì)整棵樹(shù)進(jìn)行遍歷，建立一張項(xiàng)的頭表（an item header table）。這張表的第一列是按照降序排列的頻繁項(xiàng)。第二列是指向該頻繁項(xiàng)在FP-tree中節(jié)點(diǎn)位置的指針。FP-tree中每一個(gè)節(jié)點(diǎn)還有一個(gè)指針，用于指向相同名稱的節(jié)點(diǎn)：

圖8 FP-tree

　　綜上，FP-tree的節(jié)點(diǎn)可以定義為：

1234567891011

class?TreeNode {private:????String name;?// 節(jié)點(diǎn)名稱????int?count;?// 支持度計(jì)數(shù)????TreeNode *parent;?// 父節(jié)點(diǎn)????Vector<TreeNode *> children;?// 子節(jié)點(diǎn)????TreeNode *nextHomonym;?// 指向同名節(jié)點(diǎn)?????????...}

?

3. 從FP-tree中挖掘頻繁模式（Frequent Patterns）

　　我們從頭表的底部開(kāi)始挖掘FP-tree中的頻繁模式。在FP-tree中以p結(jié)尾的節(jié)點(diǎn)鏈共有兩條，分別是<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>和<(c:1)，(b:1)，(p:1)>。其中，第一條節(jié)點(diǎn)鏈表表示客戶購(gòu)買的物品清單<f，c，a，m，p>在數(shù)據(jù)庫(kù)中共出現(xiàn)了兩次。需要注意到是，盡管<f，c，a>在第一條節(jié)點(diǎn)鏈中出現(xiàn)了3次，單個(gè)物品<f>出現(xiàn)了4次，但是它們與p一起出現(xiàn)只有2次，所以在條件FP-tree中將<(f:4)，(c:3)，(a:3)，(m:2)，(p:2)>記為<(f:2)，(c:2)，(a:2)，(m:2)，(p:2)>。同理，第二條節(jié)點(diǎn)鏈表示客戶購(gòu)買的物品清單<c，b，p>在數(shù)據(jù)庫(kù)中只出現(xiàn)了一次。我們將p的前綴節(jié)點(diǎn)鏈<(f:2)，(c:2)，(a:2)，(m:2)>和<(c:1)，(b:1)>稱為p的條件模式基（conditional pattern base）。我們將p的條件模式基作為新的事務(wù)數(shù)據(jù)庫(kù)，每一行存儲(chǔ)p的一個(gè)前綴節(jié)點(diǎn)鏈，根據(jù)第二節(jié)中構(gòu)建FP-tree的過(guò)程，計(jì)算每一行記錄中各種物品的支持度，然后按照支持度降序排列，僅保留頻繁項(xiàng)集，剔除那些低于支持度閾值的項(xiàng)，建立一棵新的FP-tree，這棵樹(shù)被稱之為p的條件FP-tree：

圖9 p的條件FP-tree

　　從圖9可以看到p的條件FP-tree中滿足支持度閾值的只剩下一個(gè)節(jié)點(diǎn)(c:3)，所以以p結(jié)尾的頻繁項(xiàng)集有(p:3)，(cp:3)。由于c的條件模式基為空，所以不需要構(gòu)建c的條件FP-tree。

　　在FP-tree中以m結(jié)尾的節(jié)點(diǎn)鏈共有兩條，分別是<(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的條件模式基作為新的事務(wù)數(shù)據(jù)庫(kù)，每一行存儲(chǔ)m的一個(gè)前綴節(jié)點(diǎn)鏈，計(jì)算每一行記錄中各種物品的支持度，然后按照支持度降序排列，僅保留頻繁項(xiàng)集，剔除那些低于支持度閾值的項(xiàng)，建立m的條件FP-tree:

圖10 m的條件FP-tree

　　與p不同，m的條件FP-tree中有3個(gè)節(jié)點(diǎn)，所以需要多次遞歸地挖掘頻繁項(xiàng)集mine(<(f:3)，(c:3)，(a:3)|(m:3)>)。按照<(a:3)，(c:3)，(f:3)>的順序遞歸調(diào)用mine(<(f:3)，(c:3)|a，m>)，mine(<(f:3)|c，m>)，mine(null|f，m)。由于(m:3)滿足支持度閾值要求，所以以m結(jié)尾的頻繁項(xiàng)集有{(m:3)}。

圖11?節(jié)點(diǎn)(a，m)的條件FP-tree

　　從圖11可以看出，節(jié)點(diǎn)(a，m)的條件FP-tree有2個(gè)節(jié)點(diǎn)，需要進(jìn)一步遞歸調(diào)用mine(<(f:3)|c，a，m>)和mine(<null|f，a，m>)。進(jìn)一步遞歸mine(<(f:3)|c，a，m>)生成mine(<null|f，c，a，m>)。因此，以(a，m)結(jié)尾的頻繁項(xiàng)集有{(am:3)，(fam:3)，(cam:3)，(fcam:3)}。

　　

圖 12 節(jié)點(diǎn)(c，m)的條件FP-tree

　　從圖12可以看出，節(jié)點(diǎn)(c，m)的條件FP-tree只有1個(gè)節(jié)點(diǎn)，所以只需要遞歸調(diào)用mine(<null|f，c，m>)。因此，以(c，m)結(jié)尾的頻繁項(xiàng)集有{(cm:3)，(fcm:3)}。同理，以(f，m)結(jié)尾的頻繁項(xiàng)集有{(fm:3)}。

　　在FP-tree中以b結(jié)尾的節(jié)點(diǎn)鏈共有三條，分別是<(f:4)，(c:3)，(a:3)，(b:1)>，<(f:4)，(b:1)>和<(c:1)，(b:1)>。由于節(jié)點(diǎn)b的條件模式基<(f:1)，(c:1)，(a:1)>，<(f:1)>和<(c:1)>都不滿足支持度閾值，所以不需要再遞歸。因此，以b結(jié)尾的頻繁項(xiàng)集只有(b:3)。

　　同理可得，以a結(jié)尾的頻繁項(xiàng)集{(fa:3)，(ca:3)，(fca:3)，(a:3)}，以c結(jié)尾的頻繁項(xiàng)集{(fc:3)，(c:4)}，以f結(jié)尾的頻繁項(xiàng)集{(f:4)}。

?

4. 算法實(shí)現(xiàn)

聲明FP-tree節(jié)點(diǎn)：

class TreeNode {//Constructors-Destructors public:TreeNode();TreeNode(string);~TreeNode();//Member variables private:string nodeName;int supportCount;TreeNode *parentNode;vector<TreeNode *> childNodeList;TreeNode *nextHomonymNode;//Member functions public:string getName();void setName(string);int getSupportCount() const;void setSupportCount(int);TreeNode* getParentNode() const;void setParentNode(TreeNode*);vector<TreeNode*> getChildNodeList() const;void addChild(TreeNode*);TreeNode* findChildNode(string) const;void setChildren(vector<TreeNode*>);void printChildrenNames() const;TreeNode* getNextHomonym() const;void setNextHomonym(TreeNode *nextHomonym);void countIncrement(int); };

構(gòu)建HeaderTable：

//HeaderTable存儲(chǔ)事務(wù)數(shù)據(jù)庫(kù)的數(shù)據(jù) vector<TreeNode*> FPTree::buildHeaderTable(vector<vector<string>> transRecords) {vector<TreeNode*> F1; //存儲(chǔ)滿足支持度閾值的節(jié)點(diǎn)，并按照支持度降序排列，支持度相等的情況下按照字母順序排序，所以構(gòu)建的FP-tree與論文有所不同，但是最終生成的頻繁項(xiàng)集是一樣的if (transRecords.size() > 0){map<string, TreeNode*> mp;//calculate supportCount of every transRecordsfor (vector<string> 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(map<string, 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 supportCount sort(F1.begin(), F1.end(), sortBySupportCount);}return F1; }

構(gòu)建FP-tree：

TreeNode* FPTree::buildTree(vector<vector<string>> transRecords, vector<TreeNode*> F1) {TreeNode *root = new TreeNode(); //根節(jié)點(diǎn)rootfor (vector<string> transRecord : transRecords){//拷貝transRecord到record vector<string> record;for (auto iter = transRecord.begin(); iter != transRecord.end(); iter++){record.push_back(*iter);}record = sortedByF1(record, F1); //根據(jù)F1中存儲(chǔ)的頻繁項(xiàng)集，將record按照支持度降序排列，并且僅保留頻繁項(xiàng)集，剔除那些低于支持度閾值的項(xiàng)

//順序比較record中的節(jié)點(diǎn)和FP-tree中的節(jié)點(diǎn)，如果record中的節(jié)點(diǎn)已經(jīng)存在于FP-tree中，將該節(jié)點(diǎn)的支持度加一，繼續(xù)比較下一個(gè)節(jié)點(diǎn)，否則調(diào)用addNodes來(lái)添加剩余節(jié)點(diǎn)到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; }

添加節(jié)點(diǎn)：

void FPTree::addNodes(TreeNode *ancestor, vector<string> *record, vector<TreeNode*> 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：

vector<string> FPTree::sortedByF1(vector<string> transRecord, vector<TreeNode*> F1) {//如果item是頻繁項(xiàng)，則一定對(duì)應(yīng)于F1中的序號(hào)，按照該序號(hào)對(duì)item進(jìn)行排序，存儲(chǔ)到rest中map<string, int> mp;for (string item : transRecord){for (int i = 0; i < F1.size(); i++){TreeNode *tNode = F1[i];if (tNode->getName() == item){mp.insert(map<string, int>::value_type(item, i));}}}vector<pair<string, 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);vector<string> rest;for (auto iterator = vec.begin(); iterator != vec.end(); iterator++){rest.push_back((*iterator).first);}return rest; }

遞歸調(diào)用FP-Growth挖掘頻繁項(xiàng)：

//postPattern存儲(chǔ)后綴，比如從HeaderTable中的p節(jié)點(diǎn)開(kāi)始挖掘頻繁項(xiàng)時(shí)，postPattern為p void FPTree::FPGrowth(vector<vector<string>> transRecords, vector<string> postPattern) {vector<TreeNode*> headerTable = buildHeaderTable(transRecords); //構(gòu)建headerTableTreeNode *treeRoot = buildTree(transRecords, headerTable); //構(gòu)建FP-tree//遞歸退出條件：根節(jié)點(diǎn)沒(méi)有孩子節(jié)點(diǎn)if (treeRoot->getChildNodeList().size() == 0) {return;} //輸出頻繁項(xiàng)集if (!postPattern.empty()){for (TreeNode *header : headerTable){cout << header->getSupportCount() << ends << header->getName() << ends;for (string str : postPattern){cout << str << ends;}cout << endl;}}//遍歷headerTable for (TreeNode *header : headerTable){vector<string> newPostPattern;newPostPattern.push_back(header->getName());//存儲(chǔ)原先的后綴 if (!postPattern.empty()) {for (string str : postPattern){newPostPattern.push_back(str);}} //newTransRecords存儲(chǔ)前綴節(jié)點(diǎn)鏈 vector<vector<string>> newTransRecords;TreeNode *backNode = header->getNextHomonym();//通過(guò)getNextHomonym遍歷同名節(jié)點(diǎn)，通過(guò)getParentNode獲取前綴節(jié)點(diǎn)鏈 while (backNode != nullptr){int supportCount = backNode->getSupportCount();vector<string> 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); //遞歸構(gòu)建條件FP-tree } }

?

5. 討論

　　在韓家煒教授提出FP-growth算法之前，關(guān)聯(lián)分析普遍采用Apriori及其變形算法。但是，Apriori及其變形算法需要多次掃描數(shù)據(jù)庫(kù)，并需要生成指數(shù)級(jí)的候選項(xiàng)集，性能并不理想。FP-growth算法提出利用了高效的數(shù)據(jù)結(jié)構(gòu)FP-tree，不再需要多次掃描數(shù)據(jù)庫(kù)，同時(shí)也不再需要生成大量的候選項(xiàng)。

　　對(duì)于單路徑的FP-tree其實(shí)不需要遞歸，通過(guò)排列組合可以直接生成。韓家煒教授在其論文中提到了針對(duì)單路徑的優(yōu)化算法。論文中也提到了面對(duì)大數(shù)據(jù)時(shí)，如何調(diào)整FP-growth算法使之適應(yīng)數(shù)據(jù)量。

?

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算法的實(shí)現(xiàn). Orisun. 華夏35度. 2011. [Link]

總結(jié)

以上是生活随笔為你收集整理的关联分析：FP-Growth算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。