发表更新数据挖掘10 分钟读完 (大约1556个字)

数据挖掘AP算法

00 算法简介

先验性质:频繁项集的所有非空子集也一定是频繁的

步骤:小项拼大项;剪枝(剪大项 & 剪小项)

01 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
初始数据集示例:
dataset:[('asian foods', 'breakfast bakery', 'buns rolls'), ('baby food formula', 'bread'), ('bread', 'breakfast bakery', 'buns rolls'), ('breakfast bars pastries', 'buns rolls'), ('bread', 'buns rolls'), ...]

#####################  第一次扫描与剪枝  #####################

# 扫描
dataset_dict = {}
for data in dataset:
    for item in data:
        统计每一项出现的次数,并记录在dataset_dict中
        同时需要统计总项数,等会计算支持度要用
	end-for
end-for

# 剪枝
del_items = [] # 用来存放不满足最低支持度的项集
for item in dataset_dict:
    if item的数量 / 总项数 < MIN_SUP: # 如果支持度不够，就把元素放到要删除的列表中
        del_items.append(item)
    end-if
end-for
for item in del_items: # 删除支持度不够的项
    del 支持度不够的项
end-for

#####################  拼接与剪枝  #####################

# 拼接(不仅存在一项拼两项,还有可能是两项拼三项、三项拼四项等，因此要考虑兼容性)
dataset_list_generated = [] # 用来存放剪枝后的结果
for key_i, value_i in dataset_dict.items():
    for key_j, value_j in dataset_dict.items():
        if key_i != key_j:
        	除了自己和自己拼接之外,其他可能的所有连接都会被拼接上
        	然后需要进行去重,这里的去重有两重含义:
        	1. 去除拼接的(key_i, key_j)和(key_j, key_i)的重复
        	2. 去除key_i和key_j中重复的项
            list_temp = list(set(key_i + key_j)) # 使用set的特性去除key_i和key_j中重复的项
            # 排序,为了后续方便去除拼接的(key_i, key_j)和(key_j, key_i)的重复
            sort(list_temp) 
            # 把当前拼接结果转为元组判断是否已经在生成的结果中,
            # 同时要求满足当前拼接结果长度仅比key_i或者key_j长1(也就是key_i和key_j只有一个项不一样)
            if tuple(list_temp) not in dataset_list_generated and len(list_temp) == len(key_i) + 1:
                把list_temp放到生成的dataset_list
            end-if
        end-if
    end-for
end-for

# 用来存放不满足最低支持度的项集
del_items = []

# 剪枝(注意剪枝中,除了看其本身的支持度是否达到,也要看组成该大项的小项是否频繁)
dataset_dict = {}
# 统计支持度个数
for item in 当前要剪枝的数据集:
    for dataset_item in 初始数据集:
    	if 初始数据集中包含当前数据集中的项:
            对当前数据集的项进行计数
        end-if
    end-for
end-for

for item in 当前要剪枝的数据集的项:
    if 当前项支持度 < MIN_SUP:
        del_items.append(item) # 把元素放到要删除的列表中
    end-if
    
    # 当有拼接出三项以及三项以上的时候,需要进行这一项剪枝
    if len(item) > 2:
        for deleteItem in 已经确定不满足最小支持度的列表:
	        if 不满足最小支持度的项出现在当前 item 中
                del_items.append(item) # 那么就删除这一项 item
                break
            end-if
        end-for
    end-if
end-for

# 批量删除支持度不够的项
for item in 要删除的项:
    if 要删除的项 in 当前要剪枝的数据集中:
        del dataset_dict[item] # 删除该项
	end-if
end-for

02 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import csv

# 待挖掘的数据集
dataset_list = []
# 最小支持度
# 最小支持度
dataset_length = 0
# 最小支持度
MIN_SUP = 0.02
# 最小置信度
MIN_CON = 0.2


# 加载数据集
def load_dataset_list():
    with open("orders.csv", "r") as dataset:
        reader = csv.reader(dataset)
        rows = [row for row in reader]

        for row_index, row in enumerate(rows):
            order_data = []
            # 忽略第一行数据
            if row_index > 0:
                for data_index, data in enumerate(row):
                    # 忽略第一列的订单 id 数据；如果不为 0，就说明该订单购买了该商品
                    if data != "0" and data_index > 0:
                        order_data.append(rows[0][data_index])
            # 挖掘的是关联性，因此只买一件商品的订单不需要统计
            if len(order_data) > 1:
                dataset_list.append(tuple(order_data))


# 第一次扫描和剪枝
def scan_pruning_first(dataset):
    dataset_dict = {}
    for data in dataset:
        for item in data:
            item_tuple = (item,)
            if item_tuple in dataset_dict:
                dataset_dict[item_tuple] += 1
            else:
                dataset_dict[item_tuple] = 1

    # 用来存放不满足最低支持度的项集
    del_items = []
    for item in dataset_dict:
        # 如果支持度不够，就把元素放到要删除的列表中
        if dataset_dict.get(item) / dataset_length < MIN_SUP:
            del_items.append(item)
    # 批量删除支持度不够的项
    for item in del_items:
        del dataset_dict[item]
    return dataset_dict


# 连接
def self_connection(dataset_dict):
    dataset_list_generated = []
    for key_i, value_i in dataset_dict.items():
        for key_j, value_j in dataset_dict.items():
            if key_i != key_j:
                list_temp = list(set(key_i + key_j))
                # 这里需要进行排序，否则下面判断有无重复的时候无法判断顺序不一样
                list_temp.sort()
                if tuple(list_temp) not in dataset_list_generated and len(list_temp) == len(key_i) + 1:
                    dataset_list_generated.append(tuple(list_temp))
    return dataset_list_generated


# 用来存放不满足最低支持度的项集
del_items = []


# 剪枝
def pruning_item(dataset):
    dataset_dict = {}
    # 统计支持度个数
    for item in dataset:
        for dataset_item in dataset_list:
            if len(set(item + dataset_item)) == len(dataset_item):
                if tuple(item) in dataset_dict:
                    dataset_dict[tuple(item)] += 1
                else:
                    dataset_dict[tuple(item)] = 1

    for item in dataset_dict:
        # 如果支持度不够，就把元素放到要删除的列表中
        if dataset_dict.get(item) / dataset_length < MIN_SUP:
            del_items.append(item)

        # 只有拼接出三项以及三项以上的时候,才需要进行这一项剪枝
        if len(item) > 2:
            # 如果有不满足最小支持度的项出现在 item 中,那么就删除这一项 item
            for deleteItem in del_items:
                if len(set(deleteItem + item)) == len(item):
                    # 判断 item 中有没有支持度不够的小项,有的话就删除这个 item
                    del_items.append(item)
                    break

    # 批量删除支持度不够的项
    for item in del_items:
        if item in dataset_dict:
            del dataset_dict[item]
    return dataset_dict

# 递归调用连接和剪枝,直到满足要求
def connectAndPruning(item_dict):
    # 连接
    dataset_connected = self_connection(item_dict)
    # 剪枝
    dataset_pruning = pruning_item(dataset_connected)

    if len(dataset_pruning) > 1:
        return connectAndPruning(dataset_pruning)
    else:
        return dataset_pruning


if __name__ == '__main__':
    # 加载数据集
    load_dataset_list()
    dataset_length = len(dataset_list)
    # 第一次扫描和剪枝
    item_dict = scan_pruning_first(dataset_list)
    result = connectAndPruning(item_dict)
    print([key for key, value in result.items()][0])

03 代码运行结果

1
2
3
4
C:\anaconda\envs\Apriori\python.exe C:/Users/Sheng/PycharmProjects/Apriori/main.py
('baking ingredients', 'bread', 'breakfast bakery')

Process finished with exit code 0
#

喜欢这篇文章？打赏一下作者吧

评论

最新文章

标签

ADB1
Ajax1
Apriori1
Bootstrap2
C++4
C语言1
Docker2
FRP1
FTP2
Git3
GitHub1
Gitee1
IDEA1
JSP3
Java16
K-Means1
Linux9
MariaDB1
Maven1
MySQL5
Navicat1
Nginx6
Node.js1
OAuth21
Office1
PHP1
PaddlePaddle1
PyTorch1
Python5
Radis1
SpEL1
Spring1
Tomcat2
UML2
Vue8
Windows2
conda1
gcc1
gpio1
iPhone1
jQuery11
pi4j1
ss1
人工智能6
其他学科4
决策树1
前端24
安卓2
广工2
微信小程序4
微表情识别1
排序算法1
数据挖掘3
数据结构4
旁路由1
树莓派9
私人网盘2
线性代数1
网易云音乐1
计算机网络1
计量经济学2
金融学1
飞浆1

分类

关注我

目录

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×