精华内容
下载资源
问答
  • 提出了基于频繁项集的最大频繁项集(BFI-DMFI)和频繁闭项集挖掘算法(BFI-DCFI)。BFI-DMFI算法通过逐个检测频繁项集在其集合中是否存在超集确定该项集是不是最大频繁项集;BFI-DCFI算法则是通过挖掘所有支持度相等...
  • 频繁项集,频繁闭项集,最大频繁项集

    万次阅读 多人点赞 2018-09-14 18:52:53
    Frequent Itemset(频繁项集) 称I={i1,i2,...,im}为项(Item)的集合,D={T1,T2,...,Tn},i∈[1,n]为事务数据集(Transaction Data Itemsets),事务Ti由I中若干项组成。 设S为由项组成的一个集合...

    转自:https://blog.csdn.net/u013007900/article/details/54743395

    Frequent Itemset(频繁项集)

    称I={i1,i2,...,im}为项(Item)的集合,D={T1,T2,...,Tn},i∈[1,n]为事务数据集(Transaction Data Itemsets),事务Ti由I中若干项组成。

    设S为由项组成的一个集合,S={i|i∈I},简称项集(Itemset)。包含k个项的项集称为k-项集

    t为一条事务, 如果S⊆t, 则称事务t包含S。

    S的支持度:sup(S)=(包含S的事务数量D中总的事务数量)×100%sup(S)

    若S的支持度≥给定最小支持度,称S为频繁项集(Frequent Itemset)

    例如,有交易数据库

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    TID为事务编号,item为事务数据集的内容。

    现在有项集S1={b,c},它出现在TID为1,2,3的事务中,也就是S1⊆{a,b,c,S1⊆{a,b,c,d},S1⊆{b,c,e}。

    所以S1的支持度计数为3,支持度为3/5。

    如果支持度阈值小于60%,那么S1就是一个频繁项集。

    Superset(超集)

    若一个集合S2中的每一个元素都在集合S1中,且集合S1中可能包含S2中没有的元素,则集合S1就是S2的一个超集。S1是S2的超集,则S2是S1的真子集,反之亦然。

    接着上面的例子,

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    现在有项集S1={b,c},那么它就是{b},{c}的超集。S1也是{a,b,c}$等的真子集。

    Max Pattern/Maximal Frequent Itemset(最大频繁项集)

    如果频繁项集L的所有超集都是非频繁项集,那么称L为最大频繁项集称最大频繁模式,记为MFI (Maximal Frequent Itemset)。

    频繁项集是最大频繁项集的子集。最大频繁项集中包含了频繁项集的频繁信息,且通常项集的规模要小几个数量级。所以在数据集中含有较长的频繁模式时挖掘最大频繁项集是非常有效的手段。

    综上,最大频繁项集是各频繁k项集中符合无超集条件的频繁项集。

    接着上面的例子,

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    现在有项集S1={b,c},且有支持度阈值=60%

    那么S1就是一个频繁项集,那么我们来看看它的超集。

    Supersetcount
    abc2
    bcd1
    bce1
    abcd1
    abce0
    bcde0
    abcde0

    由此可见,它们的支持度都小于60%60%,所以它们都不是频繁项集。

    所以S1的所有超集都不是频繁项集,则它是最大频繁项集。

    close pattern(闭合频繁项集)

    所谓闭项集,就是指一个项集X,它的直接超集的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的,也就是它的支持度大于等于最小支持度阈值,那它就称为闭频繁项集。

    接着上面的例子,

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    因为项集{b,c}出现在TID为1,2,3的事务中,所以{b,c}的支持度计数为3。而{b,c}的直接超集:{a,b,c},{a,b,c,d}的支持度计数分别为2,1,都不等于{b,c}的支持度计数3,所以{b,c}为闭项集,如果支持度阈值为40%,则{b,c}也为闭频繁项集。

    项集{a,b}出现在TID为1,2的事务中,其支持度计数为2。而它的直接超集{a,b,c}支持度计数也为2,所以{a,b}不是闭项集

    展开全文
  • 频繁项集挖掘 最大频繁项集挖掘 fp-growth fpmax 自己实现的源码还有测试用例
  • 频繁项集&频繁闭项集&最大频繁集

    万次阅读 多人点赞 2016-06-24 23:37:36
    频繁项集&频繁闭项集&最大频繁集

    之前在百度知道回答过这个问题,在这里做一下备份。

    所谓频繁项集,就是事例里频繁出现的项的集合,比如事例为每个人的购物清单,项就是买的东西,项集就是指频繁地同时出现的集合。比如人们总是喜欢同时买酒和花生,那么酒和花生这两个项就是一个频繁二项集。

    频繁项集里存在着较多的冗余,因此人们又引入了频繁闭项集最大频繁集的概念。

    频繁闭项集:设I为项的集合,T为事例的集合,则定义如下映射:1)对于X属于I(项集),f(x)是T之中包含X的事例集;2)对于Y属于T(事例集),g(Y)是所有Y都包含的项集。可以看到,对于一般的X,g(f(X))可能会大于X,而频繁闭项集满足就是g(f(X))=X的项集X。

    举例来说,比如人们总是一起买“花生-啤酒-饼干”三种东西(顺便举个例子),而不会只买其中的两种,那么如果找频繁项集,那么这三种的任意两个的组合以及三者组合都是频繁项集,比如“啤酒-饼干”;但是只有“花生-啤酒-饼干”三者的组合才是频繁闭项集。也就是说,不会存在其它的项总是和频繁闭项集一起出现,否则g(f(X))就会包含那些其它项了。

    最大频繁集:如果X是一个频繁项集,而且X的任意一个超集都是非频繁的,则称X是最大频繁项集。
    这个应该说是比较明确的,就是这个集合已经不能再扩充了,否则就不是频繁集了。

    再举个总的例子
    假如现在频繁阈值是3。 有10个事例里都有“花生-啤酒”,而且这10个事例没有其它共同项,那么“花生-啤酒”就是一个频繁闭项集,因为它首先是闭项集(没有总是跟它们同时出现的其它项),然后也满足频繁阈值。在10个事例里其中有5个同时也有“饼干”,因此“花生-啤酒-饼干”也是频繁集,因为“花生-啤酒-饼干”是“花生-啤酒”的超集,所以“花生-啤酒”不是最大频繁集。至于“花生-啤酒-饼干”是不是最大频繁集,那要看有没有它的超集满足频繁阈值,没有的话它就是最大频繁集。

    模式的数目:最大频繁集<频繁闭项集<频繁项集,不过最大频繁集丢失了很多信息,比如可能在买“花生-啤酒-饼干”的人群中,还有一部分是买洗发水的,数目也达到了频繁项阈值,那么“花生-啤酒-饼干-洗发水”就是“花生-啤酒-饼干”的一个超集,所以“花生-啤酒-饼干”这个集合的独特性就不会在频繁最大集里体现;而频繁闭项集实际上还保留着频繁项集的信息,可以继续拆分为原来的频繁项集。

    展开全文
  • C++实现Apriori算法,频繁模式数据挖掘,最大频繁项集,闭频繁项集,里面包括测试数据以及apriori.cpp、 apriori.h 、apriori_test.cpp三个文件。具体的相见博客:...
  • 频繁项集合并

    2018-01-09 08:57:32
    频繁项集合并与处理,按照最小化距离目标实现,可设定目标集合大小
  • Frequent Itemset(频繁项集)称I={i1,i2,...,im}I=\{i_1, i_2, ..., i_m\}为项(Item)的集合,D={T1,T2,...,Tn}D=\{T_1, T_2, ...,T_n\},i∈[1,n]i∈[1,n]为事务数据集(Transaction Data Itemsets),事务TiT_i由II中...

    Frequent Itemset(频繁项集)

    I = { i 1 , i 2 , . . . , i m } I=\{i_1, i_2, ..., i_m\} I={i1,i2,...,im}项(Item)的集合 D = { T 1 , T 2 , . . . , T n } D=\{T_1, T_2, ...,T_n\} D={T1,T2,...,Tn} i ∈ [ 1 , n ] i∈[1,n] i[1,n]事务数据集(Transaction Data Itemsets),事务 T i T_i Ti I I I中若干项组成。

    S S S为由项组成的一个集合, S = { i ∣ i ∈ I } S=\{i|i∈I\} S={iiI},简称项集(Itemset)。包含k个项的项集称为k-项集

    t t t为一条事务, 如果 S ⊆ t S\subseteq t St, 则称事务 t t t包含 S S S

    S S S的支持度 s u p ( S ) = ( 包 含 S 的 事 务 数 量 D 中 总 的 事 务 数 量 ) × 100 % sup(S) = ({包含S的事务数量\over D中总的事务数量})\times 100\% sup(S)=(DS)×100%

    S S S的支持度≥给定最小支持度,称 S S S频繁项集(Frequent Itemset)

    例如,有交易数据库

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    TID为事务编号,item为事务数据集的内容。

    现在有项集 S 1 = { b , c } S_1 = \{b,c\} S1={b,c},它出现在TID为1,2,3的事务中,也就是 S 1 ⊆ { a , b , c } S_1\subseteq \{a,b,c\} S1{a,b,c} S 1 ⊆ { a , b , c , d } S_1\subseteq \{a,b,c,d\} S1{a,b,c,d} S 1 ⊆ { b , c , e } S_1\subseteq \{b,c,e\} S1{b,c,e}

    所以 S 1 S_1 S1的支持度计数为3,支持度为 3 5 3\over 5 53

    如果支持度阈值小于 60 % 60\% 60%,那么 S 1 S_1 S1就是一个频繁项集。

    Superset(超集)

    若一个集合 S 2 S_2 S2中的每一个元素都在集合 S 1 S_1 S1中,且集合 S 1 S_1 S1中可能包含 S 2 S_2 S2中没有的元素,则集合 S 1 S_1 S1就是 S 2 S_2 S2的一个超集。 S 1 S_1 S1 S 2 S_2 S2的超集,则 S 2 S_2 S2 S 1 S_1 S1的真子集,反之亦然。

    接着上面的例子,

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    现在有项集 S 1 = { b , c } S_1 = \{b,c\} S1={b,c},那么它就是 { b } \{b\} {b} { c } \{c\} {c}的超集。 S 1 S_1 S1也是 { a , b , c } \{a,b,c\} {a,b,c}等的真子集。

    Max Pattern/Maximal Frequent Itemset(最大频繁项集)

    如果频繁项集L的所有超集都是非频繁项集,那么称L为最大频繁项集称最大频繁模式,记为MFI (Maximal Frequent Itemset)。

    频繁项集是最大频繁项集的子集。最大频繁项集中包含了频繁项集的频繁信息,且通常项集的规模要小几个数量级。所以在数据集中含有较长的频繁模式时挖掘最大频繁项集是非常有效的手段。

    综上,最大频繁项集是各频繁k项集中符合无超集条件的频繁项集。

    接着上面的例子,

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    现在有项集 S 1 = { b , c } S_1 = \{b,c\} S1={b,c},且有支持度阈值 = 60 % =60\% 60%

    那么 S 1 S_1 S1就是一个频繁项集,那么我们来看看它的超集。

    Supersetcount
    abc2
    bcd1
    bce1
    abcd1
    abce0
    bcde0
    abcde0

    由此可见,它们的支持度都小于 60 % 60\% 60%,所以它们都不是频繁项集。

    所以 S 1 S_1 S1的所有超集都不是频繁项集,则它是最大频繁项集。

    close pattern(闭合频繁项集)

    所谓闭项集,就是指一个项集X,它的**直接超集(最小的严格超集)**的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的,也就是它的支持度大于等于最小支持度阈值,那它就称为闭频繁项集。

    接着上面的例子,

    TIDitem
    1abc
    2abcd
    3bce
    4acde
    5de

    因为项集{b,c}出现在TID为1,2,3的事务中,所以{b,c}的支持度计数为3。而{b,c}的直接超集:{a,b,c}的支持度计数为2,都不等于{b,c}的支持度计数3,所以{b,c}为闭项集,如果支持度阈值为40%,则{b,c}也为闭频繁项集。

    项集{a,b}出现在TID为1,2的事务中,其支持度计数为2。而它的直接超集{a,b,c}支持度计数也为2,所以{a,b}不是闭项集。

    展开全文
  • java频繁项集代码

    2019-03-02 15:26:09
    java频繁项集代码 Apriori算法的核心步骤是: L(K-1)通过自连接求出项数为K的候选项集合C(K) 通过对C(K)进行一系列处理(剪枝 + 支持度判断) 得到L(K)集合
  • 关联规则的研究是数据挖掘中的重要问题,如何高效地发现频繁项集是关联规则研究中的关键问题。根据数据库事务的统计性规律,在最大频繁项集发现算法Apriori及其变种算法的基础上,提出一种新的基于层次的最大频繁项...
  • 1993年AGRAWAL R等人提出了一个重要的反映...最大频繁项集中已经隐含了所有的频繁项集,并且在许多数据挖掘应用中也只需要挖掘最大频繁项集,而不是获取所有的频繁项集,因此对最大频繁项集的挖掘具有重大的现实意义。
  • 随着分布式数据库记录的不断增加,需要对已挖掘出的全局最大频繁项集进行增量更新。在已经提出的快速挖掘全局最大频繁项集算法(FMMFI)的基础上,提出了分布式数据库全局最大频繁项集增量更新算法(IUGMFI)。IUGMFI算法...
  • 频繁项集挖掘VTK算法

    2020-02-08 16:53:16
    频繁项集挖掘算法,大数据,数据挖掘,利用垂直数据结构挖掘top rank k 频繁项集,解决传统频繁项集算法选取阈值的困难
  • 分析了Apriori算法关于发现频繁项集的方法及其效率,提出了一种基于上三角项集矩阵的频繁项集挖掘优化算法。本算法只需要扫描数据库一次,不产生候选项目集,也不使用逐层迭代的方法,大大提高了频繁项集的发现效率...
  • Apriori算法挖掘频繁项集
  • 提出一种快速挖掘分布式数据库全局最大频繁项集算法(FMMFI). FMMFI 算法首先设置了中心节点, 并以 各个节点构建局部FP-tree, 采用挖掘最大频繁项目集算法(DMFIA) 快速挖掘局部最大频繁项集; 然后与中心节点交...
  • 针对目前时态关联规则研究中存在的挖掘效率不高、规则可解释性低、未考虑项集时间关联关系等问题,在原有相关研究的基础上,提出一种新的基于频繁项集树的时态关联规则挖掘算法.通过对时间序列数据进行降维离散化处理,...
  • 挖掘加权频繁项集是多种数据挖掘应用中的关键问题,为提高传统加权频繁项集挖掘算法的性能,在研究概念格模型和差集Diffsets理论的基础上,构建一种利用差集的加权频繁项集格结构,该格结构通过差集性质快速计算加权支持...
  • 针对基于WN-list 加权频繁项集挖掘算法(NFWI)中挖掘加权频繁项集(FWI)效率低的问题,提出了一种基于WNegNodeset结构的加权频繁项集挖掘算法(NegNFWI)。该算法首先采用了新的数据结构WNegNodeset,它是...
  • 在机器学习的数据挖掘研究领域,需要频繁项集搜索作为关联挖掘的一部分。 此代码为您提供了频繁的 k 项集作为输出。 您可能希望根据需要更改 MAIN 文件中的两件事: 第一个是 'A':输入矩阵,每一行作为一个 ...
  • 关联规则挖掘算法——Apriori算法,主要过程是对频繁项集的挖掘,而在对频繁项集的挖掘中首先要生成候选频繁项集,然后再从候选集中确定出满足最小支持度计数的频繁项集,这会耗费大量的CPU开销。使用垂直数据格式挖掘...
  • 提出一个数据流环境下的基于概念格和滑动窗口的频繁项集挖掘算法DSFMCL。算法在滑动窗口内分批挖掘新流入的基本窗口频繁概念后,生成概念格的Hasse图。引入最小支持度ζ和误差因子ε对非频繁概念节点进行剪枝操作。...
  • 只能说用这个Apriori算法来练练容器的操作以及文件流的操作。这两个变得熟练了。...AA BB CC频繁项集: 最大频繁项集频繁项集 无闭频繁项集 第二组测试数据第二组 AA BB CC AA BB CC DD BB CC EE A

      只能说用这个Apriori算法来练练容器的操作以及文件流的操作。这两个变得熟练了。

    两个小测试数据集

    第一组

    测试数据第一组:
    
    AA BB  EE
    BB DD
    BB CC
    AA BB DD
    AA CC
    BB CC
    AA CC
    AA BB CC EE
    AA BB CC
    频繁项集:
    

    这里写图片描述

    最大频繁项集  
    

    这里写图片描述

    闭频繁项集
    

    无闭频繁项集

    第二组

    测试数据第二组
    
    AA BB CC
    AA BB CC DD
    BB CC EE
    AA CC DD EE
    DD EE
    频繁项集
    

    这里写图片描述

    最大频繁项集
    

    这里写图片描述

    闭频繁项集
    

    这里写图片描述

    算法实现

    apriori.h
    
    #ifndef __APRIORI_H_
    #define __APRIORI_H_
    
    
    #include <iostream>
    #include <cstdlib>
    #include <map>
    #include <set>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <sstream>
    #include <utility>
    
    using namespace std;
    
    class Apriori{
    
    public:
        Apriori(string dataFileName,float minSup){
            this->dataFileName = dataFileName;
            this->minSup = minSup;
        }
    
    /*Functions*/
    public:
        void printMapSet(map< set<string> ,int> &mapSet);
        void printsetSet(set< set<string> > &);
        void printSet(set<string> &);
    
        int buildData();
        map< set<string>, int> getTextDatabaseFre();
        map< set<string>, int> getTextDatabaseSurpport();
        map<string, int> getCandidate1ItemSet();
        map< set<string>, int > findFrequent1Itemsets();
        set< set<string> > aprioriGen(int m, set< set<string> > &);
        bool has_infrequent_subset(set<string> &, set< set<string> > &);
        map< set<string>, int > getFreqKItemSet(int k, set< set<string> > freqMItemSet);    
        set< set<string> > keySet(map< set<string>, int > &mapSet);
        set<string> retainAll(set<string> set1, set<string> set2);
    /*Functions*/
    private:    
        void removeAll(set<string> &set1, set<string> &set2);
        set<string> addAll(set<string> &set1, set<string> &set2);
    
    /*Variables*/   
    private:    
        string dataFileName;
        map<long, set<string> > textDatabase;   //事务数据库
        float minSup;                           //最小支持度,(使用绝对支持度)
        long textDatabaseCount;                 //事务数据库中的事务数
        map< set< set<string> >, int > freqItemSet;             //候选项集集合
        map< set< set<string> >, int > candidateItemSet;        //频繁项集集合
    };
    
    #endif
    apriori.cpp
    
    #include "apriori.h"
    
    void Apriori::printMapSet(map< set<string> ,int> &mapSet)
    {
        map< set<string>, int >::iterator it = mapSet.begin();
        while(it != mapSet.end()){
            set<string>::iterator itSet = it->first.begin();
            cout << "#" << it->second << "\t";
            cout << "[" ;
            while(itSet != it->first.end()){
                cout << *itSet << "," ;
                ++itSet;
            }
            cout << "]" << endl;
            ++it;
        }
    }
    void Apriori::printsetSet(set< set<string> > &setSet)
    {
        set< set<string> >::iterator c2It = setSet.begin();
        while(c2It != setSet.end()){
           set<string>::iterator ckSetIt = (*c2It).begin();
           cout << "[";
            while(ckSetIt != (*c2It).end()){
                cout << *ckSetIt << "," ;
                ++ckSetIt;
            }
            cout << "]"<< endl;
            ++c2It;            
        }
    }
    void Apriori::printSet(set<string> &setS)
    {
        set<string>::iterator setIt = setS.begin();
        cout << "[";
        while(setIt != setS.end()){
            cout <<*setIt << "," ;
            ++setIt;
        }
        cout << "]" << endl;
    }
    
    //---------------------------------------------------------
    //将文本数据存入到Map中,产生事务数据库D,即textDataBase
    //---------------------------------------------------------
    int Apriori::buildData()
    {
        /*打开文本文件*/
        ifstream inFile;
        inFile.open(dataFileName.c_str());
        if(!inFile){
            cerr << "open " <<dataFileName << "is failed!" << endl;
            return EXIT_FAILURE;
        }
        /*读取文本行*/
        string textline;
        vector<string> lines_of_text;
    
        while(getline(inFile,textline))
            lines_of_text.push_back(textline);
        /*产生事务数据库*/
        int line_num ;
        for(line_num = 0; line_num != lines_of_text.size(); ++line_num){    
            istringstream line(lines_of_text[line_num]);
            string word;    
            while(line >> word){            
                textDatabase[line_num].insert(word);
            }
        }       
        textDatabaseCount = textDatabase.size();
        cout << "textDatabaseCount: " << textDatabaseCount << " " << line_num<< endl;
        return EXIT_SUCCESS;
    }
    
    //得到事物项集D中每项的重复度,即每项在事物项集中出现的频率
    map< set<string>, int> Apriori::getTextDatabaseFre()
    {
        map< set<string>, int> textDatabaseFre;
        map<long ,set<string> >::iterator textDataIt = textDatabase.begin();  
        while(textDataIt != textDatabase.end()){
            pair<map< set<string>, int>::iterator, bool> ret = 
                textDatabaseFre.insert(make_pair(textDataIt->second,1));
            if(!ret.second)
                ++ret.first->second;        
            ++textDataIt;
        }
        return textDatabaseFre;
    }
    
    //得到事物项集D中每项的支持度,即统计数据集每一项作为子集出现的频率
    //注:set<string>中的string是按从小到大的顺序排列的
    //map< set<string>, int >
    map< set<string>, int> Apriori::getTextDatabaseSurpport()
    {
        map< set<string>, int> textDatabaseSurpport;
        map< set<string>, int> textDatabaseFre = getTextDatabaseFre();
        //cout << "原始数据集D各项的频度" << endl;
        //apriori.printMapSet(textDatabaseFre);
        map<long ,set<string> >::iterator textDataIt1 = textDatabase.begin();
        while(textDataIt1 != textDatabase.end()){        
            textDatabaseSurpport.insert(make_pair(textDataIt1->second,0));
            map<long ,set<string> >::iterator textDataIt2 = textDatabase.begin();
            while(textDataIt2 != textDatabase.end()){
                if(retainAll(textDataIt1->second, textDataIt2->second) == textDataIt1->second)
                    ++textDatabaseSurpport[textDataIt1->second];
                ++textDataIt2;
            }                  
            ++textDataIt1;
        } 
        map< set<string>, int>::iterator textDatabaseFreIt = textDatabaseFre.begin();
    
        while(textDatabaseFreIt != textDatabaseFre.end()){
            textDatabaseSurpport[textDatabaseFreIt->first] = 
                textDatabaseSurpport[textDatabaseFreIt->first]/textDatabaseFreIt->second;
            ++textDatabaseFreIt;
        }
    
        return textDatabaseSurpport;
    }
    
    
    //-------------------------------------------------------------------------
    //获取候选1项集
    //-------------------------------------------------------------------------
    map<string, int> Apriori::getCandidate1ItemSet()
    {
        map<string, int> candidate1ItemSetTemp;
        map<long, set<string> >::iterator mapIter = textDatabase.begin();
        set<string>::iterator setIter = mapIter->second.begin();
    
        while(mapIter != textDatabase.end()){
            while(setIter != mapIter->second.end()){
                pair<map<string, int>::iterator, bool> ret = 
                    candidate1ItemSetTemp.insert(make_pair(*setIter,1));
                if(!ret.second)
                    ++ret.first->second;
                ++setIter;
            }
            ++mapIter;
            setIter = mapIter->second.begin();
        }
        return candidate1ItemSetTemp;
    }
    
    //-------------------------------------------------------------------------
    //获取频繁1项集
    //-------------------------------------------------------------------------
    map< set<string>, int > Apriori::findFrequent1Itemsets()
    {
        set<string> freq1Key;
        map< set<string>, int > freq1ItemSetMap;
        map<string, int> candidate1ItemSet = getCandidate1ItemSet();
        map<string, int>::iterator candIt = candidate1ItemSet.begin();
        while(candIt != candidate1ItemSet.end()){
            if(candIt->second >= minSup){
                freq1Key.erase(freq1Key.begin(),freq1Key.end());
                freq1Key.insert(candIt->first);
                freq1ItemSetMap[freq1Key] = candIt->second;
            }
            ++candIt;
        }
        return freq1ItemSetMap;
    }
    
    //-------------------------------------------------------------------------
    //根据频繁k-1项集键集获取频繁k项集
    //k>1
    //-------------------------------------------------------------------------
    map< set<string>, int > Apriori::getFreqKItemSet(int k, set< set<string> > freqMItemSet)
    {
        map< set<string>, int > freqKItemSetMap;
        map< set<string>, int> candFreqKItemSetMap;    
        set< set<string> > candFreqKItemSet = aprioriGen(k-1, freqMItemSet);
    
        //效率是根据min_sup的值的大小决定的,大,效率高,小效率高
        map<long, set<string> >::iterator mapIter = textDatabase.begin();
        //下面的while循环效率很低
        while(mapIter != textDatabase.end()){
            set<string> itValue = mapIter->second;
            set< set<string> >::iterator kit = candFreqKItemSet.begin();
            while(kit != candFreqKItemSet.end()){
                set<string> kSet = *kit;
                set<string> setTemp(kSet.begin(),kSet.end());
                removeAll(setTemp,itValue);            
                if(setTemp.size() == 0){                
                    pair< map< set<string>, int >::iterator ,bool > ret = 
                                candFreqKItemSetMap.insert(make_pair(kSet,1));
                    if(!ret.second)
                        ++ret.first->second;                    
                }
                ++kit;
            }
            ++mapIter;
        }
    
        map< set<string>, int>::iterator candIt = candFreqKItemSetMap.begin();
    
        while(candIt != candFreqKItemSetMap.end()){
            if(candIt->second >= minSup){            
                freqKItemSetMap[candIt->first] = candIt->second;
            }
            ++candIt;
        }
    
        return freqKItemSetMap;    
    }
    
    //-------------------------------------------------------------------------
    //取交集
    //-------------------------------------------------------------------------
    set<string> Apriori::retainAll(set<string> set1, set<string> set2)
    {
    
        set<string>::iterator set1It = set1.begin();    
        set<string> retSet;
    
        while(set1It != set1.end()){
            set<string>::iterator set2It = set2.begin();
            while(set2It != set2.end()){
                if((*set1It) == (*set2It)){
                    retSet.insert(*set1It);
                    break;
                }
                ++set2It;
            }        
            ++set1It;
        }
    
        return retSet;
    }
    
    //-------------------------------------------------------------------------
    //返回set1中去除了set2的数据集
    //-------------------------------------------------------------------------
    void Apriori::removeAll(set<string> &set1, set<string> &set2)
    {
        set<string>::iterator set2It = set2.begin(); 
        while(set2It != set2.end()){
            set1.erase(*set2It);
            ++set2It;
            if(set1.size() == 0)break;
        }    
    }
    
    //-------------------------------------------------------------------------
    //取并集
    //-------------------------------------------------------------------------
    set<string> Apriori::addAll(set<string> &set1, set<string> &set2)
    {
        set<string>::iterator set1It = set1.begin();  
        set<string>::iterator set2It = set2.begin();  
        set<string> retSet(set1.begin(),set1.end());
    
        while(set2It != set2.end()){
            retSet.insert(*set2It);
            ++set2It;
        }
        return retSet;  
    }
    
    //-------------------------------------------------------------------------
    //根据频繁(k-1)项集获取候选k项集
    //m = k-1
    //freqMItemSet:频繁k-1项集
    //-------------------------------------------------------------------------
    set< set<string> > Apriori::aprioriGen(int m, set< set<string> > &freqMItemSet)
    {
        set< set<string> > candFreqKItemSet;
        set< set<string> >::iterator it = freqMItemSet.begin();
        set<string> originalItemSet;
    
        set<string> identicalSetRetain;
    
        //cout << "aprioriGen start" <<endl;
        while(it != freqMItemSet.end()){ 
            originalItemSet = *it;
    
            /*itr其实就是当前it自加一次所指*/        
            set< set<string> >::iterator itr = ++it;
            while(itr != freqMItemSet.end()){
                set<string> identicalSet(originalItemSet.begin(),originalItemSet.end());            
                set<string> setS(*itr);            
                identicalSetRetain.erase(identicalSetRetain.begin(),identicalSetRetain.end());
                identicalSetRetain = addAll(identicalSet,setS);//是取originalItemSet和setS的交集
    
                if(identicalSetRetain.size() == m+1){
                    if(!has_infrequent_subset(identicalSetRetain, freqMItemSet))                    
                        candFreqKItemSet.insert(identicalSetRetain);
                }          
                ++itr;
            }
        }
        //cout << "aprioriGen end" <<endl;
        return candFreqKItemSet;    
    }
    
    //-------------------------------------------------------------------------
    //使用先验知识,剪枝。删除候选k项集中存在k-1项的子集
    //-------------------------------------------------------------------------
    bool Apriori::has_infrequent_subset(set<string> &candKItemSet, set< set<string> > &freqMItemSet)
    {
        int occurs = 0;
    
        if(freqMItemSet.count(candKItemSet))
            return true;
    
        return false;
    }
    //-------------------------------------------------------------------------
    //获取mapSet的键值,存放于set中
    //-------------------------------------------------------------------------
    set< set<string> > Apriori::keySet(map< set<string>, int > &mapSet)
    {
        map< set<string>, int >::iterator it = mapSet.begin();
        set< set<string> > retSet;
    
        while(it != mapSet.end()){
            retSet.insert(it->first);
            ++it;
        }
    
        return retSet;
    }
    main.cpp
    
    //---------------------------------------------------
    //创建日期: 2015-10-14
    //修改日期: 2015-11-01
    //作    者: yicm
    //版    本: 
    //说    明: Apriori算法C++实现。本实现尽可能地去提高运行效率了,
    //          在aprioriGen函数中运行时间是跟min_sup有关的,min_sup越
    //          大则运行时间越短,min_sup越小则运行时间越长;在getFreqKItemSet
    //          函数中运行时间主要都消耗在扫描事务数据库,并统计每个候选的个数。
    //---------------------------------------------------
    
    
    #include <iostream>
    #include "apriori.h"
    
    
    int main(int argc,char *argv[])
    {
        if(argc != 5){
            cout << "usage: apriori.exe [min_sup] [topic-i.txt] [max-i.txt] [closed-i.txt]" << endl;
            return 0;
        }
        int min_sup = atoi(argv[1]);
    
        Apriori apriori(argv[2],min_sup);
        /*获取文本文件中原始数据*/
        apriori.buildData();
    #if (1)
        map<int, map< set<string>, int > > L; 
        map< set<string>, int > freq1ItemSetMap = apriori.findFrequent1Itemsets();    
        set< set<string> > freqKItemSet = apriori.keySet(freq1ItemSetMap);
        L.insert(make_pair(1,freq1ItemSetMap));    
        //for循环退出条件为:得到频繁k项集为空集时
    
        for(int k = 2; ;++k){
            //cout << "k= " << k <<endl;        
            map< set<string>, int> freqKItemSetMap = apriori.getFreqKItemSet(k, freqKItemSet);
            L.insert(make_pair(k,freqKItemSetMap));
            if(freqKItemSetMap.size() != 0) {
                set< set<string> > freqKItemSetTemp = apriori.keySet(freqKItemSetMap);            
                freqKItemSet = apriori.keySet(freqKItemSetMap);            
            }
            else {
                //cout << "k= " << k <<endl;
                break;
            }
        }
    
        //打印所有满足min_sup的频繁集    
        map<int, map< set<string>, int > >::iterator allLIt = L.begin();
        while(allLIt != L.end()){
            if(allLIt->second.size() != 0)cout << "频繁k" << allLIt->first << "项集: " << endl;
            apriori.printMapSet(allLIt->second);
            ++allLIt;
        } 
        //获取每个topic-i.txt的最大频繁项集
        ofstream maxFstream;
    
        maxFstream.open(argv[3],fstream::out);
        map<int, map< set<string>, int > >::iterator maxLIt = --(--L.end());
        map< set<string>, int >::iterator maxit = maxLIt->second.begin();
        while(maxit != maxLIt->second.end()){
            set<string>::iterator maxitSet = maxit->first.begin();
            maxFstream << "#" << maxit->second << "\t";
            maxFstream << "[" ;
            while(maxitSet != maxit->first.end()){
                maxFstream << *maxitSet << "," ;
                ++maxitSet;
            }
            maxFstream << "]" << endl;
            ++maxit;
        }
        maxFstream.close();
        //获取每个topic-i.txt的所有闭项集
        //第一步:求原始数据集D中的每项的支持度
        //第二步:比较第k项频繁项集的每一项的直接超集的支持度是否与该项支持度相同,直至比较完该k项频繁项集
        //第三步:循环所有的频繁项集,并保存闭项集
        //第四步:将所有的闭项集输入到closed-i.txt中   
        ofstream closedFstream;    
        closedFstream.open(argv[4],fstream::out);
    
        map< set<string>, int> textDatabaseSur = apriori.getTextDatabaseSurpport();    
        cout << "原始数据集D各项支持度" <<endl;
        apriori.printMapSet(textDatabaseSur);
    
        map<int, map< set<string>, int > >::iterator closedLIt = L.begin();
        while(closedLIt != L.end()){
            map< set<string> , int>::iterator closedMapSetIt = closedLIt->second.begin();
            while(closedMapSetIt != closedLIt->second.end()){
                map< set<string>, int>::iterator textDatabaseSurIt = textDatabaseSur.begin();
                while(textDatabaseSurIt != textDatabaseSur.end()){                
                    if(apriori.retainAll(closedMapSetIt->first,textDatabaseSurIt->first) == (closedMapSetIt->first)){                    
                        if((closedMapSetIt->second) == (textDatabaseSurIt->second))
                            break;                    
                    } 
    
                    ++textDatabaseSurIt;
                }
                //该k项频繁项集不是闭项集
                if(textDatabaseSurIt != textDatabaseSur.end()){
                    break;
                }
                ++closedMapSetIt;
            }
            //该k项频繁项集是闭项集,写入到文件中保存
            if((closedMapSetIt == closedLIt->second.end()) && (closedLIt->second.size() != 0)){
                cout << "存在第"<< closedLIt->first << "项频繁闭项集:" <<endl;
                //apriori.printMapSet(closedLIt->second);
                map< set<string>, int >::iterator closedit = closedLIt->second.begin();
                while(closedit != closedLIt->second.end()){
                    set<string>::iterator itSet = closedit->first.begin();
                    closedFstream << "#" << closedit->second << "\t";
                    closedFstream << "[" ;
                    while(itSet != closedit->first.end()){
                        closedFstream << *itSet << "," ;
                        ++itSet;
                    }
                    closedFstream << "]" << endl;
                    ++closedit;
                }
            }        
            ++closedLIt;
        }
    
    #endif
    
    #if (0)
        /*获取文本文件中原始数据*/
        apriori.buildData();
        cout << "----------------" << endl;
        /*获取候选集1*/
        map<string, int> candidate1ItemSet = apriori.getCandidate1ItemSet();
        cout << "候选1项集大小: " << candidate1ItemSet.size() << endl;
        /*获取频繁项集1*/
        map< set<string>, int > freq1ItemSetMap = apriori.findFrequent1Itemsets();
        cout << "频繁1项集大小: " << freq1ItemSetMap.size() << endl;
        /*打印频繁项集1*/
        cout << "-频繁1项集-" << endl;
        apriori.printMapSet(freq1ItemSetMap);
        /*获取候选集2*/
        set< set<string> > C2 = apriori.aprioriGen(1, apriori.keySet(freq1ItemSetMap));    
        cout << "-候选2项集-" << endl;
        apriori.printsetSet(C2);
        /*获取频繁2项集*/
        set< set<string> > C1 = apriori.keySet(freq1ItemSetMap);
        cout << "-频繁1项集键集--" << endl;
        apriori.printsetSet(C1);
        map< set<string>, int> L2 = apriori.getFreqKItemSet(2,C1);
        cout << "---频繁2项集----" << endl;
        apriori.printMapSet(L2);
        /*获取频繁3项集*/
        map< set<string>, int> L3 = apriori.getFreqKItemSet(3,C2);
        cout << "---频繁3项集----" << endl;
        apriori.printMapSet(L3);
    #endif    
        return 0;
    }
    

    源码下载:http://download.csdn.net/detail/freeape/9232031

    展开全文
  • 为解决在挖掘频繁项集时由忽略项目间重要性差异以及最小支持度频繁变动而导致的挖掘效率低以及利用率低。通过关系矩阵解决数据体量大造成的挖掘效率低的问题;通过加权规则解决不同业务项目间重要性差异问题;通过...
  • 为提高频繁项集的挖掘效率, 提出了最大频繁项集树的概念和基于FP2t ree 的最大频繁项集挖掘算法 MAXFP2M iner. 首先建立了FP2t ree, 在此基础上建立最大频繁项集树MAXFP2t ree,MAXFP2t ree 中包含了所有最 ...
  • Apriori算法是解决频繁项集挖掘最常用的算法之一,但多轮迭代扫描完整数据集的计算方式,严重影响算法效率且难以并行化处理。随着数据规模的持续增大,这一问题日益严重。针对这一问题,提出了一种基于项编码和Spark...
  • 针对相关算法在处理频繁项集更新时所存在的问题,提出了一种基于矩阵的频繁项集更新算法。该算法首先以时间为基准将更新后的数据库分为原数据库和新增数据库,分别将它们转换为0-1矩阵,通过矩阵裁剪、位运算产生...
  • 基于现有的关联规则挖掘算法,提出了一种通过循环迭代增加...并提出了一种基于索引数组的频繁项集挖掘新算法。该算法只需扫描数据库两次就能发现所有频繁项集。实验结果表明,该算法可以有效提高频繁项集的挖掘效率。
  • 频繁项集挖掘是关联规则挖掘的重要内容,而现有的频繁项集挖掘算法在数据库扫描和复杂数据结构构建方面消耗过多的时间,效率较低。为克服现有频繁项集挖掘算法的不足,提出了基于随机相遇的频繁项集挖掘算法。在随机...
  • 利用有向项集图来存储事务数据库中有关频繁项集的信息,提出了有向项集图的三叉链表式存储结构和基于有向项集图的最大频繁项集挖掘算法。它不仅实现了事务数据库的一次扫描,减少了I/O代价,而且可以同时解决好稀疏...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,122
精华内容 29,248
关键字:

频繁项集