# -*- coding:UTF-8 -*-
"""
The class for association analysis and finding frequent item sets
@author: ZhaoRenhao
"""
import math

class Association(object):
    """
    分为两个步骤：
        1）找出所有频繁项集
        2）由频繁项集产生强关联规则
    """
    def __init__(self, min_support = 0.01, min_confidence = 0.5):
        self.min_support = min_support         # 最小支持度
        self.min_confidence = min_confidence   #  最小置信度

    def apriori(self, dataset):
        """
        Apriori算法实现
        :param dataset: 数据集，类型为一个list，list中每个元素是一个dict，key为属性名，
                        value为对应属性的取值
        :return: 生成频繁项集
        """
        C1 = self.create_C1(dataset)
        #print(C1)
        dataset = [set(data) for data in dataset]
        #print(dataset)
        L1, support_data = self.scan_D(dataset, C1)
        L = [L1]
        k = 2
        while len(L[k-2]) > 0:
            Ck = self.apriori_gen(L[k-2], k)
            Lk, support_k = self.scan_D(dataset, Ck)
            #print(Lk)
            support_data.update(support_k)
            L.append(Lk)
            k += 1
        return L, support_data

    def create_C1(self, dataset):
        # 扫描dataset，构建全部可能的单元素候选项集合(list)
        # 每个单元素候选项：（属性名，属性取值）
        #print(dataset)
        C1 = []
        for data in dataset:
            for item in data:
                if [item] not in C1:
                    C1.append([item])
        #sorted(C1)
        return [frozenset(item) for item in C1]

    def scan_D(self, dataset, Ck):
        # 过滤函数
        # 根据待选项集Ck的情况，判断数据集D中Ck元素的出现频率
        # 过滤掉低于最小支持度的项集
        Ck_count = dict()
        for data in dataset:
            for cand in Ck:
                if cand.issubset(data):
                    if cand not in Ck_count:
                        Ck_count[cand] = 1
                    else:
                        Ck_count[cand] += 1

        num_items = float(len(dataset))
        return_list = []
        support_data = dict()
        # 过滤非频繁项集
        for key in Ck_count:
            support  = Ck_count[key] / num_items
            if support >= self.min_support:
                return_list.insert(0, key)
                support_data[key] = support
        #print(support_data)
        return return_list, support_data

    def apriori_gen(self, Lk, k):
        # 当待选项集不是单个元素时， 如k>=2的情况下，合并元素时容易出现重复
        # 因此针对包含k个元素的频繁项集，对比每个频繁项集第k-2位是否一致
        return_list = []
        len_Lk = len(Lk)

        for i in range(len_Lk):
            for j in range(i+1, len_Lk):
                # 第k-2个项相同时，将两个集合合并
                L1 = list(Lk[i])[:k-2]
                L2 = list(Lk[j])[:k-2]
                L1.sort()
                L2.sort()
                if L1 == L2:
                    return_list.append(Lk[i] | Lk[j])
        return return_list

    def generate_rules(self, L, support_data):

        big_rules_list = []
        for i in range(1, len(L)):
            for freq_set in L[i]:
                H1 = [frozenset([item]) for item in freq_set]
                # 只获取有两个或更多元素的集合
                if i > 1:
                    self.rules_from_conseq(freq_set, H1, support_data, big_rules_list)
                else:
                    self.cal_conf(freq_set, H1, support_data, big_rules_list)
        return big_rules_list

    def rules_from_conseq(self, freq_set, H, support_data, big_rules_list):
        # H->出现在规则右部的元素列表
        m = len(H[0])
        if len(freq_set) > (m+1):
            Hmp1 = self.apriori_gen(H, m+1)
            Hmp1 = self.cal_conf(freq_set, Hmp1, support_data, big_rules_list)
            if len(Hmp1) > 1:
                self.rules_from_conseq(freq_set, Hmp1, support_data, big_rules_list)

    def cal_conf(self, freq_set, H, support_data, big_rules_list):
        # 评估生成的规则
        prunedH = []
        #print(freq_set)
        #print(freq_set - H[0])
        for conseq in H:
            #print(conseq)
            #print('freq_set - conseq'+freq_set - conseq)
            sup = support_data[freq_set]
            conf = sup / support_data[freq_set - conseq]
            lift = conf / support_data[conseq]
            cosine = sup / math.sqrt(support_data[freq_set - conseq]*support_data[conseq])
            if conf >= self.min_confidence:
                big_rules_list.append((freq_set-conseq, conseq, sup, conf, lift,cosine))
                prunedH.append(conseq)
        return prunedH