Apriori算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  使用Apriori算法进行关联分析"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loadDataSet():\n",
    "    return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]\n",
    "def createC1(dataSet):\n",
    "    C1=[]\n",
    "    for transaction in dataSet:\n",
    "        for item in transaction:\n",
    "            if not [item] in C1:\n",
    "                C1.append([item])\n",
    "    C1.sort()\n",
    "    print(C1)\n",
    "    # forzenset生成不可变的集合，如果不提供任何参数默认会产生空集合。\n",
    "    #如果提供一个参数，则该参数必须是可迭代的，即，一个序列，或迭代器，或支持迭代的一个对象。\n",
    "    return list(map(frozenset,C1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataSet=loadDataSet()\n",
    "dataSet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1], [2], [3], [4], [5]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[frozenset({1}),\n",
       " frozenset({2}),\n",
       " frozenset({3}),\n",
       " frozenset({4}),\n",
       " frozenset({5})]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C1=createC1(dataSet)\n",
    "C1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def scanD(D,Ck,minSupport):\n",
    "    # 三个参数分别为：数据集，候选项集列表和最小支持度\n",
    "    ssCnt={}\n",
    "    for tid in D:\n",
    "        for can in Ck:\n",
    "            if can.issubset(tid):\n",
    "                if  can not  in ssCnt:\n",
    "                    ssCnt[can]=1\n",
    "                else:\n",
    "                    ssCnt[can]+=1\n",
    "    numItems=float(len(D))\n",
    "    retList=[]\n",
    "    supportData={}\n",
    "    for key in ssCnt:\n",
    "        support=ssCnt[key]/numItems # 计算每项的支持度\n",
    "        if support>=minSupport:\n",
    "            retList.insert(0,key)\n",
    "        supportData[key]=support\n",
    "    return retList,supportData\n",
    "                        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D=list(map(set,dataSet))\n",
    "D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 去掉哪些不满足最小支持度的项集\n",
    "L1,supportData0 =scanD(D,C1,0.5) # 去除了4，值出现了一次\n",
    "L1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 组织完整的Apriori算法\n",
    "def aprioriGen(Lk,k) :# creats Ck\n",
    "    # Lk 频繁项集列表，k 项集元素个数\n",
    "    retList=[]\n",
    "    lenLk=len(Lk)\n",
    "    for i in range(lenLk):\n",
    "         for j in range(i+1, lenLk): \n",
    "            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]\n",
    "            L1.sort(); L2.sort()\n",
    "            if L1==L2:\n",
    "                retList.append(Lk[i] | Lk[j]) #set union\n",
    "    return retList\n",
    "def apriori(dataSet,minSupport=0.5):\n",
    "    C1=createC1(dataSet)\n",
    "    D=list(map(set,dataSet))\n",
    "    L1,supportData=scanD(D,C1,minSupport)\n",
    "    L=[L1]\n",
    "    k=2\n",
    "    while (len(L[k-2])>0):\n",
    "        Ck=aprioriGen(L[k-2],k)\n",
    "        Lk,supK=scanD(D,Ck,minSupport)\n",
    "        supportData.update(supK)\n",
    "        L.append(Lk)\n",
    "        k+=1\n",
    "    return L,supportData"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1], [2], [3], [4], [5]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})],\n",
       " [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})],\n",
       " [frozenset({2, 3, 5})],\n",
       " []]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L,supportData=apriori(dataSet)\n",
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 从频繁项集中挖掘关联规则\n",
    "def generateRules(L, supportData, minConf=0.7):  #supportData is a dict coming from scanD\n",
    "    # 三个参数 ：频繁项集列表、包含哪些频繁项集支持数据的字典，最小可信度阈值。\n",
    "    bigRuleList = []\n",
    "    for i in range(1, len(L)):#only get the sets with two or more items\n",
    "        for freqSet in L[i]:\n",
    "            H1 = [frozenset([item]) for item in freqSet]# 包含单个元素集合的列表H1\n",
    "            if (i > 1):\n",
    "                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)\n",
    "            else:\n",
    "                calcConf(freqSet, H1, supportData, bigRuleList, minConf)\n",
    "    return bigRuleList  \n",
    "#生成候规则集\n",
    "def calcConf(freqSet, H, supportData, brl, minConf=0.7):\n",
    "    prunedH = [] #create new list to return\n",
    "    for conseq in H:\n",
    "        conf = supportData[freqSet]/supportData[freqSet-conseq] #calc confidence\n",
    "        if conf >= minConf: \n",
    "            print(freqSet-conseq,'-->',conseq,'conf:',conf)\n",
    "            brl.append((freqSet-conseq, conseq, conf))\n",
    "            prunedH.append(conseq)\n",
    "    return prunedH\n",
    "# 对规则进行评估\n",
    "def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):\n",
    "    m = len(H[0])\n",
    "    if (len(freqSet) > (m + 1)): #try further merging\n",
    "        Hmp1 = aprioriGen(H, m+1)#create Hm+1 new candidates\n",
    "        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)\n",
    "        if (len(Hmp1) > 1):    #need at least two sets to merge\n",
    "            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "frozenset({3}) --> frozenset({2}) conf: 0.6666666666666666\n",
      "frozenset({2}) --> frozenset({3}) conf: 0.6666666666666666\n",
      "frozenset({5}) --> frozenset({3}) conf: 0.6666666666666666\n",
      "frozenset({3}) --> frozenset({5}) conf: 0.6666666666666666\n",
      "frozenset({5}) --> frozenset({2}) conf: 1.0\n",
      "frozenset({2}) --> frozenset({5}) conf: 1.0\n",
      "frozenset({3}) --> frozenset({1}) conf: 0.6666666666666666\n",
      "frozenset({1}) --> frozenset({3}) conf: 1.0\n",
      "frozenset({5}) --> frozenset({2, 3}) conf: 0.6666666666666666\n",
      "frozenset({3}) --> frozenset({2, 5}) conf: 0.6666666666666666\n",
      "frozenset({2}) --> frozenset({3, 5}) conf: 0.6666666666666666\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(frozenset({3}), frozenset({2}), 0.6666666666666666),\n",
       " (frozenset({2}), frozenset({3}), 0.6666666666666666),\n",
       " (frozenset({5}), frozenset({3}), 0.6666666666666666),\n",
       " (frozenset({3}), frozenset({5}), 0.6666666666666666),\n",
       " (frozenset({5}), frozenset({2}), 1.0),\n",
       " (frozenset({2}), frozenset({5}), 1.0),\n",
       " (frozenset({3}), frozenset({1}), 0.6666666666666666),\n",
       " (frozenset({1}), frozenset({3}), 1.0),\n",
       " (frozenset({5}), frozenset({2, 3}), 0.6666666666666666),\n",
       " (frozenset({3}), frozenset({2, 5}), 0.6666666666666666),\n",
       " (frozenset({2}), frozenset({3, 5}), 0.6666666666666666)]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rules=generateRules(L, supportData, minConf=0.5)\n",
    "rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 发现毒蘑菇的相似特征"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "ename": "FileNotFoundError",
     "evalue": "[Errno 2] No such file or directory: './mushroom.dat'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-39-cb086d9c1fb5>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m# 收集数据\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mmushDatSet\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m[\u001b[0m\u001b[0mline\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msplit\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mline\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mopen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"./mushroom.dat\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mreadlines\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmushDataSet\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mFileNotFoundError\u001b[0m: [Errno 2] No such file or directory: './mushroom.dat'"
     ]
    }
   ],
   "source": [
    "# 收集数据\n",
    "mushDatSet = [line.split() for line in open(\"./mushroom.dat\").readlines()]\n",
    "print(len(mushDataSet))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'mushDatSet' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-40-b4c62b0c436d>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mL\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0msuppData\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mapriori\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mmushDatSet\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mminSupport\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;36m0.3\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mitem\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mL\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mitem\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mintersection\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'2'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m         \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mitem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m: name 'mushDatSet' is not defined"
     ]
    }
   ],
   "source": [
    "\n",
    "L, suppData = apriori(mushDatSet, minSupport=0.3)\n",
    "for item in L[1]:\n",
    "    if item.intersection('2'):\n",
    "        print(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}