12机器学习实战-第12章 使用FP-growth算法来高效发现频繁项集.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#第12章-使用FP-growth算法来高效发现频繁项集\" data-toc-modified-id=\"第12章-使用FP-growth算法来高效发现频繁项集-1\">第12章 使用FP-growth算法来高效发现频繁项集</a></span><ul class=\"toc-item\"><li><span><a href=\"#FP树-介绍\" data-toc-modified-id=\"FP树-介绍-1.1\">FP树 介绍</a></span></li><li><span><a href=\"#FP-growth-原理\" data-toc-modified-id=\"FP-growth-原理-1.2\">FP-growth 原理</a></span></li></ul></li><li><span><a href=\"#FP-growth-算法优缺点:\" data-toc-modified-id=\"FP-growth-算法优缺点:-2\">FP-growth 算法优缺点:</a></span></li><li><span><a href=\"#从一棵-FP-树中挖掘频繁项集\" data-toc-modified-id=\"从一棵-FP-树中挖掘频繁项集-3\">从一棵 FP 树中挖掘频繁项集</a></span></li><li><span><a href=\"#示例:从新闻网站点击流中挖掘\" data-toc-modified-id=\"示例:从新闻网站点击流中挖掘-4\">示例:从新闻网站点击流中挖掘</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第12章 使用FP-growth算法来高效发现频繁项集\n",
    "\n",
    "\n",
    "本章会在上一章讨论话题的基础上进行扩展，将给出一个非常好的频繁项集发现算法。该算法称作FP-growth，它比上一章讨论的Apriori算法要快。它基于Apriori构建，但在完成相同任务时采用了一些不同的技术。这里的任务是将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或者频繁项对，即常在一块出现的元素项的集合FP树。\n",
    "\n",
    "FP-growth算法只需要对数据库进行两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快。 \n",
    "它发现频繁项集的基本过程如下： \n",
    "(1) 构建FP树 \n",
    "(2) 从FP树中挖掘频繁项集 \n",
    "\n",
    "### FP树 介绍\n",
    "FP树的节点结构如下:\n",
    "```\n",
    "class treeNode:\n",
    "    def __init__(self, nameValue, numOccur, parentNode):\n",
    "        self.name = nameValue     # 节点名称\n",
    "        self.count = numOccur     # 节点出现次数\n",
    "        self.nodeLink = None      # 不同项集的相同项通过nodeLink连接在一起\n",
    "        # needs to be updated\n",
    "        self.parent = parentNode  # 指向父节点\n",
    "        self.children = {}        # 存储叶子节点\n",
    "```\n",
    "\n",
    "### FP-growth 原理\n",
    "基于数据构建FP树\n",
    "\n",
    "步骤1:\n",
    "\n",
    "1. 遍历所有的数据集合，计算所有项的支持度。\n",
    "2. 丢弃非频繁的项。\n",
    "3. 基于 支持度 降序排序所有的项。\n",
    "\n",
    "![](./image/Ch12/1.jpg)\n",
    "\n",
    "\n",
    "1. 所有数据集合按照得到的顺序重新整理。\n",
    "2. 重新整理完成后，丢弃每个集合末尾非频繁的项。\n",
    "\n",
    "![](./image/Ch12/2.jpg)\n",
    "\n",
    "\n",
    "步骤2: 6. 读取每个集合插入FP树中，同时用一个头部链表数据结构维护不同集合的相同项。\n",
    "\n",
    "![](./image/Ch12/3.jpg)\n",
    "\n",
    "最终得到下面这样一棵FP树\n",
    "\n",
    "![](./image/Ch12/4.jpg)\n",
    "\n",
    "从FP树中挖掘出频繁项集\n",
    "\n",
    "步骤3:\n",
    "\n",
    "1. 对头部链表进行降序排序\n",
    "2. 对头部链表节点从小到大遍历，得到条件模式基，同时获得一个频繁项集。\n",
    "\n",
    "![](./image/Ch12/5.jpg)\n",
    "\n",
    "如上图，从头部链表 t 节点开始遍历，t 节点加入到频繁项集。找到以 t 节点为结尾的路径如下:\n",
    "\n",
    "![](./image/Ch12/6.jpg)\n",
    "\n",
    "去掉FP树中的t节点，得到条件模式基<左边路径,左边是值>[z,x,y,s,t]:2，[z,x,y,r,t]:1 。条件模式基的值取决于末尾节点 t ，因为 t 的出现次数最小，一个频繁项集的支持度由支持度最小的项决定。所以 t 节点的条件模式基的值可以理解为对于以 t 节点为末尾的前缀路径出现次数。\n",
    "\n",
    "条件模式基继续构造条件 FP树， 得到频繁项集，和之前的频繁项组合起来，这是一个递归遍历头部链表生成FP树的过程，递归截止条件是生成的FP树的头部链表为空。 根据步骤 2 得到的条件模式基 [z,x,y,s,t]:2，[z,x,y,r,t]:1 作为数据集继续构造出一棵FP树，计算支持度，去除非频繁项，集合按照支持度降序排序，重复上面构造FP树的步骤。最后得到下面 t-条件FP树 :\n",
    "\n",
    "![](./image/Ch12/7.jpg)\n",
    "\n",
    "\n",
    "然后根据 t-条件FP树 的头部链表进行遍历，从 y 开始。得到频繁项集 ty 。然后又得到 y 的条件模式基，构造出 ty的条件FP树，即 ty-条件FP树。继续遍历ty-条件FP树的头部链表，得到频繁项集 tyx，然后又得到频繁项集 tyxz. 然后得到构造tyxz-条件FP树的头部链表是空的，终止遍历。我们得到的频繁项集有 t->ty->tyz->tyzx，这只是一小部分。\n",
    "\n",
    "条件模式基:头部链表中的某一点的前缀路径组合就是条件模式基，条件模式基的值取决于末尾节点的值。\n",
    "条件FP树:以条件模式基为数据集构造的FP树叫做条件FP树。\n",
    "\n",
    "\n",
    "## FP-growth 算法优缺点:\n",
    "\n",
    "* 优点： 1. 因为 FP-growth 算法只需要对数据集遍历两次，所以速度更快。\n",
    "        2. FP树将集合按照支持度降序排序，不同路径如果有相同前缀路径共用存储空间，使得数据得到了压缩。\n",
    "        3. 不需要生成候选集。\n",
    "        4. 比Apriori更快。\n",
    "* 缺点： 1. FP-Tree第二次遍历会存储很多中间过程的值，会占用很多内存。\n",
    "        2. 构建FP-Tree是比较昂贵的。\n",
    "* 适用数据类型：标称型数据(离散型数据)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "#FP树中节点的类定义\n",
    "class treeNode:\n",
    "    def __init__(self, nameValue, numOccur, parentNode):\n",
    "        self.name = nameValue\n",
    "        self.count = numOccur\n",
    "        self.nodeLink = None #nodeLink 变量用于链接相似的元素项\n",
    "        self.parent = parentNode #指向当前节点的父节点\n",
    "        self.children = {} #空字典，存放节点的子节点\n",
    "\n",
    "    def inc(self, numOccur):\n",
    "        self.count += numOccur\n",
    "\n",
    "#将树以文本形式显示\n",
    "    def disp(self, ind=1):\n",
    "        print ('  ' * ind, self.name, ' ', self.count)\n",
    "        for child in self.children.values():\n",
    "            child.disp(ind + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "#构建FP-tree\n",
    "def createTree(dataSet, minSup=1):\n",
    "    headerTable = {}\n",
    "    for trans in dataSet:  #第一次遍历：统计各个数据的频繁度\n",
    "        for item in trans:\n",
    "            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]\n",
    "            #用头指针表统计各个类别的出现的次数，计算频繁量：头指针表[类别]=出现次数\n",
    "    for k in list(headerTable.keys()):  #删除未达到最小频繁度的数据\n",
    "        if headerTable[k] < minSup:\n",
    "            del (headerTable[k])\n",
    "    freqItemSet = set(headerTable.keys())#保存达到要求的数据\n",
    "    # print ('freqItemSet: ',freqItemSet)\n",
    "    if len(freqItemSet) == 0:\n",
    "        return None, None  #若达到要求的数目为0\n",
    "    for k in headerTable: #遍历头指针表\n",
    "        headerTable[k] = [headerTable[k], None]  #保存计数值及指向每种类型第一个元素项的指针\n",
    "    # print ('headerTable: ',headerTable)\n",
    "    retTree = treeNode('Null Set', 1, None)  #初始化tree\n",
    "    for tranSet, count in dataSet.items():  # 第二次遍历：\n",
    "        localD = {}\n",
    "        for item in tranSet:  # put transaction items in order\n",
    "            if item in freqItemSet:#只对频繁项集进行排序\n",
    "                localD[item] = headerTable[item][0]\n",
    "\n",
    "        #使用排序后的频率项集对树进行填充\n",
    "        if len(localD) > 0:\n",
    "            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)]\n",
    "            updateTree(orderedItems, retTree, headerTable, count)  # populate tree with ordered freq itemset\n",
    "    return retTree, headerTable  #返回树和头指针表\n",
    "\n",
    "\n",
    "def updateTree(items, inTree, headerTable, count):\n",
    "    if items[0] in inTree.children:  # 首先检查是否存在该节点\n",
    "        inTree.children[items[0]].inc(count)  # 存在则计数增加\n",
    "    else:  # 不存在则将新建该节点\n",
    "        inTree.children[items[0]] = treeNode(items[0], count, inTree)#创建一个新节点\n",
    "        if headerTable[items[0]][1] == None:  # 若原来不存在该类别，更新头指针列表\n",
    "            headerTable[items[0]][1] = inTree.children[items[0]]#更新指向\n",
    "        else:#更新指向\n",
    "            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])\n",
    "    if len(items) > 1:  #仍有未分配完的树，迭代\n",
    "        updateTree(items[1::], inTree.children[items[0]], headerTable, count)\n",
    "\n",
    "#节点链接指向树中该元素项的每一个实例。\n",
    "# 从头指针表的 nodeLink 开始,一直沿着nodeLink直到到达链表末尾\n",
    "def updateHeader(nodeToTest, targetNode):\n",
    "    while (nodeToTest.nodeLink != None):\n",
    "        nodeToTest = nodeToTest.nodeLink\n",
    "    nodeToTest.nodeLink = targetNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "后面构建树时会 \n",
    "使用 createTree() 函数,而该函数的输入数据类型不是列表。其需要的是一部字典,其中项集为字典中的键,而频率为每个键对应的取值。 createInitSet() 用于实现上述从列表到字典的类型转换过程。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loadSimpDat():\n",
    "    simpDat = [['r', 'z', 'h', 'j', 'p'],\n",
    "               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],\n",
    "               ['z'],\n",
    "               ['r', 'x', 'n', 'o', 's'],\n",
    "               ['y', 'r', 'x', 'z', 'q', 't', 'p'],\n",
    "               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]\n",
    "    return simpDat\n",
    "#createInitSet() 用于实现上述从列表到字典的类型转换过程\n",
    "def createInitSet(dataSet):\n",
    "    retDict = {}\n",
    "    for trans in dataSet:\n",
    "        retDict[frozenset(trans)] = 1\n",
    "    return retDict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "直接参考书中代码运行报错：RuntimeError: dictionary changed size during iteration \n",
    "解决：修改createTree()函数的for k in headerTable.keys(): 为for k in list(headerTable): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['r', 'z', 'h', 'j', 'p'],\n",
       " ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],\n",
       " ['z'],\n",
       " ['r', 'x', 'n', 'o', 's'],\n",
       " ['y', 'r', 'x', 'z', 'q', 't', 'p'],\n",
       " ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simpDat=loadSimpDat()\n",
    "simpDat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{frozenset({'h', 'j', 'p', 'r', 'z'}): 1,\n",
       " frozenset({'s', 't', 'u', 'v', 'w', 'x', 'y', 'z'}): 1,\n",
       " frozenset({'z'}): 1,\n",
       " frozenset({'n', 'o', 'r', 's', 'x'}): 1,\n",
       " frozenset({'p', 'q', 'r', 't', 'x', 'y', 'z'}): 1,\n",
       " frozenset({'e', 'm', 'q', 's', 't', 'x', 'y', 'z'}): 1}"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "initSet=createInitSet(simpDat)\n",
    "initSet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   Null Set   1\n",
      "     z   5\n",
      "       r   1\n",
      "       x   3\n",
      "         s   2\n",
      "           t   2\n",
      "             y   2\n",
      "         r   1\n",
      "           t   1\n",
      "             y   1\n",
      "     x   1\n",
      "       s   1\n",
      "         r   1\n"
     ]
    }
   ],
   "source": [
    "myFPtree,myHeaderTab=createTree(initSet,3)\n",
    "myFPtree.disp()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面给出的是元素项及其对应的频率计数值,其中每个缩进表示所处的树的深度。可以验证一下这棵树上图中所示的树是否等价\n",
    "\n",
    "## 从一棵 FP 树中挖掘频繁项集 \n",
    "从FP树中抽取频繁项集的三个基本步骤如下:\n",
    "\n",
    ">(1) 从FP树中获得条件模式基;\n",
    "(2) 利用条件模式基,构建一个条件FP树;\n",
    "(3) 迭代重复步骤(1)步骤(2),直到树包含一个元素项为止。\n",
    "\n",
    "接下来首先寻找条件模式基的过程。之后为每一个条件模式基创建对应的条件FP树。最后需要构造少许代码来封装上述两个函数,并从FP树中获得频繁项集。\n",
    "\n",
    "**条件模式基是以所查找元素项为结尾的路径集合。**  \n",
    "\n",
    "每一条路径其实都是一条前缀路径(prefix path)。简而言之,一条前缀路径是介于所查找元素项与树根节点之间的所有内容。\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "#从FP树中发现频繁项集\n",
    "def ascendTree(leafNode, prefixPath):  #递归上溯整棵树\n",
    "    if leafNode.parent != None:\n",
    "        prefixPath.append(leafNode.name)\n",
    "        ascendTree(leafNode.parent, prefixPath)\n",
    "\n",
    "\n",
    "def findPrefixPath(basePat, treeNode):  #参数：指针，节点；\n",
    "    condPats = {}\n",
    "    while treeNode != None:\n",
    "        prefixPath = []\n",
    "        ascendTree(treeNode, prefixPath)#寻找当前非空节点的前缀\n",
    "        if len(prefixPath) > 1:\n",
    "            condPats[frozenset(prefixPath[1:])] = treeNode.count #将条件模式基添加到字典中\n",
    "        treeNode = treeNode.nodeLink\n",
    "    return condPats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{frozenset({'z'}): 3}"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findPrefixPath('x',myHeaderTab['x'][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{frozenset({'z'}): 1, frozenset({'s', 'x'}): 1, frozenset({'x', 'z'}): 1}"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findPrefixPath('x',myHeaderTab['r'][1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于每一个频繁项都要创建一棵条件FP树，使用条件模式基作为输入数据，用相同的建树代码构建条件树，之后递归地发现频繁项、发现条件模式基，并且继续构造条件树，直到条件树中没有元素。\n",
    "\n",
    "函数mineTree对参数inTree代表的FP树进行频繁项集挖掘。首先对headerTable中出现的单个元素按出现频率从小到大排序，之后将每个元素的条件模式基作为输入数据，建立针对当前元素的条件树，如果生成的这棵条件树仍有元素，就在这棵条件树里寻找频繁项集，因为prefix参数是在递归过程中不断向下传递的，因此由最初的headerTable中的某个元素x衍生出的所有频繁项集都带有x。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "#递归查找频繁项集\n",
    "def mineTree(inTree, headerTable, minSup, preFix, freqItemList):\n",
    "    # 头指针表中的元素项按照频繁度排序,从小到大\n",
    "    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: str(p[1]))]#python3修改\n",
    "    for basePat in bigL:  #从底层开始\n",
    "        #加入频繁项列表\n",
    "        newFreqSet = preFix.copy()\n",
    "        newFreqSet.add(basePat)\n",
    "#         print ('finalFrequent Item: ',newFreqSet)\n",
    "        freqItemList.append(newFreqSet)\n",
    "        #递归调用函数来创建基\n",
    "        condPattBases = findPrefixPath(basePat, headerTable[basePat][1])\n",
    "#         print ('condPattBases :',basePat, condPattBases)\n",
    "\n",
    "        #2. 构建条件模式Tree\n",
    "        myCondTree, myHead = createTree(condPattBases, minSup)\n",
    "        #将创建的条件基作为新的数据集添加到fp-tree\n",
    "#         print ('head from conditional tree: ', myHead)\n",
    "        if myHead != None: #3. 递归\n",
    "#             print ('conditional tree for: ',newFreqSet)\n",
    "            myCondTree.disp(1)\n",
    "            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "测试以上代码会报错：TypeError: unorderable types: treeNode() < treeNode()原因是python3：comparing integers and strings is not allowed，因此需要修改函数中的为bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: str(p[1]))]添加str将类型转化为字符串类型。 \n",
    "修改参考下列链接说明：https://www.peterbe.com/plog/sorting-mixed-type-lists-in-python-3 \n",
    "测试结果：显示所有的条件树 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   Null Set   1\n",
      "     x   3\n",
      "       z   3\n",
      "   Null Set   1\n",
      "     x   3\n",
      "   Null Set   1\n",
      "     x   3\n",
      "   Null Set   1\n",
      "     t   3\n",
      "       x   3\n",
      "         z   3\n",
      "   Null Set   1\n",
      "     t   3\n",
      "   Null Set   1\n",
      "     t   3\n",
      "       x   3\n",
      "   Null Set   1\n",
      "     t   3\n",
      "   Null Set   1\n",
      "     z   3\n"
     ]
    }
   ],
   "source": [
    "freqItems=[]\n",
    "mineTree(myFPtree,myHeaderTab,3,set([]),freqItems)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'t'},\n",
       " {'t', 'x'},\n",
       " {'t', 'z'},\n",
       " {'t', 'x', 'z'},\n",
       " {'s'},\n",
       " {'s', 'x'},\n",
       " {'r'},\n",
       " {'y'},\n",
       " {'x', 'y'},\n",
       " {'t', 'x', 'y'},\n",
       " {'t', 'y'},\n",
       " {'y', 'z'},\n",
       " {'t', 'y', 'z'},\n",
       " {'x', 'y', 'z'},\n",
       " {'t', 'x', 'y', 'z'},\n",
       " {'x'},\n",
       " {'x', 'z'},\n",
       " {'z'}]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "freqItems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 示例:从新闻网站点击流中挖掘 \n",
    "在上传的源码中,有一个kosarak.dat文件,它包含将近100万条记录 。该文件中的每一行包含某个用户浏览过的新闻报道。一些用户只看过一篇报道,而有些用户看过2498篇报道。 \n",
    "用户和报道被编码成整数,所以查看频繁项集很难得到更多的东西,但是该数据对于展示FP-growth算法的速度十分有效。\n",
    "\n",
    "首先放python3测试结果："
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}