大師兄的數(shù)據(jù)分析學(xué)習(xí)筆記(二十八）：聚類（四）
大師兄的數(shù)據(jù)分析學(xué)習(xí)筆記(三十）：半監(jiān)督學(xué)習(xí)
一缓呛、關(guān)聯(lián)規(guī)則
- 關(guān)聯(lián)規(guī)則反應(yīng)一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。
- 幾個(gè)重要概念：
- 項(xiàng)目：一個(gè)字段杭隙，對(duì)交易來說一般指一次交易中的一個(gè)物品哟绊，如：尿布。
- 事務(wù)：某個(gè)客戶在一次交易中痰憎，發(fā)生的所有項(xiàng)目的集合票髓，如：尿布、啤酒铣耘。
- 項(xiàng)集：包含一次事務(wù)中的若干個(gè)項(xiàng)目的集合洽沟。
- 頻繁項(xiàng)集：某個(gè)相集的支持度大于閾值，則稱為頻繁項(xiàng)集蜗细。
- 頻繁項(xiàng)集中的幾個(gè)概念：
- 支持度Support：相集{X,Y}在總項(xiàng)集中出現(xiàn)的概率裆操。
- 置信度Condifence：在先決條件X發(fā)生的條件下，由關(guān)聯(lián)規(guī)則{X->Y}退出Y的概率炉媒。
- 提升度：表示含有X的條件下同時(shí)含有Y的概率跷车，與無論含不含X含有Y的概率之比。(Confidence({X}->{Y})/Support({Y}))橱野。
- 關(guān)聯(lián)規(guī)則的目的朽缴，就是找到數(shù)據(jù)中的頻繁項(xiàng)集。
1. Apriori算法
- Apriorio算法是關(guān)聯(lián)規(guī)則中的常用算法水援，思路如下：
- 首先指定一個(gè)支持度的閾值密强，
- 用閾值將頻繁項(xiàng)集分出來，比如下圖中深色的部分為頻繁項(xiàng)集：
- 圖中的數(shù)字表示項(xiàng)集中項(xiàng)目的個(gè)數(shù)蜗元。
- 其中頻繁項(xiàng)集的組合不一定是頻繁項(xiàng)集或渤，因?yàn)?strong>項(xiàng)集組合取的是兩個(gè)頻繁項(xiàng)集的交集，結(jié)果要看交集的結(jié)果是否大于閾值奕扣。
- 同理薪鹦，兩個(gè)非頻繁項(xiàng)集的組合一定是非頻繁項(xiàng)集。
- 而頻繁項(xiàng)集和非頻繁項(xiàng)集的組合也一定是非頻繁項(xiàng)集。
- 在經(jīng)過若干組合后池磁，只需要輸出頻繁項(xiàng)集即可奔害。
二、序列規(guī)則
- 序列規(guī)則將時(shí)間因素考慮進(jìn)來地熄，剔除關(guān)聯(lián)規(guī)則中時(shí)間點(diǎn)靠后的項(xiàng)目對(duì)時(shí)間點(diǎn)靠前的項(xiàng)的支持华临。
1. Apriori-All算法
- Apriori-All算法通常分為兩步：
Forward：Apriori算法過程。
Backward：去掉時(shí)間序列之后的項(xiàng)對(duì)之前的項(xiàng)的支持端考。
三雅潭、代碼實(shí)現(xiàn)
>>>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 = [
>>> ["魔獸世界", "博德之門", "仙劍奇?zhèn)b傳", "反恐精英"],
>>> ["魔獸世界", "博德之門", "最終幻想", "心跳回憶"],
>>> ["博德之門", "最終幻想", "心跳回憶"],
>>> ["最終幻想", "生化危機(jī)", "空之軌跡"],
>>> ["魔獸世界", "博德之門", "最終幻想", "心跳回憶"],
>>> ["魔獸世界", "最終幻想", "心跳回憶"],
>>> ]
>>> 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, {'仙劍奇?zhèn)b傳', '博德之門', '魔獸世界'}, 1, 0.3333333333333333], [{'博德之門'}, 4, {'博德之門', '反恐精英'}, 1, 0.25], [{'博德之門'}, 4, {'仙劍奇?zhèn)b傳', '博德之門'}, 1, 0.25], [{'魔獸世界'}, 4, {'魔獸世界', '反恐精英'}, 1, 0.25], [{'魔獸世界'}, 4, {'仙劍奇?zhèn)b傳', '魔獸世界'}, 1, 0.25], [{'最終幻想'}, 5, {'空之軌跡', '最終幻想'}, 1, 0.2], [{'最終幻想'}, 5, {'生化危機(jī)', '最終幻想'}, 1, 0.2]]
