歡迎來到Linux教程網
設為首頁 加入收藏
Linux教程網
Linux教程網
Linux教程網
您现在的位置： Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

關聯分析：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-tree

　　FP-growth算法通過構建FP-tree來壓縮事務數據庫中的信息，從而更加有效地產生頻繁項集。FP-tree其實是一棵前綴樹，按支持度降序排列，支持度越高的頻繁項離根節點越近，從而使得更多的頻繁項可以共享前綴。

圖2 事務型數據庫

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

　　FP-tree的根節點為null，不表示任何項。接下來，對事務型數據庫進行第二次掃描，從而開始構建FP-tree：

　　第一條記錄<f，c，a，m，p>對應於FP-tree中的第一條分支<(f:1)，(c:1)，(a:1)，(m:1)，(p:1)>：

圖3 第一條記錄

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

圖4 第二條記錄

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

圖5 第三條記錄

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

圖6 第四條記錄

　　類似地，將第五條記錄<f，c，a，m，p>作為FP-tree的一個分支，更新相關節點的支持度：

圖7 第五條記錄

 　　為了便於對整棵樹進行遍歷，建立一張項的頭表（an item header table）。這張表的第一列是按照降序排列的頻繁項。第二列是指向該頻繁項在FP-tree中節點位置的指針。FP-tree中每一個節點還有一個指針，用於指向相同名稱的節點：

圖8 FP-tree

　　綜上，FP-tree的節點可以定義為：

1 2 3 4 5 6 7 8 9 10 11 class TreeNode {   private:     String name; // 節點名稱     int count; // 支持度計數     TreeNode *parent; // 父節點     Vector<TreeNode *> 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)>。其中，第一條節點鏈表表示客戶購買的物品清單<f，c，a，m，p>在數據庫中共出現了兩次。需要注意到是，盡管<f，c，a>在第一條節點鏈中出現了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)>。同理，第二條節點鏈表示客戶購買的物品清單<c，b，p>在數據庫中只出現了一次。我們將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)|a，m>)，mine(<(f:3)|c，m>)，mine(null|f，m)。由於(m:3)滿足支持度阈值要求，所以以m結尾的頻繁項集有{(m:3)}。

圖11 節點(a，m)的條件FP-tree

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

　　

圖 12 節點(c，m)的條件FP-tree

　　從圖12可以看出，節點(c，m)的條件FP-tree只有1個節點，所以只需要遞歸調用mine(<null|f，c，m>)。因此，以(c，m)結尾的頻繁項集有{(cm:3)，(fcm:3)}。同理，以(f，m)結尾的頻繁項集有{(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;
    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);
};

構建HeaderTable：

//HeaderTable存儲事務數據庫的數據
vector<TreeNode*> FPTree::buildHeaderTable(vector<vector<string>> transRecords)
{
    vector<TreeNode*> F1; //存儲滿足支持度阈值的節點，並按照支持度降序排列，支持度相等的情況下按照字母順序排序，所以構建的FP-tree與論文有所不同，但是最終生成的頻繁項集是一樣的
    if (transRecords.size() > 0)
    {
        map<string, TreeNode*> mp;

        //calculate supportCount of every transRecords
        for (vector<string> record : transRecords)
        {
            for (string item : record)
            {
                //if item not in map, put item into map and set supportCount one
                if (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 F1
        for (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;
}

構建FP-tree：

TreeNode* FPTree::buildTree(vector<vector<string>> transRecords, vector<TreeNode*> F1)
{

    TreeNode *root = new TreeNode(); //根節點root
    for (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); //根據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, 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是頻繁項，則一定對應於F1中的序號，按照該序號對item進行排序，存儲到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;
}

遞歸調用FP-Growth挖掘頻繁項：

//postPattern存儲後綴，比如從HeaderTable中的p節點開始挖掘頻繁項時，postPattern為p
void FPTree::FPGrowth(vector<vector<string>> transRecords, vector<string> postPattern)
{
    vector<TreeNode*> headerTable = buildHeaderTable(transRecords); //構建headerTable
    TreeNode *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;
        }
    }

//遍歷headerTable
    for (TreeNode *header : headerTable)
    {
        vector<string> newPostPattern;
        newPostPattern.push_back(header->getName());

//存儲原先的後綴
        if (!postPattern.empty()) 
        {
            for (string str : postPattern)
            {
                newPostPattern.push_back(str);
            }
        }
//newTransRecords存儲前綴節點鏈
        vector<vector<string>> newTransRecords;
        TreeNode *backNode = header->getNextHomonym();

//通過getNextHomonym遍歷同名節點，通過getParentNode獲取前綴節點鏈
        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); //遞歸構建條件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]

Linux編程

選擇排序算法及其性能分析

各種排序算法的分析及Java實現

Mahout源碼分析：並行化FP-Growth算法

排序算法對比分析

紅黑樹的原理分析和算法設計

Hash算法沖突解決方法分析

Linux2.6定時器的時間輪算法分析

Hibernate關聯映射---多對一實例分析(單項關聯)

相關文章
  • Linux編程
  • SHELL編程
  • PERL編程
    • Copyright © Linux教程網 All Rights Reserved