大师兄的数据分析学习笔记(二十八）：聚类（四）
大师兄的数据分析学习笔记(三十）：半监督学习
一、关联规则
- 关联规则反应一个事物与其他事物之间的相互依存性和关联性。
- 几个重要概念：
- 项目：一个字段，对交易来说一般指一次交易中的一个物品，如：尿布。
- 事务：某个客户在一次交易中，发生的所有项目的集合，如：尿布、啤酒。
- 项集：包含一次事务中的若干个项目的集合。
- 频繁项集：某个相集的支持度大于阈值，则称为频繁项集。
- 频繁项集中的几个概念：
- 支持度Support：相集{X,Y}在总项集中出现的概率。
- 置信度Condifence：在先决条件X发生的条件下，由关联规则{X->Y}退出Y的概率。
- 提升度：表示含有X的条件下同时含有Y的概率，与无论含不含X含有Y的概率之比。(Confidence({X}->{Y})/Support({Y}))。
- 关联规则的目的，就是找到数据中的频繁项集。
1. Apriori算法
- Apriorio算法是关联规则中的常用算法，思路如下：
- 首先指定一个支持度的阈值，
- 用阈值将频繁项集分出来，比如下图中深色的部分为频繁项集：
- 图中的数字表示项集中项目的个数。
- 其中频繁项集的组合不一定是频繁项集，因为项集组合取的是两个频繁项集的交集，结果要看交集的结果是否大于阈值。
- 同理，两个非频繁项集的组合一定是非频繁项集。
- 而频繁项集和非频繁项集的组合也一定是非频繁项集。
- 在经过若干组合后，只需要输出频繁项集即可。
二、序列规则
- 序列规则将时间因素考虑进来，剔除关联规则中时间点靠后的项目对时间点靠前的项的支持。
1. Apriori-All算法
- Apriori-All算法通常分为两步：
Forward：Apriori算法过程。
Backward：去掉时间序列之后的项对之前的项的支持。
三、代码实现
>>>from itertools import combinations
>>>def comb(lst):
>>> ret = []
>>> for i in range(1, len(lst) + 1):
>>> ret += list(combinations(lst, i))
>>> return ret
>>>class AprLayer(object):
>>> d = {}
>>> def __init__(self):
>>> self.d = {}
>>>class AprNode(object):
>>> def __init__(self, node):
>>> self.s = set(node)
>>> self.size = len(self.s)
>>> self.lnk_nodes = {}
>>> self.num = 0
>>> def __hash__(self):
>>> return hash("__".join(sorted([str(itm) for itm in list(self.s)])))
>>> def __eq__(self, other):
>>> return "__".join(sorted([str(itm) for itm in list(self.s)])) == "__".join(
>>> sorted([str(itm) for itm in list(other.s)]))
>>> def isSubnode(self, node):
>>> return self.s.issubset(node.s)
>>> def incNum(self, num=1):
>>> self.num += num
>>> def addLnk(self, node):
>>> self.lnk_nodes[node] = node.s
>>>class AprBlk():
>>> def __init__(self, data):
>>> cnt = 0
>>> self.apr_layers = {}
>>> self.data_num = len(data)
>>> for datum in data:
>>> cnt += 1
>>> datum = comb(datum)
>>> nodes = [AprNode(da) for da in datum]
>>> for node in nodes:
>>> if not node.size in self.apr_layers:
>>> self.apr_layers[node.size] = AprLayer()
>>> if not node in self.apr_layers[node.size].d:
>>> self.apr_layers[node.size].d[node] = node
>>> self.apr_layers[node.size].d[node].incNum()
>>> for node in nodes:
>>> if node.size == 1: continue
>>> for sn in node.s:
>>> sub_n = AprNode(node.s - set([sn]))
>>> self.apr_layers[node.size - 1].d[sub_n].addLnk(node)
>>> def getFreqItems(self, thd=1, hd=1):
>>> freq_items = []
>>> for layer in self.apr_layers:
>>> for node in self.apr_layers[layer].d:
>>> if self.apr_layers[layer].d[node].num < thd: continue
>>> freq_items.append((self.apr_layers[layer].d[node].s, self.apr_layers[layer].d[node].num))
>>> freq_items.sort(key=lambda x: x[1], reverse=True)
>>> return freq_items[:hd]
>>> def getConf(self, low=True, h_thd=10, l_thd=1, hd=1):
>>> confidence = []
>>> for layer in self.apr_layers:
>>> for node in self.apr_layers[layer].d:
>>> if self.apr_layers[layer].d[node].num < h_thd: continue
>>> for lnk_node in node.lnk_nodes:
>>> if lnk_node.num < l_thd: continue
>>> conf = float(lnk_node.num) / float(node.num)
>>> confidence.append([node.s, node.num, lnk_node.s, lnk_node.num, conf])
>>> confidence.sort(key=lambda x: x[4])
>>> if low:
>>> return confidence[:hd]
>>> else:
>>> return confidence[-hd::-1]
>>>class AssctAnaClass():
>>> def fit(self, data):
>>> self.apr_blk = AprBlk(data)
>>> return self
>>> def get_freq(self, thd=1, hd=1):
>>> return self.apr_blk.getFreqItems(thd=thd, hd=hd)
>>> def get_conf_high(self, thd, h_thd=10):
>>> return self.apr_blk.getConf(low=False, h_thd=h_thd, l_thd=thd)
>>> def get_conf_low(self, thd, hd, l_thd=1):
>>> return self.apr_blk.getConf(h_thd=thd, l_thd=-l_thd, hd=hd)
>>>def main():
>>> data = [
>>> ["魔兽世界", "博德之门", "仙剑奇侠传", "反恐精英"],
>>> ["魔兽世界", "博德之门", "最终幻想", "心跳回忆"],
>>> ["博德之门", "最终幻想", "心跳回忆"],
>>> ["最终幻想", "生化危机", "空之轨迹"],
>>> ["魔兽世界", "博德之门", "最终幻想", "心跳回忆"],
>>> ["魔兽世界", "最终幻想", "心跳回忆"],
>>> ]
>>> aac = AssctAnaClass().fit(data)
>>> print(f"Fred", aac.get_freq(thd=2, hd=10))
>>> print(f"Conf", aac.get_conf_high(thd=1, h_thd=3))
>>>if __name__ == '__main__':
>>> main()
Fred [({'最终幻想'}, 5), ({'魔兽世界'}, 4), ({'博德之门'}, 4), ({'心跳回忆'}, 4), ({'心跳回忆', '最终幻想'}, 4), ({'博德之门', '魔兽世界'}, 3), ({'魔兽世界', '最终幻想'}, 3), ({'魔兽世界', '心跳回忆'}, 3), ({'博德之门', '最终幻想'}, 3), ({'博德之门', '心跳回忆'}, 3)]
Conf [[{'博德之门', '心跳回忆'}, 3, {'博德之门', '心跳回忆', '最终幻想'}, 3, 1.0], [{'博德之门', '最终幻想'}, 3, {'博德之门', '心跳回忆', '最终幻想'}, 3, 1.0], [{'魔兽世界', '心跳回忆'}, 3, {'魔兽世界', '心跳回忆', '最终幻想'}, 3, 1.0], [{'魔兽世界', '最终幻想'}, 3, {'魔兽世界', '心跳回忆', '最终幻想'}, 3, 1.0], [{'心跳回忆'}, 4, {'心跳回忆', '最终幻想'}, 4, 1.0], [{'最终幻想'}, 5, {'心跳回忆', '最终幻想'}, 4, 0.8], [{'心跳回忆', '最终幻想'}, 4, {'博德之门', '心跳回忆', '最终幻想'}, 3, 0.75], [{'心跳回忆', '最终幻想'}, 4, {'魔兽世界', '心跳回忆', '最终幻想'}, 3, 0.75], [{'心跳回忆'}, 4, {'博德之门', '心跳回忆'}, 3, 0.75], [{'心跳回忆'}, 4, {'魔兽世界', '心跳回忆'}, 3, 0.75], [{'博德之门'}, 4, {'博德之门', '心跳回忆'}, 3, 0.75], [{'博德之门'}, 4, {'博德之门', '最终幻想'}, 3, 0.75], [{'博德之门'}, 4, {'博德之门', '魔兽世界'}, 3, 0.75], [{'魔兽世界'}, 4, {'魔兽世界', '心跳回忆'}, 3, 0.75], [{'魔兽世界'}, 4, {'魔兽世界', '最终幻想'}, 3, 0.75], [{'魔兽世界'}, 4, {'博德之门', '魔兽世界'}, 3, 0.75], [{'博德之门', '心跳回忆', '最终幻想'}, 3, {'博德之门', '魔兽世界', '心跳回忆', '最终幻想'}, 2, 0.6666666666666666], [{'魔兽世界', '心跳回忆', '最终幻想'}, 3, {'博德之门', '魔兽世界', '心跳回忆', '最终幻想'}, 2, 0.6666666666666666], [{'博德之门', '心跳回忆'}, 3, {'博德之门', '魔兽世界', '心跳回忆'}, 2, 0.6666666666666666], [{'博德之门', '最终幻想'}, 3, {'博德之门', '魔兽世界', '最终幻想'}, 2, 0.6666666666666666], [{'魔兽世界', '心跳回忆'}, 3, {'博德之门', '魔兽世界', '心跳回忆'}, 2, 0.6666666666666666], [{'魔兽世界', '最终幻想'}, 3, {'博德之门', '魔兽世界', '最终幻想'}, 2, 0.6666666666666666], [{'博德之门', '魔兽世界'}, 3, {'博德之门', '魔兽世界', '心跳回忆'}, 2, 0.6666666666666666], [{'博德之门', '魔兽世界'}, 3, {'博德之门', '魔兽世界', '最终幻想'}, 2, 0.6666666666666666], [{'最终幻想'}, 5, {'博德之门', '最终幻想'}, 3, 0.6], [{'最终幻想'}, 5, {'魔兽世界', '最终幻想'}, 3, 0.6], [{'博德之门', '魔兽世界'}, 3, {'博德之门', '魔兽世界', '反恐精英'}, 1, 0.3333333333333333], [{'博德之门', '魔兽世界'}, 3, {'仙剑奇侠传', '博德之门', '魔兽世界'}, 1, 0.3333333333333333], [{'博德之门'}, 4, {'博德之门', '反恐精英'}, 1, 0.25], [{'博德之门'}, 4, {'仙剑奇侠传', '博德之门'}, 1, 0.25], [{'魔兽世界'}, 4, {'魔兽世界', '反恐精英'}, 1, 0.25], [{'魔兽世界'}, 4, {'仙剑奇侠传', '魔兽世界'}, 1, 0.25], [{'最终幻想'}, 5, {'空之轨迹', '最终幻想'}, 1, 0.2], [{'最终幻想'}, 5, {'生化危机', '最终幻想'}, 1, 0.2]]
