Apriori算法的Python实现，apriori算法python

Apriori算法的Python实现，apriori算法python

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(''.join(newitemset))
    print ', '.join(newLk)
    Lk = newLk

Apriori算法的实现,关键是建立其数学模型.以前我写作业时,设计的数据结构如下:
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define ITEM_NAME_LENGTH 20
#define MIN_SUPPORT 2
//项集结构
struct ITEMSET
{
char itemName[ITEM_NAME_LENGTH];
struct ITEMSET *next;
};
//数据库结构
struct TRANSACTION
{
unsigned int tranID;
struct ITEMSET *itemPoint;
struct TRANSACTION *next;
};
//大项目集结构
struct BIGITEMSET
{
struct ITEMSET *itemPoint;
unsigned int count;
struct BIGITEMSET *next;
};
//以下是数据库
char *tran1[3]={"1","3","4"};
char *tran2[3]={"2","3","5"};
char *tran3[4]={"1","2","3","5"};
char *tran4[2]={"2","5"};
//以下是变量声明
struct TRANSACTION *tranHead;
struct BIGITEMSET *bigHead;
struct BIGITEMSET *test;
struct BIGITEMSET *subSetHeadC1,*subSetHeadC2;
当真正理解该算法后,再写程序并不难.
 

你说的是什么语言吧，这样问也不对，既然是算法，那么用什么语言都能实现。