实验四 Apriori / k-Means算法实现_apriori 算法实验目的

一、实验目的

1、掌握Apriori/k-Means算法。

2、掌握关联或分类的方法。

3、掌握C/C++、python等的用法。

二、实验内容

我们进行交易的数据项见下表所示，预定义最小支持度minsupport=2。

此实验为综合型实验，要求学生综合利用先修课程高级程序设计语言、数据库、算法设计与分析，与本门数据挖掘课程的知识，选择一种编程工具，实现经典挖掘算法Apriori算法和k-Means。

三、实验原理

Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。

该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递归的方法。

但其有一些难以克服的缺点：

（1）对数据库的扫描次数过多。

（2）Apriori算法会产生大量的中间项集。

（3）采用唯一支持度。

（4）算法的适应面窄。

Kmeans

先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：

1)没有（或最小数目）对象被重新分配给不同的聚类。

2)没有（或最小数目）聚类中心再发生变化。

3)误差平方和局部最小。

伪代码

选择k个点作为初始质心。

repeat 将每个点指派到最近的质心，形成k个簇 重新计算每个簇的质心 until 质心不发生变化

实验代码

Dashuju4.py

1.min_sup = 2
2.min_conf = 0.6
3.# 最大 K 项集
4.K = 3
5.
6.def apriori():
7.    data_set = load_data()
8.    C1 = create_C1(data_set)
9.    item_count = count_itemset1(data_set, C1)
10.    L1 = generate_L1(item_count)
11.    Lk_copy = L1.copy()
12.    L = []
13.    L.append(Lk_copy)
14.    for i in range(2, K + 1):
15.        Ci = create_Ck(Lk_copy, i)
16.        Li = generate_Lk_by_Ck(Ci, data_set)
17.        Lk_copy = Li.copy()
18.        L.append(Lk_copy)
19.
20.    print('频繁项集\t支持度计数')
21.    support_data = {}
22.    for item in L:
23.        for i in item:
24.            print(list(i), '\t', item[i])
25.            support_data[i] = item[i]
26.
27.    strong_rules_list = generate_strong_rules(L, support_data, data_set)
28.    strong_rules_list.sort(key=lambda result: result[2], reverse=True)
29.    print("\nStrong association rule\nX\t\t\tY\t\tconf")
30.    for item in strong_rules_list:
31.        print(list(item[0]), "\t", list(item[1]), "\t", item[2])
32.
33.
34.
35.def load_data():
36.
37.    data = {'001': 'I1,I3,I4', '002': 'I2,I3,I5',
38.            '003': 'I1,I2,I3,I5', '004': 'I2,I5'}
39.    data_set = []
40.    for key in data:
41.        item = data[key].split(',')
42.        data_set.append(item)
43.    return data_set
44.
45.
46.def create_C1(data_set):
47.    C1 = set()
48.    for t in data_set:
49.        for item in t:
50.            item_set = frozenset([item])
51.            C1.add(item_set)
52.    return C1
53.
54.
55.def count_itemset1(data_set, C1):
56.    item_count = {}
57.    for data in data_set:
58.        for item in C1:
59.            if item.issubset(data):
60.                if item in item_count:
61.                    item_count[item] += 1
62.                else:
63.                    item_count[item] = 1
64.    return item_count
65.
66.
67.def generate_L1(item_count):
68.    L1 = {}
69.    for i in item_count:
70.        if item_count[i] >= min_sup:
71.            L1[i] = item_count[i]
72.    return L1
73.
74.
75.def is_apriori(Ck_item, Lk_copy):
76.    for item in Ck_item:
77.        sub_Ck = Ck_item - frozenset([item])
78.        if sub_Ck not in Lk_copy:
79.            return False
80.    return True
81.
82.
83.def create_Ck(Lk_copy, k):
84.    Ck = set()
85.    len_Lk_copy = len(Lk_copy)
86.    list_Lk_copy = list(Lk_copy)
87.    for i in range(len_Lk_copy):
88.        for j in range(1, len_Lk_copy):
89.            l1 = list(list_Lk_copy[i])
90.            l2 = list(list_Lk_copy[j])
91.            l1.sort()
92.            l2.sort()
93.            if l1[0:k-2] == l2[0:k-2]:
94.                Ck_item = list_Lk_copy[i] | list_Lk_copy[j]
95.                if is_apriori(Ck_item, Lk_copy):
96.                    Ck.add(Ck_item)
97.    return Ck
98.
99.
100.def generate_Lk_by_Ck(Ck, data_set):
101.    item_count = {}
102.    for data in data_set:
103.        for item in Ck:
104.            if item.issubset(data):
105.                if item in item_count:
106.                    item_count[item] += 1
107.                else:
108.                    item_count[item] = 1
109.    Lk2 = {}
110.    for i in item_count:
111.        if item_count[i] >= min_sup:
112.            Lk2[i] = item_count[i]
113.    return Lk2
114.
115.
116.def generate_strong_rules(L, support_data, data_set):
117.    strong_rule_list = []
118.    sub_set_list = []
119.    # print(L)
120.    for i in range(0, len(L)):
121.        for freq_set in L[i]:
122.            for sub_set in sub_set_list:
123.                if sub_set.issubset(freq_set):
124.                    # 计算包含 X 的交易数
125.                    sub_set_num = 0
126.                    for item in data_set:
127.                        if (freq_set - sub_set).issubset(item):
128.                            sub_set_num += 1
129.                    conf = support_data[freq_set] / sub_set_num
130.                    strong_rule = (freq_set - sub_set, sub_set, conf)
131.                    if conf >= min_conf and strong_rule not in strong_rule_list:
132.                        # print(list(freq_set-sub_set), " => ", list(sub_set), "conf: ", conf)
133.                        strong_rule_list.append(strong_rule)
134.            sub_set_list.append(freq_set)
135.    return strong_rule_list
136.
137.
138.if __name__ == '__main__':
139.    apriori()

可视化代码

1.# coding=utf-8
2.min_sup = 2
3.min_conf = 0.6
4.# 最大 K 项集
5.K = 3
6.import matplotlib.pyplot as plt
7.import numpy as np
8.def apriori():
9.    data_set = load_data()
10.    C1 = create_C1(data_set)
11.    item_count = count_itemset1(data_set, C1)
12.    L1 = generate_L1(item_count)
13.    Lk_copy = L1.copy()
14.    L = []
15.    L.append(Lk_copy)
16.    for i in range(2, K + 1):
17.        Ci = create_Ck(Lk_copy, i)
18.        Li = generate_Lk_by_Ck(Ci, data_set)
19.        Lk_copy = Li.copy()
20.        L.append(Lk_copy)
21.
22.    print('频繁项集\t支持度计数')
23.    a = [[],[]]
24.    z = [[],[],[]]
25.    cla = []
26.    support_data = {}
27.    for item in L:
28.        for i in item:
29.            print(list(i), '\t', item[i])
30.            a[0].append(str(list(i)))
31.            a[1].append(str(item[i]))
32.            support_data[i] = item[i]
33.            cla.append(str(i))
34.    strong_rules_list = generate_strong_rules(L, support_data, data_set)
35.    strong_rules_list.sort(key=lambda result: result[2], reverse=True)
36.    print("\nStrong association rule\nX\t\t\tY\t\tconf")
37.    print([0])
38.    for item in strong_rules_list:
39.        print(list(item[0]), "\t", list(item[1]), "\t", item[2])
40.    # 设置x/y轴尺度
41.
42.    plt.ylim(0,4)
43.    for i in range(len(a[0])):
44.        plt.bar(a[0][i], int(a[1][i]), label=cla[i], width=1)
45.
46.    plt.legend()
47.    plt.xlabel('number')
48.    plt.ylabel('value')
49.
50.    plt.title("Frequent itemsets, support count")
51.
52.    plt.show()
53.    for item in strong_rules_list:
54.        print(list(item[0]), "\t", list(item[1]), "\t", item[2])
55.        z[0].append(str(list(item[0])))
56.        z[1].append(str(list(item[1])))
57.        z[2].append(item[2])
58.    # 表示随机生成一个标准正态分布形状是600*2的数组
59.    plt.figure(figsize=(8, 5))  # 表示绘制图形的画板尺寸为8*5
60.
61.    # 表示随机生成一个第三维度的数据集，取值在0-10之间的整数
62.    plt.scatter(z[0], z[1], c=z[2], marker='o')  # 表示颜色数据来源于第三维度的c
63.    plt.colorbar()
64.    plt.show()
65.
66.def load_data():
67.
68.    data = {'001': 'I1,I3,I4', '002': 'I2,I3,I5',
69.            '003': 'I1,I2,I3,I5', '004': 'I2,I5'}
70.    data_set = []
71.    for key in data:
72.        item = data[key].split(',')
73.        data_set.append(item)
74.    return data_set
75.
76.
77.def create_C1(data_set):
78.    C1 = set()
79.    for t in data_set:
80.        for item in t:
81.            item_set = frozenset([item])
82.            C1.add(item_set)
83.    return C1
84.
85.
86.def count_itemset1(data_set, C1):
87.    item_count = {}
88.    for data in data_set:
89.        for item in C1:
90.            if item.issubset(data):
91.                if item in item_count:
92.                    item_count[item] += 1
93.                else:
94.                    item_count[item] = 1
95.    return item_count
96.
97.
98.def generate_L1(item_count):
99.    L1 = {}
100.    for i in item_count:
101.        if item_count[i] >= min_sup:
102.            L1[i] = item_count[i]
103.    return L1
104.
105.
106.def is_apriori(Ck_item, Lk_copy):
107.    for item in Ck_item:
108.        sub_Ck = Ck_item - frozenset([item])
109.        if sub_Ck not in Lk_copy:
110.            return False
111.    return True
112.
113.
114.def create_Ck(Lk_copy, k):
115.    Ck = set()
116.    len_Lk_copy = len(Lk_copy)
117.    list_Lk_copy = list(Lk_copy)
118.    for i in range(len_Lk_copy):
119.        for j in range(1, len_Lk_copy):
120.            l1 = list(list_Lk_copy[i])
121.            l2 = list(list_Lk_copy[j])
122.            l1.sort()
123.            l2.sort()
124.            if l1[0:k-2] == l2[0:k-2]:
125.                Ck_item = list_Lk_copy[i] | list_Lk_copy[j]
126.                if is_apriori(Ck_item, Lk_copy):
127.                    Ck.add(Ck_item)
128.    return Ck
129.
130.
131.def generate_Lk_by_Ck(Ck, data_set):
132.    item_count = {}
133.    for data in data_set:
134.        for item in Ck:
135.            if item.issubset(data):
136.                if item in item_count:
137.                    item_count[item] += 1
138.                else:
139.                    item_count[item] = 1
140.    Lk2 = {}
141.    for i in item_count:
142.        if item_count[i] >= min_sup:
143.            Lk2[i] = item_count[i]
144.    return Lk2
145.
146.
147.def generate_strong_rules(L, support_data, data_set):
148.    strong_rule_list = []
149.    sub_set_list = []
150.    # print(L)
151.    for i in range(0, len(L)):
152.        for freq_set in L[i]:
153.            for sub_set in sub_set_list:
154.                if sub_set.issubset(freq_set):
155.                    # 计算包含 X 的交易数
156.                    sub_set_num = 0
157.                    for item in data_set:
158.                        if (freq_set - sub_set).issubset(item):
159.                            sub_set_num += 1
160.                    conf = support_data[freq_set] / sub_set_num
161.                    strong_rule = (freq_set - sub_set, sub_set, conf)
162.                    if conf >= min_conf and strong_rule not in strong_rule_list:
163.                        # print(list(freq_set-sub_set), " => ", list(sub_set), "conf: ", conf)
164.                        strong_rule_list.append(strong_rule)
165.            sub_set_list.append(freq_set)
166.    return strong_rule_list
167.
168.
169.if __name__ == '__main__':
170.    apriori()

kmeans 分类

1.import random
2.import pandas as pd
3.import numpy as np
4.import matplotlib.pyplot as plt
5.
6.
7.# 计算欧拉距离
8.def calcDis(dataSet, centroids, k):
9.    clalist = []
10.    for data in dataSet:
11.        diff = np.tile(data, (k,
12.                              1)) - centroids  # 相减   (np.tile(a,(2,1))就是把a先沿x轴复制1倍，即没有复制，仍然是 [0,1,2]。 再把结果沿y方向复制2倍得到array([[0,1,2],[0,1,2]]))
13.        squaredDiff = diff ** 2  # 平方
14.        squaredDist = np.sum(squaredDiff, axis=1)  # 和  (axis=1表示行)
15.        distance = squaredDist ** 0.5  # 开根号
16.        clalist.append(distance)
17.    clalist = np.array(clalist)  # 返回一个每个点到质点的距离len(dateSet)*k的数组
18.    return clalist
19.
20.
21.# 计算质心
22.def classify(dataSet, centroids, k):
23.    # 计算样本到质心的距离
24.    clalist = calcDis(dataSet, centroids, k)
25.    # 分组并计算新的质心
26.    minDistIndices = np.argmin(clalist, axis=1)  # axis=1 表示求出每行的最小值的下标
27.    newCentroids = pd.DataFrame(dataSet).groupby(
28.        minDistIndices).mean()  # DataFramte(dataSet)对DataSet分组，groupby(min)按照min进行统计分类，mean()对分类结果求均值
29.    newCentroids = newCentroids.values
30.
31.    # 计算变化量
32.    changed = newCentroids - centroids
33.
34.    return changed, newCentroids
35.
36.
37.# 使用k-means分类
38.def kmeans(dataSet, k):
39.    # 随机取质心
40.    centroids = random.sample(dataSet, k)
41.
42.    # 更新质心 直到变化量全为0
43.    changed, newCentroids = classify(dataSet, centroids, k)
44.    while np.any(changed != 0):
45.        changed, newCentroids = classify(dataSet, newCentroids, k)
46.
47.    centroids = sorted(newCentroids.tolist())  # tolist()将矩阵转换成列表 sorted()排序
48.
49.    # 根据质心计算每个集群
50.    cluster = []
51.    clalist = calcDis(dataSet, centroids, k)  # 调用欧拉距离
52.    minDistIndices = np.argmin(clalist, axis=1)
53.    for i in range(k):
54.        cluster.append([])
55.    for i, j in enumerate(minDistIndices):  # enymerate()可同时遍历索引和遍历元素
56.        cluster[j].append(dataSet[i])
57.
58.    return centroids, cluster
59.
60.
61.# 创建数据集
62.def createDataSet():
63.    return [[1, 1], [1, 2], [2, 2], [1, 3], [3, 3], [4, 2], [5, 3], [6, 3], [6, 2], [6, 4], [7, 1], [2, 5], [3, 6], [6, 7]]
64.
65.
66.if __name__ == '__main__':
67.    dataset = createDataSet()
68.    centroids, cluster = kmeans(dataset, 2)
69.    print('质心为：%s' % centroids)
70.    print('集群为：%s' % cluster)
71.    for i in range(len(dataset)):
72.        for j in range(len(centroids)):
73.            plt.scatter(centroids[j][0], centroids[j][1], marker='x', color='red', s=50, label='质心')
74.    for i in range(len(cluster[0])):
75.        plt.scatter(cluster[0][i][0], cluster[0][i][1], marker='o', color='yellow', s=40, label='shenzu')
76.    for j in range(len(cluster[1])):
77.        plt.scatter(cluster[1][j][0], cluster[1][j][1], marker='o', color='blue', s=40, label='qizu')
78.    plt.show()

 运行结果图：