الگوریتم اپریوری (Apriori) به همراه کد پیاده‌سازی در پایتون — کاوش قواعد وابستگی در داده‌کاوی

الگوریتم اپریوری (Apriori) بر این اصل بنا شده که اگر یک مجموعه اقلام (itemset) مکرر است، پس همه زیرمجموعه‌های آن نیز مکرر هستند. این بدین معنا است که اگر {0,1} مکرر باشد، پس {0} و {1} نیز مکرر هستند. بالعکس این قاعده نیز صادق است، یعنی اگر یک مجموعه اقلام مکرر نباشد، زیرمجموعه‌های آن نیز مکرر نیستند. با توجه به توضیحات بالا، برای یافتن یک مجموعه قواعد وابستگی، ابتدا باید مجموعه اقلام مکرر را پیدا کرد. برای حل این مساله، نیاز به کار با نوع داده‌های عددی و اسمی (دسته‌ای) است.

تحلیل وابستگی

جست‌و‌جو به دنبال روابط در پایگاه داده‌های بزرگ با عنوان تحلیل وابستگی یا کاوش قواعد وابستگی (association rule mining) شناخته شده است. مساله آن است که کشف ترکیب‌های گوناگون از اقلام می‌تواند کاری زمان‌بر و چه بسا از لحاظ توان پردازشی غیر ممکن باشد. این ترکیب‌ها به دو شکل ممکن است به وقوع بپیوندند. این دو فرم عبارتند از اقلام مکرر و قواعد وابستگی. مجموعه اقلام مکرر مجموعه‌ای از آیتم‌ها هستند که مکررا با یکدیگر به وقوع می‌پیوندند. دومین راه برای مشاهده روابط جالب بین آیتم‌ها، قواعد وابستگی است. قواعد وابستگی، ارتباطات قدرتمند بین آیتم‌ها را تبیین می‌کنند.

با استفاده از کاوش مجموعه اقلام مکرر، خرده‌فروشان قادر به کسب درک بهتر از مشتریان خود هستند. دیگر مثال از کاربردهای قواعد وابستگی، موتورهای جست‌و‌جو است. برای کاوش مجموعه اقلام مکرر و کشف قواعد وابستگی، از پشتیبان و اطمینان به عنوان راهکارهایی استفاده می‌شود که با بهره‌گیری از آن‌ها می‌توان تحلیل وابستگی را کمّی کرد.

پشتیبان یک مجموعه اقلام، به عنوان درصدی از مجموعه داده که شامل آن مجموعه اقلام است تعریف شده. اطمینان برای قاعده P ➞ H به صورت (support(P | H) / support(P تعریف شده است. در پایتون، علامت «|» برای اتحاد مجموعه‌ها به کار می‌رود، این در حالیست که نماد ریاضی اتحاد مجموعه‌ها «U» است. P | H یعنی (اتحاد P و H) شامل همه آیتم‌های موجود در مجموعه P یا H است.

رویکرد عمومی به الگوریتم اپریوری (Apriori)

1. گردآوری: هر روشی
2. آماده‌سازی: هر نوع داده‌ای (در حالیکه مجموعه داده در حال جمع‌آوری است) کار می‌کند.
3. تحلیل: هر روشی
4. آموزش: استفاده از روش اپریوری برای یافتن مجموعه اقلام مکرر
5. تست: اعمال نمی‌شود.
6. کاربرد: این راهکار برای پیدا کردن مجموعه اقلام مکرر و قواعد وابستگی بین اقلام به کار می‌رود.

پیدا کردن مجموعه اقلام مکرر

راهکار جهت پیدا کردن مجموعه اقلام مکرر استفاده از الگوریتم اپریوری است. این الگوریتم نیازمند آن است که حداقل میزان اطمینان (Support) به عنوان ورودی به آن داده شود. الگوریتم، لیستی از همه اقلام کاندید با یک آیتم را فراهم می‌کند. سپس، مجموعه داده تراکنشی به منظور بررسی آنکه کدام مجموعه‌ها دارای حداقل سطح پشتیبان هستند اسکن می‌شود.

مجموعه‌هایی که حداقل سطح پشتیبان را ندارند، حذف می‌شوند. مجموعه داده‌های باقیمانده ترکیب می‌شوند تا مجموعه اقلام دارای دو آیتم حاصل شوند. دوباره، مجموعه داده تراکنشی اسکن می‌شود و مجموعه اقلامی که دارای حداقل سطح پشتیبانی نیستند، بیرون انداخته می‌شوند. این روال تا زمانی که همه مجموعه‌ها حذف شوند ادامه می‌یابد.

اسکن کردن مجموعه داده

برای هر تراکنش در مجموعه داده:

برای هر مجموعه اقلام مکرر:

Check to see if can is a subset of tran
If so increment the count of can

برای هر مجموعه اقلام مکرر کاندید:

اگر پشتیبان به آستانه حداقلی می‌رسد، آن آیتم را نگه دارد

لیست مجموعه اقلام مکرر را بازگردان

In [1]:

from numpy import *

یک مجموعه داده ساده برای تست بساز

In [2]:

def loadDataSet():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

قطعه کد بالا، C1 را می‌سازد. C1، مجموعه اقلام مکرر کاندید با سایز یک است. در الگوریتم اپریوری C1 ساخته و سپس کل مجموعه داده به منظور بررسی آنکه آیا یک مجموعه اقلام حداقل آستانه لازم برای پشتیبانی را دارا است یا خیر، اسکن می‌شود. مجموعه داده‌ای که دارای حداقل آستانه است به L1 مبدل خواهد شد. L1 ترکیب می‌شود تا C2 ساخته شود و C2 فیلتر می‌شود تا به L2 تبدیل شود. Frozensets، مجموعه‌هایی هستند که فریز شده‌اند تا غیر قابل تغییر باشند. به جای set، نیاز به استفاده از frozenset‌ها است، زیرا در ادامه از این مجموعه‌ها به عنوان کلید در دیکشنری (dictionary) استفاده خواهد شد.

نمی‌توان یک مجموعه را تنها با یک عدد صحیح (integer) در پایتون ساخت. برای این کار نیاز به استفاده از لیست (list) است. به همین دلیل است که لیستی از لیست‌های تک آیتمی ساخته می‌شود. در نهایت، لیست باید مرتب‌سازی، هر آیتم در لیست به ()frozenset نگاشت و در نهایت لیست frozenset‌ها بازگردانده شود.

In [11]:

def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
                
    C1.sort()
    return list(map(frozenset, C1))#use frozen set so we
                            #can use it as a key in a dict

این تابع سه آرگومان مجموعه داده (Ck)، لیستی از مجموعه‌های کاندید و minSupport را دریافت می‌کند. minSupport حداقل پشتیبانی است که داده‌کاو انتظار دارد. کد زیر مربوط به تابعی است که برای تولید L1 از C1 استفاده می‌شود. علاوه بر این، تابع یک دیکشنری با مقادیر پشتیبان را باز می‌گرداند.

In [28]:

def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):
                if not can in ssCnt: ssCnt[can]=1
                else: ssCnt[can] += 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key]/numItems
        if support >= minSupport:
            retList.insert(0,key)
        supportData[key] = support
    return retList, supportData

In [29]:

dataSet = loadDataSet()
dataSet

Out[29]:

In [30]:

C1 = createC1(dataSet)

In [31]:

C1

Out[31]:

C1 شامل لیستی از همه آیتم‌های موجود در frozenset است.

In [32]:

#D is a dataset in the setform.

D = list(map(set,dataSet))

In [33]:

D

Out[33]:

اکنون همه چیز به شکل مجموعه موجود است و می‌توان آیتم‌هایی که حداقل پشتیبان را ندارند، حذف کرد.

In [34]:

L1,suppDat0 = scanD(D,C1,0.5)
L1

Out[34]:

چهار آیتم مشخص شده در بالا، لیست L1 را می‌سازند، این همان لیست مجموعه‌های تک آیتمی است که در حداقل ۵۰٪ از تراکنش‌ها به وقوع می‌پیوندند. آیتم ۴ حداقل سطح پشتیبانی را ندارد، بنابراین بخشی از L1 محسوب نمی‌شود. با حذف آن، چیزهای بیشتری نسبت به زمانی که مجموعه‌های دو آیتمی کشف می‌شوند حذف شده است.

شبه کد الگوریتم اپریوری

در حالیکه تعداد آیتم‌های موجود در مجموعه بزرگ‌تر از صفر است:

Create a list of candidate itemsets of length k
Scan the dataset to see if each itemset is frequent
Keep frequent itemsets to create itemsets of length k+1

تابع اصلی ()apriori است. این تابع ()aprioriGen را برای ساخت مجموعه اقلام کاندید فراخوانی می‌کند (Ck). تابع ()aprioriGen لیستی از اقلام مکرر (Lk)، و ابعاد مجموعه اقلام (K) را دریافت می‌کند تا Ck را بسازد. برای مثال، مجموعه اقلام {0}، {1} و {2} را دریافت کرده و  {0,1}، {0,2} و {1,2} را می‌سازد. این مجموعه‌ها با استفاده از اتحاد مجموعه‌ها با یکدیگر ترکیب می‌شوند. نماد اتحاد در پایتون همانطور که پیش از این بیان شد، «|» است.

In [35]:

def aprioriGen(Lk, k): #creates Ck
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i+1, lenLk): 
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1==L2: #if first k-2 elements are equal
                retList.append(Lk[i] | Lk[j]) #set union
    return retList

In [38]:

def apriori(dataSet, minSupport = 0.5):
    C1 = createC1(dataSet)
    D = list(map(set, dataSet))
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk
        supportData.update(supK)
        L.append(Lk)
        k += 1
    return L, supportData

In [39]:

L,suppData = apriori(dataSet)

In [40]:

L

Out[40]:

L شامل لیست‌هایی از مجموعه اقلام مکرر است که دارای حداقل پشتیبان ۰.۵ هستند. متغیر suppData، یک دیکشنری با مقادیر پشتیبان مجموعه اقلام این مطلب است.

In [46]:

L[0]

Out[46]:

In [47]:

L[1]

Out[47]:

In [48]:

L[2]

Out[48]:

In [49]:

L[3]

Out[49]:

In [50]:

aprioriGen(L[0],2)

Out[50]:

کاوش قواعد وابستگی از مجموعه اقلام مکرر

برای کشف قواعد وابستگی، کار با یک مجموعه اقلام مکرر آغاز می‌شود. داده‌کاو می‌داند که این مجموعه اقلام یکتا هستند، اما قصد دارد بررسی کند که آیا می‌توان نکته دیگری از آن استخراج کرد. یک آیتم یا یک مجموعه از اقلام می‌تواند دلالت ضمنی بر دیگر آیتم داشته باشد. ()generateRules دستور اصلی است که دو دستور دیگر را فراخوانی می‌کند.

تابع ()generateRules، سه ورودی دریافت می‌کند. این ورودی‌ها عبارتند از لیست مجموعه اقلام مکرر، یک دیکشنری از داده‌های پشتیبان برای آن اقلام و یک آستانه حداقل اطمینان. این تابع قرار است لیستی از قواعد با مقدار اطمینان آن‌ها را تولید کند تا بتوان بعدا آن‌ها را بر اساس این مقدار مرتب‌سازی کرد.

In [51]:

def generateRules(L, supportData, minConf=0.7):  #supportData is a dict coming from scanD
    bigRuleList = []
    for i in range(1, len(L)):#only get the sets with two or more items
        for freqSet in L[i]:
            H1 = [frozenset([item]) for item in freqSet]
            if (i > 1):
                rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
            else:
                calcConf(freqSet, H1, supportData, bigRuleList, minConf)
    return bigRuleList

()calcConf اطمینان قواعد را محاسبه و سپس بررسی می‌کند که کدام قواعد حداقل اطمینان (آستانه اطمینان) را دارند.

In [53]:

def calcConf(freqSet, H, supportData, brl, minConf=0.7):
    prunedH = [] #create new list to return
    for conseq in H:
        conf = supportData[freqSet]/supportData[freqSet-conseq] #calc confidence
        if conf >= minConf: 
            print (freqSet-conseq,'-->',conseq,'conf:',conf)
            brl.append((freqSet-conseq, conseq, conf))
            prunedH.append(conseq)
    return prunedH

()rulesFromConseq قواعد وابستگی بیشتری از مجموعه داده اولیه تولید می‌کند. این تابع، مجموعه اقلام مکرر و H که لیستی از اقلامی که می‌توانند در سمت راست قاعده باشند را دریافت می‌کند.

In [54]:

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    m = len(H[0])
    if (len(freqSet) > (m + 1)): #try further merging
        Hmp1 = aprioriGen(H, m+1)#create Hm+1 new candidates
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):    #need at least two sets to merge
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

In [55]:

L,suppData= apriori(dataSet,minSupport=0.5)

In [56]:

rules= generateRules(L,suppData, minConf=0.7)

حاصل اجرای کد بالا سه قاعده زیر است.

{1} ➞ {3}

{5} ➞ {2}

{2} ➞ {5}

نکته جالب توجه آن است که قواعد دارای ۲ و ۵ قابل معکوس شدن هستند، اما قاعده دارای ۱ و ۳ اینچنین نیست.

کشف ویژگی‌های مشابه در قارچ‌های سمی

در ادامه چگونگی کشف ویژگی‌های مشابه در قارچ‌های سمی با استفاده از الگوریتم اپریوری و کد پایتون آمده است.

In [70]:

mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]

In [71]:

L,suppData= apriori(mushDatSet, minSupport=0.3)

با استفاده از قطعه کد زیر، اقلام مکرر در ویژگی سمی ۲ جست‌و‌جو می‌شوند.

 In [73]:

for item in L[1]:
    if item.intersection('2'):
        print (item)

می‌توان این کار را برای مجموعه اقلام بزرگ‌تر تکرار کرد.

In [79]:

for item in L[6]:
    if item.intersection('2'):
        print (item)

In [83]:

rules= generateRules(L,suppData, minConf=0.7)

اگر نوشته بالا برای شما مفید بود، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های آمار، احتمالات و داده‌کاوی
• آموزش برنامه‌نویسی پایتون – مقدماتی
• آموزش برنامه‌نویسی یادگیری عمیق با پایتون (TensorFlow و Keras)
• مجموعه آموزش‌های برنامه نویسی متلب (MATLAB)
• مجموعه آموزش‌های هوش محاسباتی

^^