精华内容
下载资源
问答
  • 【机器学习】四、关联规则原理及实例
    千次阅读
    2019-07-09 18:09:46

    一、关联规则简介
    关联规则(Apriori算法),又称为关联分析。其目的是找出,一堆事物中具有关联的事物。
    关联规则最经典的案例就是“啤酒与尿布”,沃尔玛拥有世界上最大的数据仓库系统,为了能够准确了解顾客在其门店的购买习惯,沃尔玛对其顾客的购物行为进行购物篮分析,想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上,沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。码字不易,喜欢请点赞!!!
    在这里插入图片描述
    一个意外的发现是:"跟尿布一起购买最多的商品竟是啤酒!经过大量实际调查和分析,揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式:在美国,一些年轻的父亲下班后经常要到超市去买婴儿尿布,而他们中有30%~40%的人同时也为自己买一些啤酒。产生这一现象的原因是:美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布,而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

    二、关联规则
    关联规则最重要的就是支持度Support和置信度Confidence。

    1. 支持度的计算方法:
    #下面式中XY表示XY同时发生的次数,N表示总事物数
    support(X->Y) = XY/N
    
    1. 置信度的计算方法:
    confidence(X->Y) = support(X->Y) / support(X)
    <=>
    #XY表示XY同时发生的次数,X表示X发生的次数
    confidence(X->Y) = XY/X
    

    最终找到的规则,要满足支持度和置信度即可。

    三、关联规则使用
    关联规则的使用可以看我下面这篇博客,是一个公司机器学习岗位的笔试题。
    https://blog.csdn.net/Asher117/article/details/87745195

    更多相关内容
  • 第三章 关联规则挖掘理论和算法 内容提要;关联规则挖掘Association Rule Mining是数据挖掘中研究较早而且至今仍活跃的研究方法之一 最早是由Agrawal等人提出的1993最初提出的动机是针对购物篮分析Basket Analysis...
  • 这八个定义包含了关联规则相关的几个重要基本概念,关联规则挖掘主要有两个问题: 找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集。 利用频繁项集生成所需要的关联规则,根据用户设定的最小可信度...

    概念

    定义一:设I={i1,i2,…,im},是m个不同的项目的集合,每个ik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度,长度为k的项集称为k-项集。引例中每个商品就是一个项目,项集为I={bread, beer, cake,cream, milk, tea},I的长度为6。
    定义二:每笔交易T是项集I的一个子集。对应每一个交易有一个唯一标识交易号,记作TID。交易全体构成了交易数据库D,|D|等于D中交易的个数。引例中包含10笔交易,因此|D|=10。

    定义三:对于项集X,设定count(X⊆T)为交易集D中包含X的交易的数量,则项集X的支持度为:

    support(X)=count(X⊆T)/|D|

    引例中X={bread, milk}出现在T1,T2,T5,T9和T10中,所以支持度为0.5。

    定义四:最小支持度是项集的最小支持阀值,记为SUPmin,代表了用户关心的关联规则的最低重要性。支持度不小于SUPmin 的项集称为频繁集,长度为k的频繁集称为k-频繁集。如果设定SUPmin为0.3,引例中{bread, milk}的支持度是0.5,所以是2-频繁集。

    定义五:关联规则是一个蕴含式:

    R:X⇒Y

    其中X⊂I,Y⊂I,并且X∩Y=⌀。表示项集X在某一交易中出现,则导致Y以某一概率也会出现。用户关心的关联规则,可以用两个标准来衡量:支持度和可信度。

    定义六:关联规则R的支持度是交易集同时包含X和Y的交易数与|D|之比。即:

    support(X⇒Y)=count(X⋃Y)/|D|

    支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。

    定义七:对于关联规则R,可信度是指包含X和Y的交易数与包含X的交易数之比。即:

    confidence(X⇒Y)=support(X⇒Y)/support(X)

    可信度反映了如果交易中包含X,则交易包含Y的概率。一般来说,只有支持度和可信度较高的关联规则才是用户感兴趣的。

    定义八:设定关联规则的最小支持度和最小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin ,则称为强关联规则。关联规则挖掘的目的就是找出强关联规则,从而指导商家的决策。

    这八个定义包含了关联规则相关的几个重要基本概念,关联规则挖掘主要有两个问题:

    找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集。
    利用频繁项集生成所需要的关联规则,根据用户设定的最小可信度筛选出强关联规则。
    

    目前研究人员主要针对第一个问题进行研究,找出频繁集是比较困难的,而有了频繁集再生成强关联规则就相对容易了。

    理论基础

    首先来看一个频繁集的性质。

    定理:如果项目集X是频繁集,那么它的非空子集都是频繁集。

    根据定理,已知一个k-频繁集的项集X,X的所有k-1阶子集都肯定是频繁集,也就肯定可以找到两个k-1频繁集的项集,它们只有一项不同,且连接后等于X。这证明了通过连接k-1频繁集产生的k-候选集覆盖了k-频繁集。同时,如果k-候选集中的项集Y,包含有某个k-1阶子集不属于k-1频繁集,那么Y就不可能是频繁集,应该从候选集中裁剪掉。Apriori算法就是利用了频繁集的这个性质。

    算法实现过程

    连接以及修剪依据关联规则实现过程算法核心及其瓶颈

    代码实现

    def local_data(file_path):
        import pandas as pd
    
        dt = pd.read_excel(file_path)
        data = dt['con']
        locdata = []
        for i in data:
            locdata.append(str(i).split(","))
    
       # print(locdata)  # change to [[1,2,3],[1,2,3]]
        length = []
        for i in locdata:
            length.append(len(i))  # 计算长度并存储
       # print(length)
        ki = length[length.index(max(length))]
       # print(length[length.index(max(length))])  # length.index(max(length)读取最大值的位置,然后再定位取出最大值
    
        return locdata,ki
    
    def create_C1(data_set):
        """
        Create frequent candidate 1-itemset C1 by scaning data set.
        Args:
            data_set: A list of transactions. Each transaction contains several items.
        Returns:
            C1: A set which contains all frequent candidate 1-itemsets
        """
        C1 = set()
        for t in data_set:
            for item in t:
                item_set = frozenset([item])
                C1.add(item_set)
        return C1
    
    
    def is_apriori(Ck_item, Lksub1):
        """
        Judge whether a frequent candidate k-itemset satisfy Apriori property.
        Args:
            Ck_item: a frequent candidate k-itemset in Ck which contains all frequent
                     candidate k-itemsets.
            Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
        Returns:
            True: satisfying Apriori property.
            False: Not satisfying Apriori property.
        """
        for item in Ck_item:
            sub_Ck = Ck_item - frozenset([item])
            if sub_Ck not in Lksub1:
                return False
        return True
    
    
    def create_Ck(Lksub1, k):
        """
        Create Ck, a set which contains all all frequent candidate k-itemsets
        by Lk-1's own connection operation.
        Args:
            Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
            k: the item number of a frequent itemset.
        Return:
            Ck: a set which contains all all frequent candidate k-itemsets.
        """
        Ck = set()
        len_Lksub1 = len(Lksub1)
        list_Lksub1 = list(Lksub1)
        for i in range(len_Lksub1):
            for j in range(1, len_Lksub1):
                l1 = list(list_Lksub1[i])
                l2 = list(list_Lksub1[j])
                l1.sort()
                l2.sort()
                if l1[0:k-2] == l2[0:k-2]:
                    Ck_item = list_Lksub1[i] | list_Lksub1[j]
                    # pruning
                    if is_apriori(Ck_item, Lksub1):
                        Ck.add(Ck_item)
        return Ck
    
    
    def generate_Lk_by_Ck(data_set, Ck, min_support, support_data):
        """
        Generate Lk by executing a delete policy from Ck.
        Args:
            data_set: A list of transactions. Each transaction contains several items.
            Ck: A set which contains all all frequent candidate k-itemsets.
            min_support: The minimum support.
            support_data: A dictionary. The key is frequent itemset and the value is support.
        Returns:
            Lk: A set which contains all all frequent k-itemsets.
        """
        Lk = set()
        item_count = {}
        for t in data_set:
            for item in Ck:
                if item.issubset(t):
                    if item not in item_count:
                        item_count[item] = 1
                    else:
                        item_count[item] += 1
        t_num = float(len(data_set))
        for item in item_count:
            if (item_count[item] / t_num) >= min_support:
                Lk.add(item)
                support_data[item] = item_count[item] / t_num
        return Lk
    
    
    def generate_L(data_set, k, min_support):
        """
        Generate all frequent itemsets.
        Args:
            data_set: A list of transactions. Each transaction contains several items.
            k: Maximum number of items for all frequent itemsets.
            min_support: The minimum support.
        Returns:
            L: The list of Lk.
            support_data: A dictionary. The key is frequent itemset and the value is support.
        """
        support_data = {}
        C1 = create_C1(data_set)
        L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)
        Lksub1 = L1.copy()
        L = []
        L.append(Lksub1)
        for i in range(2, k+1):
            Ci = create_Ck(Lksub1, i)
            Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)
            Lksub1 = Li.copy()
            L.append(Lksub1)
        return L, support_data
    
    
    def generate_big_rules(L, support_data, min_conf):
        """
        Generate big rules from frequent itemsets.
        Args:
            L: The list of Lk.
            support_data: A dictionary. The key is frequent itemset and the value is support.
            min_conf: Minimal confidence.
        Returns:
            big_rule_list: A list which contains all big rules. Each big rule is represented
                           as a 3-tuple.
        """
        big_rule_list = []
        sub_set_list = []
        for i in range(0, len(L)):
            for freq_set in L[i]:
                for sub_set in sub_set_list:
                    if sub_set.issubset(freq_set):
                        conf = support_data[freq_set] / support_data[freq_set - sub_set]
                        big_rule = (freq_set - sub_set, sub_set, conf)
                        if conf >= min_conf and big_rule not in big_rule_list:
                            # print freq_set-sub_set, " => ", sub_set, "conf: ", conf
                            big_rule_list.append(big_rule)
                sub_set_list.append(freq_set)
        return big_rule_list
    
    
    if __name__ == "__main__":
        """
        Test
        """
        file_path = "test_aa.xlsx"
      
        data_set,k = local_data(file_path)
        L, support_data = generate_L(data_set, k, min_support=0.2)
        big_rules_list = generate_big_rules(L, support_data, min_conf=0.4)
        print(L)
        for Lk in L:
            if len(list(Lk)) == 0:
                break
            print("="*50)
            print("frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport")
            print("="*50)
            for freq_set in Lk:
                print(freq_set, support_data[freq_set])
        print()
        print("Big Rules")
        for item in big_rules_list:
            print(item[0], "=>", item[1], "conf: ", item[2])
    

    本文原博客链接

    https://www.cnblogs.com/shizhenqiang/p/8251213.html

    展开全文
  • 1. 关联规则 关联规则是形如X=>Y的蕴含式,其中X、Y分别是一事务的真子集,且X∩Y=Φ。X称为规则的前提,Y称为规则的结果。关联规则反映出X中的项目在事务中出现时,Y中的项目也跟着出现的规律。 2.支持度 关联...

    一、基本概念

    1. 关联规则

    关联规则是形如X=>Y的蕴含式,其中X、Y分别是一事务的真子集,且X∩Y=Φ。X称为规则的前提,Y称为规则的结果。关联规则反映出X中的项目在事务中出现时,Y中的项目也跟着出现的规律。

    2.支持度

    关联规则的支持度是事务集中同时包含X和Y的事务数量与所有事务数量之比,它反映了X和Y中所含的事务的项在事务集中同时出现的频率,记为support(X=>Y),即support(X=>Y)=support(X∪Y)=P(XY)

    3.置信度

    关联规则的置信度是事务集中同时包含X和Y的事务数量与包含X的事务数量之比,记为confidence(X=>Y),置信度反映了包含X的事务中出现Y的条件概率。即 confidence(X=>Y)=support(X∪Y)/support(X)=P(XY)

    4. 频繁项集

    设U∈I,项目集U在事务集T上的支持度是包含U的事务在T中所占的百分比,即support(U)=|| {t∈T | U∈t} || / ||T||。式中,|| … ||表示集合中的元素数目。对项目集I,在事务数据库T中所有满足用户指定的最小支持度的项目集,即不小于最小支持度阀值的I的非空子集,称为频繁项目集或大项目集。

    二、Apriori算法原理

    1.算法思想

    Apriori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度,发现所有的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描,第一次扫描得到频繁1-项集L1,第k(k>1)次扫描首先利用第(k-1)次扫描的结果L(k-1)来产生候选k-项集的集合Ck,然后在扫描过程中确定Ck中元素的支持度,最后在每一次扫描结束时计算频繁k-项集的集合Lk,算法在当候选k-项集的集合Ck为空时结束。

    2.Apriori算法产生频繁项集

    产生频繁项集的过程主要分为连接和剪枝两步:
    (1)连接步。为找到Lk(k≧2),通过L(k-1)与自身连接产生候选k-项集的集合Ck。自身连接时,两个项集对应的想按从小到大顺序排列好,当前除最后一项外的其他项都相等时,两个项集可连接,连接产生的结果为(l1[1], l1[2], …, l1[k-1], l2[k-2])。
    (2)剪枝步。由Apriori算法的性质可知,频繁k-项集的任何子集必须是频繁项集。由连接步产生的集合Ck需进行验证,除去不满足支持度的非频繁k-项集。

    3.Apriori算法的基本步骤

    (1)扫描全部数据,产生候选1-项集的集合C1;
    (2)根据最小支持度,由候选1-项集的集合C1产生频繁1-项集的集合L;
    (3)对k>1,重复执行步骤(4)、(5)、(6);
    (4)由Lk执行连接和剪枝操作,产生候选(k+1)-项集的集合C(k+1)。
    (5)根据最小支持度,由候选(k+1)-项集的集合C(k+1),产生频繁(k+1)-项集的集合L(k+1);
    (6)若L≠Ф,则k=k+1,跳往步骤(4);否则往下执行;
    (7)根据最小置信度,由频繁项集产生强关联规则,程序结束。

    三.Apriori算法实例

    下表是一个数据库事物列表,在数据库中有9笔交易,即 |D| =9下面描述一下Apriori算法寻找D中频繁项集的过程。
    数据库数据列表
    设最小支持度为2,产生候选项集及频繁项集的过程如下:
    1)第一次扫描
    扫描数据库D获得每个候选项的计数:
    在这里插入图片描述
    由于最小事务支持数为2,没有删除任何项目。
    2)第二次扫描
    为发现频繁2-项集的集合L2,算法使用L1∞L1产生候选2-项集的集合C2。在剪枝步没有候选项集从C2删除,因为这些候选项的子集也是频繁的。
    在这里插入图片描述
    3)第三次扫描
    L2∞L2产生候选3-项集的集合C3。
    在这里插入图片描述
    候选3项集C3产生的详细列表如下:
    ①连接C3=L2∞L2={{I1, I2}, {I1, I3},{I1, I5},{I2, I3},{I2, I4},{I2, I5},}∞{{I1, I2}, {I1, I3},{I1, I5},{I2, I3},{I2, I4},{I2, I5},}={{I1, I2, I3}, {I1, I2, I5},{I1, I3, I5},{I2, I3, I4},{I2, I3, I5},{I2, I4, I5},}。
    ②使用Apriori性质剪枝:频繁项集的所有非空子集也必须是频繁的。例如{I1, I3, I5}的2-项子集是{I1, I3}, {I1, I5}, {I3, I5}。{I3, I5}不是L2的元素,因此不是频繁的。所有删掉C3中的{I1, I3, I5}。剪枝C3={{I1, I2, I3},{I1, I2, I5}}。

    4)第四次扫描
    算法使用L3∞L3产生候选集4-项集的集合C4。L3∞L3={{I1, I2, I3, I4}},根据Apriori性质,因为它的子集{I2, I3, I5}不是频繁的,使用这个项集被删除。这样C4=Φ,因此算法结束,找到了所有频繁项集。

    四、源码

    #include<iostream>
    #include<string> 
    #include <vector>
    #include <map>
    #include <algorithm>
    using namespace std;
    
    class Apriori
    {
    public:
    	Apriori(size_t is = 0, unsigned int mv = 0)
    	{
    		item_size = is;
    		min_value = mv;
    	}
    	//~Apriori() {};
    	void getItem();
    	map< vector<string>, unsigned int> find_freitem();//求事务的频繁项
    	//连接连个k-1级频繁项,得到第k级频繁项
    	map< vector<string>, unsigned int > apri_gen(unsigned int K, map< vector<string>, unsigned int > K_item);
    	//展示频繁项集
    	void showAprioriItem(unsigned int K, map< vector<string>, unsigned int > showmap);
    private:
    	map< int, vector<string> > item;//存储所有最开始的事务及其项
    	map< vector<string>, unsigned int > K_item;//存储频繁项集
    	size_t item_size;//事务数目
    	unsigned  int min_value;//最小阈值
    };
    
    void Apriori::getItem()//用户输入最初的事务集
    {
    	int ci = item_size;
    	for (int i = 0;i < ci;i++)
    	{
    		string str;
    		vector<string> temp;
    		cout << "请输入第 " << i + 1 << "个事务的项集(123 end):";
    		while (cin >> str && str != "123")
    		{
    			temp.push_back(str);
    		}
    		sort(temp.begin(), temp.end());
    		pair< map<int, vector<string> >::iterator, bool> ret = item.insert(make_pair(i + 1, temp));
    		if (!ret.second)
    		{
    			--i;
    			cout << "你输入的元素已存在!请重新输入!" << endl;
    		}
    	}
    	cout << "-------------运行结果如下:--------------" << endl;
    }
    
    map< vector<string>, unsigned int> Apriori::find_freitem()
    {
    	unsigned int i = 1;
    	bool isEmpty = false;
    	map< int, vector<string> >::iterator mit;
    	for (mit = item.begin();mit != item.end();mit++)
    	{
    		vector<string> vec = mit->second;
    		if (vec.size() != 0)
    			break;
    	}
    	if (mit == item.end())//事务集为空
    	{
    		isEmpty = true;
    		cout << "事务集为空!程序无法进行..." << endl;
    		map< vector<string>, unsigned int> empty;
    		return empty;
    	}
    	while (1)
    	{
    		map< vector<string>, unsigned int > K_itemTemp = K_item;
    
    		K_item = apri_gen(i++, K_item);
    
    		if (K_itemTemp == K_item)
    		{
    			i = UINT_MAX;
    			break;
    		}
    		//判断是否需要进行下一次的寻找
    		map< vector<string>, unsigned int > pre_K_item = K_item;
    		size_t Kitemsize = K_item.size();
    		//存储应该删除的第K级频繁项集,不能和其他K级频繁项集构成第K+1级项集的集合
    		if (Kitemsize != 1 && i != 1)
    		{
    			vector< map< vector<string>, unsigned int >::iterator > eraseVecMit;
    			map< vector<string>, unsigned int >::iterator pre_K_item_it1 = pre_K_item.begin(), pre_K_item_it2;
    			while (pre_K_item_it1 != pre_K_item.end())
    			{
    				map< vector<string>, unsigned int >::iterator mit = pre_K_item_it1;
    				bool isExist = true;
    				vector<string> vec1;
    				vec1 = pre_K_item_it1->first;
    				vector<string> vec11(vec1.begin(), vec1.end() - 1);
    				while (mit != pre_K_item.end())
    				{
    					vector<string> vec2;
    					vec2 = mit->first;
    					vector<string> vec22(vec2.begin(), vec2.end() - 1);
    					if (vec11 == vec22)
    						break;
    					++mit;
    				}
    				if (mit == pre_K_item.end())
    					isExist = false;
    				if (!isExist && pre_K_item_it1 != pre_K_item.end())
    					eraseVecMit.push_back(pre_K_item_it1);//该第K级频繁项应该删除
    				++pre_K_item_it1;
    			}
    			size_t eraseSetSize = eraseVecMit.size();
    			if (eraseSetSize == Kitemsize)
    				break;
    			else
    			{
    				vector< map< vector<string>, unsigned int >::iterator >::iterator currentErs = eraseVecMit.begin();
    				while (currentErs != eraseVecMit.end())//删除所有应该删除的第K级频繁项
    				{
    					map< vector<string>, unsigned int >::iterator eraseMit = *currentErs;
    					K_item.erase(eraseMit);
    					++currentErs;
    				}
    			}
    		}
    		else
    			if (Kitemsize == 1)
    				break;
    	}
    	cout << endl;
    	showAprioriItem(i, K_item);
    	return K_item;
    }
    
    map< vector<string>, unsigned int > Apriori::apri_gen(unsigned int K, map< vector<string>, unsigned int > K_item)
    {
    	if (1 == K)//求候选集C1
    	{
    		size_t c1 = item_size;
    		map< int, vector<string> >::iterator mapit = item.begin();
    		vector<string> vec;
    		map<string, unsigned int> c1_itemtemp;
    		while (mapit != item.end())//将原事务中所有的单项统计出来
    		{
    
    			vector<string> temp = mapit->second;
    			vector<string>::iterator vecit = temp.begin();
    			while (vecit != temp.end())
    			{
    				pair< map<string, unsigned int>::iterator, bool > ret = c1_itemtemp.insert(make_pair(*vecit++, 1));
    				if (!ret.second)
    				{
    					++ret.first->second;
    				}
    			}
    			++mapit;
    		}
    		map<string, unsigned int>::iterator item_it = c1_itemtemp.begin();
    		map< vector<string>, unsigned int > c1_item;
    		while (item_it != c1_itemtemp.end())//构造第一级频繁项集
    		{
    			vector<string> temp;
    			if (item_it->second >= min_value)
    			{
    				temp.push_back(item_it->first);
    				c1_item.insert(make_pair(temp, item_it->second));
    			}
    			++item_it;
    		}
    		return c1_item;
    	}
    	else
    	{
    		cout << endl;
    		showAprioriItem(K - 1, K_item);
    		map< vector<string>, unsigned int >::iterator ck_item_it1 = K_item.begin(), ck_item_it2;
    		map< vector<string>, unsigned int > ck_item;
    		while (ck_item_it1 != K_item.end())
    		{
    			ck_item_it2 = ck_item_it1;
    			++ck_item_it2;
    			map< vector<string>, unsigned int >::iterator mit = ck_item_it2;
    
    			//取当前第K级频繁项与其后面的第K级频繁项集联合,但要注意联合条件
    			//联合条件:连个频繁项的前K-1项完全相同,只是第K项不同,然后两个联合生成第K+1级候选频繁项
    			while (mit != K_item.end())
    			{
    				vector<string> vec, vec1, vec2;
    				vec1 = ck_item_it1->first;
    				vec2 = mit->first;
    				vector<string>::iterator vit1, vit2;
    
    				vit1 = vec1.begin();
    				vit2 = vec2.begin();
    				while (vit1 < vec1.end() && vit2 < vec2.end())
    				{
    					string str1 = *vit1;
    					string str2 = *vit2;
    					++vit1;
    					++vit2;
    					if (K == 2 || str1 == str2)
    					{
    						if (vit1 != vec1.end() && vit2 != vec2.end())
    						{
    							vec.push_back(str1);
    						}
    
    					}
    					else
    						break;
    				}
    				if (vit1 == vec1.end() && vit2 == vec2.end())
    				{
    					--vit1;
    					--vit2;
    					string str1 = *vit1;
    					string str2 = *vit2;
    					if (str1 > str2)
    					{
    						vec.push_back(str2);
    						vec.push_back(str1);
    					}
    					else
    					{
    						vec.push_back(str1);
    						vec.push_back(str2);
    					}
    					map< int, vector<string> >::iterator base_item = item.begin();
    					unsigned int Acount = 0;
    					while (base_item != item.end())//统计该K+1级候选项在原事务集出现次数
    					{
    						unsigned int count = 0, mincount = UINT_MAX;
    						vector<string> vv = base_item->second;
    						vector<string>::iterator vecit, bvit;
    						for (vecit = vec.begin();vecit < vec.end();vecit++)
    						{
    							string t = *vecit;
    							count = 0;
    							for (bvit = vv.begin();bvit < vv.end();bvit++)
    							{
    								if (t == *bvit)
    									count++;
    							}
    							mincount = (count < mincount ? count : mincount);
    						}
    						if (mincount >= 1 && mincount != UINT_MAX)
    							Acount += mincount;
    						++base_item;
    					}
    					if (Acount >= min_value && Acount != 0)
    					{
    						sort(vec.begin(), vec.end());
    						//该第K+1级候选项为频繁项,插入频繁项集
    						pair< map< vector<string>, unsigned int >::iterator, bool> ret = ck_item.insert(make_pair(vec, Acount));
    						if (!ret.second)
    						{
    							ret.first->second += Acount;
    						}
    					}
    				}
    				++mit;
    			}
    			++ck_item_it1;
    		}
    		if (ck_item.empty())//该第K+1级频繁项集为空,说明调用结束,把上一级频繁项集返回
    			return K_item;
    		else
    			return ck_item;
    	}
    }
    void Apriori::showAprioriItem(unsigned int K, map< vector<string>, unsigned int > showmap)
    {
    	map< vector<string>, unsigned int >::iterator showit = showmap.begin();
    	if (K != UINT_MAX)
    		cout << endl << "第 " << K << " 级频繁项集为:" << endl;
    	else
    		cout << "最终的频繁项集为:" << endl;
    	cout << "项  集" << "  \t  " << "频率" << endl;
    	while (showit != showmap.end())
    	{
    		vector<string> vec = showit->first;
    		vector<string>::iterator vecit = vec.begin();
    		cout << "{ ";
    		while (vecit != vec.end())
    		{
    			cout << *vecit << "  ";
    			++vecit;
    		}
    		cout << "}" << "  \t  ";
    		cout << showit->second << endl;
    		++showit;
    	}
    }
    
    unsigned int parseNumber(const char * str)//对用户输入的数字进行判断和转换
    {
    	if (str == NULL)
    		return 0;
    	else
    	{
    		unsigned int num = 0;
    		size_t len = strlen(str);
    		for (size_t i = 0;i < len;i++)
    		{
    			num *= 10;
    			if (str[i] >= '0' && str[i] <= '9')
    				num += str[i] - '0';
    			else
    				return 0;
    		}
    		return num;
    	}
    }
    
    void main()
    {
    	//Apriori a;
    	unsigned int itemsize = 0;
    	unsigned int min;
    
    	do
    	{
    		cout << "请输入事务数:";
    		char * str = new char;
    		cin >> str;
    		itemsize = parseNumber(str);
    		if (itemsize == 0)
    		{
    			cout << "请输入大于0正整数!" << endl;
    		}
    	} while (itemsize == 0);
    
    	do
    	{
    		cout << "请输入最小阈值:";
    		char * str = new char;
    		cin >> str;
    		min = parseNumber(str);
    		if (min == 0)
    		{
    			cout << "请输入大于0正整数!" << endl;
    		}
    	} while (min == 0);
    
    	Apriori a(itemsize, min);
    	a.getItem();
    	map< vector<string>, unsigned int> AprioriMap = a.find_freitem();
    	//a.showAprioriItem(UINT_MAX,AprioriMap);
    	system("pause");
    }
    
    

    本文参考了王振武编著《数据挖掘算法原理与实现》一书Apriori算法相关内容。

    展开全文
  • 数据挖掘中关联规则挖掘的应用研究 ,吴海玲,王志坚,本文首先介绍关联规则基本原理,并简单概括其挖掘任务,然后说明关联规则的经典挖掘算法Apriori算法,通过一个实例分析进一步明��
  • 关联规则推荐算法的原理及实现

    千次阅读 2017-04-28 14:34:38
    关联规则用来发现数据间潜在的关联,最典型的应用是电商网站的购物车分析。本文将通过一个简单的例子来说明关联规则中各个术语的含义以及具体的计算方法。 这是一些用户的购物数据,uid是用户的ID,后面是每个...
    关联规则用来发现数据间潜在的关联,最典型的应用是电商网站的购物车分析。本文将通过一个简单的例子来说明关联规则中各个术语的含义以及具体的计算方法。

    这是一些用户的购物数据,uid是用户的ID,后面是每个用户具体购买的商品名称,我们使用字母进行标识。下面我们将使用关联规则对这些数据进行分析,挖掘不同商品间的联系。

    首先将前面的一维的购物车流水数据转换为二维的列表。然后在这个基础上计算不同商品及商品组成出现的频率。

    在关联规则中,有三个重要的术语,分别为支持度(Support),可信度(Confidence)和作用度(Lift)。第一个属于是支持度,支持度是一件商品在所有购物车中出现的频率。如果我们希望分析的是两件商品的关联,那么支持度就是这两件商品同时出现的频率。支持度的作用是用来衡量关联规则重要性的指标,简单来说就是我们所要挖掘的关系有多大的普遍性,普遍性越大这条关联规则越重要。第二个术语是可信度,可信度是指两件商品中当第一件出现时,第二件商品同时出现的频率。可信度用来衡量关联规则的准确性。第三个术语是作用度,作用度用来衡量关联规则对于商品出现频率的影响。只有作用度大于1的关联规则才有实际的应用意义。下面我们分别介绍这三个术语的计算方法。

    支持度(Support)

    支持度是两件商品在所有购物车中同时出现的概率,可以记录为P(A U B)。支持度的计算公式为A,B两件物品同时出现的次数与购物车总数的比率。对于前面例子中,如果我们要计算商品A和B在5条购物车记录中的支持度,具体的计算公式为1/5。商品A和B在5条购物车记录中只在uid1中同时出现过。

    单件商品的支持度的计算方法与两件商品一样,如果我们要计算商品A的支持度,具体的计算公式为3/5。商品A在5条购物车记录中共出现了3次。单件商品的支持度描述了在没有其他商品影响的情况下,商品在购物车中出现的次数。

    可信度(Confidence)

    可信度是一个条件概率,两件商品其中一件出现在购物车中时,另一件也会出现的概率。可以记录为P(B|A)。对于前面的例子中,如果要计算A和B两件物品的可信度,具体的计算公式为1/3。商品A出现的3次,商品B同时出现的次数为1次。

    作用度(Lift)

    作用度通过衡量使用规则后的提升效果来判断规则是否可用,简单来说就是使用规则后商品在购物车中出现的次数是否高于商品单独出现在购物车中的频率。如果大于1说明规则有效,小于1则无效。对于前面的例子中,如果要计算规则A-B是否有效,计算公式为(1/5)/(3/5*3/5)=(0.2)/(0.6*0.6)=0.2/0.36=0.55。作用度小于1说明A-B规则对于商品B的提升没有效果。

    按照前面的计算公式我们分别对下面的四个规则进行了计算,在获得支持度,可信度后计算出了四个规则的作用度。其中A-D规则作用度大于1,说明对购物车中已经包含商品A的用户推荐商品D,购买概率是单独推荐D的1.11倍。


    来源:http://bluewhale.cc/2016-11-13/association-rules.html?utm_source=tuicool&utm_medium=referral

    展开全文
  • 关联规则挖掘——Apriori算法的基本原理以及改进

    万次阅读 多人点赞 2016-11-24 17:09:06
    问题引入关联规则挖掘发现大量数据中项集之间有趣的关联或者相互联系。关联规则挖掘的一个典型例子就是购物篮分析,该过程通过发现顾客放入其购物篮中不同商品之间的联系,分析出顾客的购买习惯,通过了解哪些商品...
  • 关于Weka的数据关联规则分析实验 班级 市场091 姓名 杨超 学号 200916012106 实验基本原理及目的 关联规则的定义 假设I是项的集合给定一个交易数据库其中每个事务(Transaction)t是I的非空子集即每一个交易都与一个...
  • 关联规则算法总结

    千次阅读 2021-08-12 15:35:32
    关联规则算法总结 文章目录一、Apriori、FP Growth算法原理:1.1 Apriori算法原理1.2 FP Growth(Frequent Pattern Growth)算法原理二、Apriori、FP Growth算法的实现三、实际应用 一、Apriori、FP Growth算法原理...
  • 关联规则基本概念 置信度的局限——错估某个关联规则的重要性 提升度和零事务的关系 先验原则 实际案例 代码实战 频繁项集和支持度 置信度调用 文末资源推荐 每文一语 走进关联规则 什么是关联规则? ...
  • 数据挖掘之关联规则(Apriori算法)

    万次阅读 多人点赞 2021-02-18 17:12:33
    关联规则想必大家都是听说过 尿布和啤酒的故事; 在一家超市里,有一个有趣的现象:尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话,而是发生在美国沃尔玛连锁店...
  • 文章目录关联规则基本思想算法基本过程算法总结 Apriori算法是第一个关联规则挖掘算法,也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系,以形成规则,其过程由连接(类矩阵运算)与剪枝(去掉...
  • 关联规则

    千次阅读 2017-11-13 20:15:55
    1. 算法简介关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。1993年,Agrawal等人在首先提出关联规则概念,同时给出了相应的挖掘算法AIS,但是性能较差。1994年,他们建立了项目集格...
  • 基于关联规则的推荐算法

    万次阅读 2019-01-09 17:15:45
    基于关联规则的推荐是根据历史数据统计不同规则出现的关系,形如:X-&amp;amp;gt;Y,表示X事件发生后,Y事件会有一定概率发生,这个概率是通过历史数据统计而来。 对于一个规则X-&amp;amp;gt;Y,有两个指标...
  • 数据挖掘——关联规则挖掘

    千次阅读 2022-04-14 15:54:57
    《数据挖掘》国防科技大学 ...关联规则是描述在一个交易中物品之间同时出现的规律的知识模式,更确切的说,关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响。 关联分析 association ana
  • 关联规则与数据分析

    千次阅读 2019-01-13 13:55:59
    关联规则的产生背景2. 基本概念与原理Aprioir算法用SSAS对医疗数据进行关联分析 关联规则 1.关联规则的产生背景 最早是由Agrawal等人提出的(1993)。最初的动机是针对购物篮分析(Basket Analysis)问题提出的,...
  • 关联规则—Apriori算法—FPTree

    万次阅读 多人点赞 2018-07-19 13:58:56
    1 关联规则 2 频繁项集(Frequent Itemset) 3 关联规则Association Rule 4 关联规则评估指标 5 关联规则挖掘方法: 6 关联规则 Apriori 算法 ▶ 关联规则新指标: [Math Processing Error]liftlift 值 ▶ 关联...
  • 介绍了关联规则挖掘的基本原理和方法,详细分析了分布式关联规则挖掘算法并给出其模型;提出一种充分考虑数据源异构性、基于相似度的的分布式数据挖掘方法。实验证明该模型提高了挖掘的准确率。
  • 首先就要满足支持度的要求,太小则直接被删去,支持度的大小可根据关联规则的多少调整 如果关联规则很少,可根据实际情况放宽支持度的要求。相关参数说明: + minSupport:最小支持度阈值 + minConf:最小置信度阈值 + ...
  • 10.1 关联规则基本概念 10.2 关联规则算法原理 10.3 分层搜索经典算法-Apriori算法 10.4 并行挖掘算法 10.5 增量更新挖掘算法 10.6 多层关联规则挖掘 10.7 多维关联规则挖掘 10.8 约束性关联规则挖掘 10.9 数量关联...
  • 基本原理是用二进制的形式将数据库事务转换成数字事务,并在以数字事务为记录的数据库中,运用二 进制的逻辑“与”运算计算出目标的效用度、包含目标的数字事务支持度和置信度,形成数字化的目标关联规则,接着根据...
  • 关联规则:购物篮分析,最早的出现是为了发现超市销售数据库中不同商品之间的关联关系。 文章目录1.案例引入(1)啤酒与尿布的故事(2)购物篮例子2.关联分析问题定义2.1二元表示2.2项集和支持度计数2.3 关联规则2.4...
  • 阐述了关联规则算法的基本原理,并利用事务数据库中的销售数据和SQL Server 2008 Data Mining Add-Ins for Microsoft office 2007工具挖掘顾客购买的商品之间各种有趣联系,帮助商家制定营销策略,最终向每个顾客...
  • 文章目录关联规则挖掘过程Apriori算法1. Apriori算法的基本思想2. Apriori算法产生频繁项集的过程3. Apriori算法的主要步骤4. 举例及代码实现 关联规则挖掘过程 关联规则挖掘问题可以分解为以下两个子问题 找频繁...
  • 关联规则(Association Rules)是反映一个事物与其他事物之间的相互依存性和关联性,如果两个或多个事物之间存在一定的关联关系,那么,其中一个事物就能通过其他事物预测到。关联规则是数据挖掘的一个重要技术,...
  • 关联规则分析也是一种比较常见的推荐算法,主要是根据历史数据统计不同规则出现的关系,比如:X−>Y X-&gt;YX−>Y,表示X XX事件发生后,Y YY事件也会有一定概率发生。 关联规则分析最著名的就是“啤酒-...
  • R语言--数据挖掘3---关联规则分析

    千次阅读 2021-04-15 21:54:51
    文章目录关联规则分析数据介绍基本原理介绍基本概念:Apriori算法有意义的关联规则案例分析总结反思学习其他同学的代码参考代码这其实跟前面排序是等价的查看分析结果inspect函数逐条查看关联规则by="lift"指定按...
  • 关联——基本概念和算法

    千次阅读 2019-04-10 21:37:07
    关联规则是反映一个事物与其他事物之间的相互依存性和关联性,是数据挖掘的一个重要技术,用于从大量数据中挖掘出有价值的数据项之间的相关关系。 2.支持度(support): 在X→Y关联规则下,同时出现{X,Y}的项集占总...
  • 数据挖掘之关联规则挖掘(Apriori算法)

    万次阅读 多人点赞 2018-06-06 11:31:34
    主要介绍关联规则基本概念、Apriori算法原理和Apriori算法实例,文章末尾处附加Apriori算法源程序。二、关联规则挖掘的基本概念关联规则挖掘发现大量数据中项集之间有趣的关联关系。如果两项或者多项属性之间存在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,791
精华内容 38,316
热门标签
关键字:

关联规则的基本原理