Heim >Datenbank >MySQL-Tutorial >Apriori算法的Python实现

Apriori算法的Python实现

WBOY
WBOYOriginal
2016-06-07 16:09:541920Durchsuche

Apriori算法是数据挖掘中频发模式挖掘的鼻祖,从60年代就开始流行,其算法思想也十分简单朴素,首先挖掘出长度为1的频繁模式,然后k=2 将这些频繁模式合并组成长度为k的频繁模式,算出它们的频繁次数,而且要保证其所有k-1长度的子集也是频繁的,值得注意的

Apriori算法是数据挖掘中频发模式挖掘的鼻祖,从60年代就开始流行,其算法思想也十分简单朴素,首先挖掘出长度为1的频繁模式,然后k=2

将这些频繁模式合并组成长度为k的频繁模式,算出它们的频繁次数,而且要保证其所有k-1长度的子集也是频繁的,值得注意的是,为了避免重复,合并的时候,只合并那些前k-2个字符都相同,而k-1的字符一边是少于另一边的。

以下是算法的Python实现:

__author__ = 'linfuyuan'
min_frequency = int(raw_input('please input min_frequency:'))
file_name = raw_input('please input the transaction file:')
transactions = []


def has_infrequent_subset(candidate, Lk):
    for i in range(len(candidate)):
        subset = candidate[:-1]
        subset.sort()
        if not ''.join(subset) in Lk:
            return False
        lastitem = candidate.pop()
        candidate.insert(0, lastitem)
    return True


def countFrequency(candidate, transactions):
    count = 0
    for transaction in transactions:
        if transaction.issuperset(candidate):
            count += 1
    return count


with open(file_name) as f:
    for line in f.readlines():
        line = line.strip()
        tokens = line.split(',')
        if len(tokens) > 0:
            transaction = set(tokens)
            transactions.append(transaction)
currentFrequencySet = {}
for transaction in transactions:
    for item in transaction:
        time = currentFrequencySet.get(item, 0)
        currentFrequencySet[item] = time + 1
Lk = set()
for (itemset, count) in currentFrequencySet.items():
    if count >= min_frequency:
        Lk.add(itemset)
print ', '.join(Lk)

while len(Lk) > 0:
    newLk = set()
    for itemset1 in Lk:
        for itemset2 in Lk:
            cancombine = True
            for i in range(len(itemset1)):
                if i < len(itemset1) - 1:
                    cancombine = itemset1[i] == itemset2[i]
                    if not cancombine:
                        break
                else:
                    cancombine = itemset1[i] < itemset2[i]
                    if not cancombine:
                        break
            if cancombine:
                newitemset = []
                for char in itemset1:
                    newitemset.append(char)
                newitemset.append(itemset2[-1])
                if has_infrequent_subset(newitemset, Lk) and countFrequency(newitemset, transactions) >= min_frequency:
                    newLk.add(&#39;&#39;.join(newitemset))
    print &#39;, &#39;.join(newLk)
    Lk = newLk
Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn