本案例提供一份有关青少年爱好与生活习惯的数据集 主要收集年轻人的爱好和生活习惯 方面的信息. 问卷调查数据集的总体情况如下:
- 该问卷调查的数据集共涉及1010份的150项问题的调查
- columns.csv 文件中记录了这 150 项问题的详细描述
- 数据集中包含缺失值,即被调查者未填写的项目
- 数据集中既有数值型数据又有字符型数据
- 数值型数据代表认同程度从 1 到 5 程度逐渐增加
对于150 项的调查内容, 可以分为若干类别: 音乐喜好、电影喜好、爱好和兴趣、厌恶、卫生习惯、个性特点, 人生观、消费习惯和个人基本信息。
本案例结合调查问卷数据集, 从零开始，实现关联规则领域的经典算法FPGrowth，找出数据集中隐藏的关联规则。
FP-Growth的数据结构¶
我们构造两个在算法实现中需要用到的数据结构，Node和FPTree。
Node
Node类表示的是树中的节点，保存节点的子节点(children)，父节点(parent)，以及节点代表的元素(value)出现的频数(count)等信息。
FPTree
FPTree表示的是FP树，它将数据集以树形结构进行存储，根节点为null，其余节点代表数据集中的一个频繁项和它的支持度信息。由于不同的频繁项会有重合的部分，在FP树结构中存储的数据就可以共享相同的路径，达到压缩数据的效果。
In [1]:
'''
Node类,包含以下变量：
name： 当前节点代表的频繁项
count：当前节点出现的频数
link：FP树的其他路径中代表相同频繁项的节点
parent：当前节点的父节点
children：当前节点的子节点
包含以下方法：
__init__()： 构造方法
increment()：增加当前节点代表的频繁项的支持度
display()：可视化节点，以及对应的频繁项支持度
'''
class Node:
'''
输入参数：name：节点代表的频繁项
count：频繁项的支持度
parent：节点的父节点
'''
def __init__(self, name, count, parent):
self.name = name
self.count = count
self.link = None
self.parent = parent
self.children = {}
'''
输入参数： num：整数，代表频繁项支持度增加的数值
'''
def increment(self, num):
self.count += num
'''
输入参数：lens：节点的初始支持度
'''
def display(self, lens = 1):
print ' '*lens, self.name, ' ', self.count
for child in self.children.values():
child.display(lens + 1)
然后，我们实现FPTRee类，它也是频繁树增长算法的核心数据结构。
In [2]:
'''
FPTree类,包含以下变量：
flag：表示构建FPTree还是条件FPTree，取决于输入数据
root： FP树的根节点
data：FP树代表的数据集
data_type：数据集存储的原始类型（字典或者嵌套列表）
min_support：最小支持度（绝对）
frequent：频繁1项集集合
headerTable：FP树对应的频繁项表
包含以下方法：
__init__()： 构造方法
find_frequent_items()：根据数据集生成频繁1项集集合
build_tree()：将数据集中的每条数据记录插入FP树种，也就是建树过程
get_tree()：返回树的根节点
get_frequent_items()：返回频繁1项集集合
get_headertable()：返回频繁项表
get_data()：返回数据集
show()：可视化FP树的结构
'''
class FPTree:
'''
输入参数：transactions：数据集
min_support：最小支持度
root_value：根节点代表的频繁项
count：根节点代表的频繁项的支持度
'''
def __init__(self, transactions, min_support, root_value, count, flag):
self.flag = flag
self.root = Node(root_value, count, None)
self.data = transactions
self.data_type = type(self.data)
self.min_support = min_support
self.frequent = self.find_frequent_items()
self.headerTable = {v:[self.frequent[v], None] for v in self.frequent}
'''
返回参数：以字典格式存储的频繁1项集集合
'''
def find_frequent_items(self):
from collections import defaultdict
freq1 = defaultdict(int)
#统计列表中各个元素的出现频次
if self.data_type == list and self.flag == 'fptree':
flatten_list = [element for item in self.data for element in item]
for value in flatten_list:
freq1[frozenset([value])] += 1
# 条件FP树
elif self.data_type == dict and self.flag == 'cfptree':
for item in self.data:
for element in item:
if type(element) == frozenset:
freq1[element] += self.data[item]
else:
freq1[frozenset([element])] += self.data[item]
# 过滤掉非频繁项
return {v:freq1[v] for v in freq1 if freq1[v] >= self.min_support}
def build_tree(self):
root = Node('null', 1, None)
sorted_headertable = [v[0] for v in sorted(self.frequent.items(), key=lambda kv: (-kv[1], list(kv[0])[0]))]
# 将业务数据库中的每条记录插入树中，更新频繁项表
for record in self.data:
# 找到业务数据纪录中的频繁项
sorted_items = [item for item in sorted_headertable if list(item)[0] in record]
#print u'将排序后的频繁项集放入FP树中: '
#print sorted_items
#print ''
node = self.root
while len(sorted_items) > 0:
first_value = sorted_items[0]
#print u' 开始插入节点 ', first_value
if first_value in node.children:
#print u' 当前节点的子节点中包含节点 ', first_value
if self.data_type == list:
node.children[first_value].increment(1)
elif self.data_type == dict:
node.children[first_value].increment(self.data[record])
else:
# 创建新的子节点
#print u' 创建新节点 ', first_value
if self.data_type == list:
node.children[first_value] = Node(list(first_value)[0], 1, node)
elif self.data_type == dict:
node.children[first_value] = Node(first_value, self.data[record], node)
# 更新频繁项表
if self.headerTable[first_value][1] == None:
#print u' 在频繁项表中，添加对应链表的第一个节点', first_value
self.headerTable[first_value][1] = node.children[first_value]
else:
#print u' 添加到频繁项表对应链表的末尾'
currentNode = self.headerTable[first_value][1]
# 遍历连表，确保在表的尾部插入新的节点指针
while currentNode.link != None:
currentNode = currentNode.link
currentNode.link = node.children[first_value]
#print '***********'
sorted_items.pop(0)
node = node.children[first_value]
#print ''
def get_tree(self):
return self.root
def get_frequent_items(self):
return self.frequent
def get_headertable(self):
return self.headerTable
def get_data(self):
return self.data
def show(self, depth = 1):
print ' '*depth, self.root.name, ' ', self.root.count
for node in self.root.children.values():
node.display(depth + 1)
In [3]:
# 二维列表存储的数据集
data = [
['f', 'a', 'c', 'd', 'g', 'i', 'm', 'p'],
['a','b','c','f','l','m','o'],
['b','f','h','j','o'],
['b','c','k','s','p'],
['a','f','c','e','l','p','m','n']]
data
Out[3]:
与数据集对应的频繁树为：
在测试例子中，我们设置最小支持度为3，然后使用data创建FP树的一个实例对象fptree。
In [4]:
#最小支持度
min_support = 3
#创建实例
fptree = FPTree(data, min_support, 'null', 1, 'fptree')
通过调用get_frequent_items()方法，我们可以查看数据集的频繁1项集。从结果上来看，过滤掉不符合最小支持度条件的项d, e, g, i, k, l, h, n, o, s。
In [5]:
# 频繁1项集集合
freq1 = fptree.get_frequent_items()
freq1
Out[5]:
然后，在建树过程中，我们可以通过build_tree()方法的打印语句来详细考察FP树的建立过程。
In [6]:
fptree.build_tree()
FP树建立完成后，可视化树的结构，可以和之前的图进行对比验证。
In [7]:
fptree.show(1)
挖掘FP树¶
频繁树增长算法将构建的FP树划分为一系列条件模式库。然后，基于每一个条件模式库，递归地构建条件频繁模式树。例如，我们构造以p为后缀的条件模式库，首先根据频繁项表中存储的p的链表结构，回溯所有的路径(cbp, cfamp)；然后，再将路径中除去p的部分作为新的项集，继续构建FP树。
在构建的FP树种，回溯以某个节点为后缀的路径，我们使用函数find_prefix()来实现。
In [8]:
'''
输入参数：Node节点
返回参数：以输入节点为后缀的条件模式库
'''
def find_prefix(node):
#条件模式库
cpb = {}
suffix_list = []
# 判断条件，是否已经达到链表的尾部
while node != None:
suffix_list.append(node)
node = node.link
for item in suffix_list:
path = []
num = item.count
# 判断条件，是否已经回溯到树的顶点
while item.parent != None:
path.append(item.name)
item = item.parent
# 除去当前节点的部分作为条件模式基，并以当前节点的支持度作为条件模式库的支持度
cpb[frozenset(path[1:])] = num
return cpb
接下来，我们构造mine_tree方法，来实现FP树的挖掘过程。
In [9]:
'''
输入参数：frequent_items：数据集的频繁1项集集合
headerTable：数据集的频繁项表
frequent：每次迭代过程生成的频繁项
item_list：存储所有迭代过程生成的的频繁项集
'''
def mine_tree(frequent_items, headerTable, min_support, frequent, item_list):
# 频繁项表中的元素降序排列
candidates = [v[0] for v in sorted(frequent_items.items(), key=lambda kv: (-kv[1], list(kv[0])[0]))]
#print candidates
for item in candidates[::-1]:
#从以下的元素开始
#print 'from the node: ', item
# 针对每个条件模式库，生成频繁项集
freq_set = frequent.copy()
freq_set.add(item)
item_list.append(freq_set)
# 生成条件模式库
cpbs = find_prefix(headerTable[item][1])
#print 'its cpbs: ', cpbs
#创建条件FP树
cTree = FPTree(cpbs, min_support, 'root', 1, 'cfptree')
cTree.build_tree()
#print '-----headerTable: ', cTree.get_headertable()
#判断条件：频繁项表为空
if len(cTree.get_headertable()) != 0:
#print 'condtional tree for: ', freq_set
#cTree.show(1)
mine_tree(cTree.get_frequent_items(), cTree.get_headertable(), min_support, freq_set, item_list)
将构建的FP树实例fptree代入函数mine_tree，返回所有的频繁项集。
In [10]:
#存储所有的频繁项
frequent_item = []
#存储一次迭代过程产生的频繁项
frequent = set()
#FP树的根节点
root_node = fptree.get_tree()
#数据集data的headertable
headertable = fptree.get_headertable()
#数据集data的频繁1项集集合
freq_items = fptree.get_frequent_items()
#挖掘FP树fptree
mine_tree(freq_items, headertable, min_support, frequent, frequent_item)
打印frequent_item的内容，展示所有的频繁项集。
In [11]:
frequent_item
Out[11]:
In [12]:
# 导入处理过程中需要用到的第三方库
from sklearn.preprocessing import Binarizer
import pandas as pd
import numpy as np
使用Pandas库的read_csv()函数读入数据。
In [13]:
real_data = pd.read_csv('./input/responses.csv')
real_data.head()
Out[13]:
In [14]:
# 数据集的大小
real_data.shape
Out[14]:
首先，我们需要了解数据集是否存在缺失值。在这里，我们使isnull()函数来获取boolean矩阵，并分别沿行，列求和，观察缺数据的缺失情况。在Python语言中，对boolean数组求和，如果元素为True，则记为1；反之，则记为0。
In [15]:
# 举例
boo_list = [True, True, False, True]
sum(boo_list)
Out[15]:
利用这样的特性，来获取数据集的缺失值分布信息。
In [16]:
# 数据记录（行）缺失值情况
row_missing = real_data.isnull().sum(axis = 1)
# non_missing_indicator
non_missing_indicator = row_missing == 0
missing_indicator = np.logical_not(non_missing_indicator)
non_missing_index = list(row_missing[non_missing_indicator].index)
In [17]:
print 'number of non missing record: ', len(non_missing_index)
查看含有缺失值的行的索引。
In [18]:
missing_index = list(row_missing[missing_indicator].index)
print missing_index
In [19]:
print 'missing ratio: ', format(float(len(missing_index))/real_data.shape[0], '0.1%')
In [20]:
# 从列的角度来看
col_missing = real_data.isnull().sum()
non_missing_attribute = list(col_missing[col_missing == 0].index)
missing_attribute = list(col_missing[col_missing != 0].index)
print non_missing_attribute
In [21]:
print 'attribute missing ratio: ', format(float(real_data.shape[1] - len(non_missing_attribute))/real_data.shape[1], '0.1%')
在掌握了数据的缺失情况之后，需要考察数据集变量的类型，以及相应的缺失值处理方法。
In [22]:
# 查看data各个变量的类型
real_data.dtypes.value_counts()
Out[22]:
In [23]:
attribute_type = dict(real_data.dtypes)
attribute_type
Out[23]:
在本案例中，我们删除素有含有缺失值的行，保留所有的变量。
In [24]:
new_data = real_data.dropna(axis = 0)
new_data.shape
Out[24]:
为了使用频繁模式算法发现潜在关联的变量，我们需要对变量的取值进行处理，包括离散化，二值化，便于后续的统计。下面，我们针对不同类型的变量，采用不同的处理方法。
对于浮点型变量，我们需要了解各个变量的取值范围。在这里，我们统计各个变量取值的最大值。
In [25]:
float_attribute = [v for v in attribute_type if attribute_type[v] == 'float64']
float_data = new_data[float_attribute].max()
float_data.value_counts()
Out[25]:
In [26]:
float_data[float_data != 5.0]
Out[26]:
对于一般的浮点型变量(最大值为5.0)来说，我们可以直接进行二值化，阈值为3。
In [27]:
#130个普通浮点型变量
personal_attribute = ['Height', 'Age', 'Weight', 'Number of siblings']
float_attribute = [v for v in attribute_type if attribute_type[v] == 'float64' and v not in personal_attribute]
print float_attribute
In [28]:
# 方法1
binary_float_attr = new_data[float_attribute].applymap(lambda x: 1 if x > 3.0 else 0)
binary_float_attr.head()
Out[28]:
In [29]:
# 方法1
binary_float_attr = new_data[float_attribute].applymap(lambda x: 1 if x > 3.0 else 0)
binary_float_attr.head()
Out[29]:
In [30]:
# 方法2
bianry_float_attr1 = Binarizer(threshold=3).transform(new_data[float_attribute])
bianry_float_attr1
Out[30]:
对于personal_attribute存储的浮点型变量来说，需要先进行变量离散化，然后进行特征编码。
In [31]:
new_data[['Age','Height', 'Weight', 'Number of siblings']].describe()
Out[31]:
In [32]:
# Age变量
#阈值
level = 20
binary_age_attr = new_data[['Age']].applymap(lambda x: 1 if x >=20 else 0)
binary_age_attr.columns = ['Age_older_than_20']
binary_age_attr.head()
Out[32]:
In [33]:
# Height变量
#划定三个子区间
binary_height_attr = pd.get_dummies(pd.qcut(new_data['Height'], 3), prefix='Height_')
binary_height_attr.head()
Out[33]:
In [34]:
#Weight变量
#划定四个子区间
binary_weight_attr = pd.get_dummies(pd.qcut(new_data['Weight'], 4), prefix='Weight_')
binary_weight_attr.head()
Out[34]:
In [35]:
#Number of Siblings变量
#划定2个子区间
binary_sibling_attr = new_data[['Number of siblings']].applymap(lambda x: 1 if x > 3.0 else 0)
binary_sibling_attr.columns = ['Number of siblings_larger_than_3']
binary_sibling_attr.head()
Out[35]:
In [36]:
# 字符型变量
str_attribute = [v for v in attribute_type if attribute_type[v] == 'object']
print str_attribute
我们可以查看字符型变量的取值，然后使用Pandas库的get_dummies()函数进行特征编码。
In [37]:
# 查看各个字符型变量的取值
value_list = []
for item in str_attribute:
index = list(new_data[item].value_counts(dropna=False).index)
value_list.append(index)
print index
print ''
In [38]:
# 特征编码
binary_str_attr = pd.get_dummies(new_data[str_attribute])
binary_str_attr.head()
Out[38]:
In [39]:
# 整型变量
int_attribute = [v for v in attribute_type if attribute_type[v] == 'int64']
print int_attribute
对于整型变量来说，我们选取阈值为3，进行二值化。
In [40]:
binary_int_attr = new_data[int_attribute].applymap(lambda x: 1 if x > 3 else 0)
binary_int_attr.columns = ['Eating to survive_very_much',
'Snakes_very_much',
'Number of friends_larger_than_3',
'Dreams_very_much',
'Spending on gadgets_very_much']
binary_int_attr.head()
Out[40]:
使用concat函数把处理后的变量拼接在一起。
In [41]:
final_data = pd.concat([binary_float_attr.reset_index(drop=True),
binary_str_attr.reset_index(drop=True),
binary_int_attr.reset_index(drop=True),
binary_age_attr.reset_index(drop=True),
binary_height_attr.reset_index(drop=True),
binary_weight_attr.reset_index(drop=True),
binary_sibling_attr.reset_index(drop=True)], axis=1)
final_data.head()
Out[41]:
In [42]:
final_data.shape
Out[42]:
原始的real_data经过离散化，二值化等预处理之后，生成新的数据final_data，变量的数量由150增加为177个，取值均为0或者1。
为了便于输入算法，我们把final_data转换为形如示例数据集的嵌套列表格式。
In [43]:
input_data= []
#变量名称
column_name = final_data.columns.values
# 数据集的行数
row = final_data.shape[0]
# 针对每一行数据记录
for index in xrange(row):
name_list = []
# 将对应位置值为1的变量名称加入到name_list中
for item in column_name:
if final_data.ix[index, item] == 1:
name_list.append(item)
else:
continue
# 将每行数据记录转换生成的name_list放入到最终的结果列表中
input_data.append(name_list)
In [44]:
# 展示前2行数据
print input_data[:2]
In [45]:
# 最小支持度
min_support = 400
fptree = FPTree(input_data, min_support, 'null', 1, 'fptree')
In [46]:
# 频繁1项集
frequent1 = fptree.get_frequent_items()
print u'频繁项集集合的数量为：', len(frequent1)
print ''
print frequent1
由于数据集的变量较多，我们暂时把build_tree()和mine_tree()中的打印语句注释掉，方便程序运行和结果展示。
In [47]:
fptree.build_tree()
建树完成后，我们开始挖掘FPtree。从长度为1的频繁模式开始，生成条件模式库。然后以条件模式库为数据集，构造条件FPtree，并生成频繁模式集合。
In [48]:
frequent_item = []
frequent = set()
root_node = fptree.get_tree()
headertable = fptree.get_headertable()
freq_items = fptree.get_frequent_items()
mine_tree(freq_items, headertable, min_support, frequent, frequent_item)
打印输出frequent_item的前10个元素的内容。
In [51]:
for index in range(10):
print frequent_item[index]
从频繁项集中，我们可以了解青少年的生活状态。比如，和朋友在一块儿很开心，喜欢音乐，喜欢喜剧，电影等这些青少年身上的特质经常在一起出现。当然，还有很多其他有趣的信息可以从频繁项集中找到。
参考文献：
- 《机器学习实战》
- FP-Growth算法实现1