Apriori 알고리즘

난이도 ★★★★★ (너무 어렵다)

요구사항

● 실행파일 이름 : apriori.exe

● 실행프로그램 인자 : minimum support, input file name, output file name

● 입력파일 형식

● 출력파일 형식

● 기타 주의사항

1. 실행시 인자로 넘겨주는 Min Support값과 출력시 Support값은 %값이다.

2. 출력파일에서의 행별 정렬 순서는 중요하지 않다.

● 결과 테스트용 입력 파일

input.txt

● 결과 테스트용 출력 파일

1. Min Support = 10%

output_10.txt

2. Min Support = 9%

output_9.txt

3. Min Support = 6%

output_6.txt

4. Min Support = 2% (굉장히 오래걸림. 1시간 이상)

output_2.txt

● 소스 코드 (답은 맞지만 느립니다. 최적의 코드가 결코 아닙니다)

1. 직접 다운

apriori.cpp

2. 소스 보기

#include <stdio.h>
#include <stdlib.h>
 
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
 
#include <set>
#include <algorithm>
 
#include <iomanip>
 
#define DEBUG_MODE true
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    set<int> itemset;
    int sup;
} Itemset;
 
void makeC(vector<Itemset> *pC, vector<Itemset> *pLi) {
    pC->clear();
 
    // self-joining L
    for (int i = 0; i < pLi->size() - 1; i++) {
        for (int j = i + 1; j < pLi->size(); j++) {
            // get L(i) - L(j)
            set<int> i_diff_j;
            set_difference(pLi->at(i).itemset.begin(), pLi->at(i).itemset.end(),
                pLi->at(j).itemset.begin(), pLi->at(j).itemset.end(),
                inserter(i_diff_j, i_diff_j.end()));
 
            // if could
            if (i_diff_j.size() == 1) {
                // generate a candidate
                set<int> candidate;
 
                candidate.insert(pLi->at(j).itemset.begin(), pLi->at(j).itemset.end());
                candidate.insert(i_diff_j.begin(), i_diff_j.end());
 
                // redundancy check
                bool found = false;
                for each (Itemset c in *pC) {
                    set<int> result;
                    set_difference(c.itemset.begin(), c.itemset.end(), candidate.begin(), candidate.end(), inserter(result, result.end()));
                    if (result.empty()) {
                        found = true;
                        break;
                    }
                }
 
                // if not found, push
                if (!found) {
                    Itemset item;
 
                    item.itemset = candidate;
                    item.sup = 0;
 
                    pC->push_back(item);
                }
            }
        }
    }
 
    // if don't need to be pruned, return
    if ((pC->size() < 1) || (pC->at(0).itemset.size() < 3)) {
        return;
    }
 
    // pruning
    int i = 0;
    while (true) {
        if (i >= pC->size()) {
            break;
        }
 
        for (int j = 0; j < pC->at(i).itemset.size(); j++) {
            // get subSet which excludes jth number
            set<int> subSet;
 
            set<int>::iterator it = pC->at(i).itemset.begin();
            if (j == 0) {    // first
                std::advance(it, 1);
                subSet.insert(it, pC->at(i).itemset.end());
            }
            else if (j == pC->at(i).itemset.size() - 1) {    // last
                std::advance(it, j);
                subSet.insert(pC->at(i).itemset.begin(), it);
            }
            else {    // else
                std::advance(it, j);
                subSet.insert(pC->at(i).itemset.begin(), it);
 
                std::advance(it, 1);
                subSet.insert(it, pC->at(i).itemset.end());
            }
 
            // check
            bool found = false;
            for each (Itemset l in *pLi) {
                set<int> result;
                set_difference(subSet.begin(), subSet.end(), l.itemset.begin(), l.itemset.end(), inserter(result, result.end()));
                if (result.empty()) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                pC->erase(pC->begin() + i);
                i--;
                break;
            }
        }
 
        i++;
    }
}
 
void makeL(vector<vector<Itemset>> *pL, vector<Itemset> *pC, int minSupport) {
    vector<Itemset> Li;
 
    for each (Itemset c in *pC) {
        if (c.sup >= minSupport) {
            Itemset item;
 
            item.itemset = c.itemset;    // could generate error
            item.sup = c.sup;
 
            Li.push_back(item);
        }
    }
 
    pL->push_back(Li);
 
    if (DEBUG_MODE) {
        printf("\n************************\n");
        int i = pL->size() - 1;
        printf("L[%d] (size = %d, minSup = %d)\n", i, pL->at(i).size(), minSupport);
        for each (Itemset l in pL->at(i)) {
            printf("{ ");
            for each (int num in l.itemset) {
                printf("%d ", num);
            }
            printf(" }, %d\t", l.sup);
        }
        printf("\n*************************\n");
    }
}
 
set<set<int>> findSubsets(set<int> A) {
    if (A.empty()) {
        set<set<int>> ret;
        return ret;
    }
 
    set<int> tmp;
    set<int>::iterator it = A.begin();
    std::advance(it, 1);
    tmp.insert(it, A.end());
 
    set<set<int>> B = findSubsets(tmp);
 
    set<set<int>> C;
 
    int A0 = *A.begin();
    for each (set<int> D in B) {
        set<int> temp;
        temp.insert(A0);
        temp.insert(D.begin(), D.end());
        C.insert(temp);
 
        set<int> temp2;
        temp2.insert(A0);
        C.insert(temp2);
    }
    if (B.empty()) {
        set<int> temp;
 
        temp.insert(A0);
 
        C.insert(temp);
    }
 
    B.insert(C.begin(), C.end());
 
    return B;
}
 
int getSupport(set<int> *itemset, vector<vector<Itemset>> *pL) {
    for each (Itemset l in pL->at(itemset->size() - 1)) {
        set<int> result;
        set_difference(l.itemset.begin(), l.itemset.end(), itemset->begin(), itemset->end(), inserter(result, result.end()));
        if (result.empty()) {
            return l.sup;
        }
    }
 
    return -1;
}
 
int main(int argc, char** argv) {
    if (argc != 4) {
        cout << "Error Code: 001" << "\n" << "argc should be 4" << endl;
        return 0;
    }
 
    int relativeSupport = atoi(argv[1]);
    char* inputFileName = argv[2];
    char* outputFileName = argv[3];
 
    if (DEBUG_MODE) {
        printf("%d %s %s\n", relativeSupport, argv[2], argv[3]);
    }
 
    int sizeOfTransactions = 0;
 
    // scan to increment the count of all candidates in C(1)
    vector<vector<Itemset>> L;    // L(i) : frequent itemset of size i
    vector<Itemset> C;    // C(i) : candidate itemset of size i
    ifstream inputFile(inputFileName);
    if (inputFile.is_open()) {
        string line;
        while (getline(inputFile, line)) {
            sizeOfTransactions++;
 
            // get transaction
            set<int> transaction;
            stringstream ss(line);
            int num;
            while (ss >> num) {
                transaction.insert(num);
 
                // find num in C
                int target = -1;
                for (int i = 0; i < C.size(); i++) {
                    if (C[i].itemset.find(num) != C[i].itemset.end()) {
                        target = i;
                        break;
                    }
                }
 
                // not found
                if (target == -1) {
                    Itemset item;
 
                    item.itemset.insert(num);
                    item.sup = 0;
 
                    C.push_back(item);
                }
 
                // found
                else {
                    C[target].sup++;
                }
            }
 
            // get C's sup
            for each (Itemset c in C) {
                set<int> result;
                set_difference(c.itemset.begin(), c.itemset.end(), transaction.begin(), transaction.end(), inserter(result, result.end()));
                if (result.empty()) {
                    c.sup++;
                }
            }
        }
        inputFile.close();
    }
    else {
        cout << "Error Code: 002" << "\n" << "Cannot open input file. (name: " << inputFileName << ")" << endl;
        return 0;
    }
 
    // get minSupport
    int minSupport = ceil(((double)sizeOfTransactions / 100) * relativeSupport);
 
    // get L(1)
    makeL(&L, &C, minSupport);
 
    // get C(i) & L(i) where i > 1
    int i = 0;
    while (true) {
        // get C(i+1)
        makeC(&C, &L[i]);
 
        // if cannot generate C(i+1), break
        if (C.empty()) {
            break;
        }
 
        // scan to increment the count of all candidates in C
        ifstream inputFile(inputFileName);
        if (inputFile.is_open()) {
            string line;
            while (getline(inputFile, line)) {
                // get transaction
                set<int> transaction;
                stringstream ss(line);
                int num;
                while (ss >> num) {
                    transaction.insert(num);
                }
 
                // get C's sup
                for (int j = 0; j < C.size(); j++) {
                    set<int> result;
                    set_difference(C[j].itemset.begin(), C[j].itemset.end(), transaction.begin(), transaction.end(), inserter(result, result.end()));
                    if (result.empty()) {
                        C[j].sup++;
                    }
                }
            }
            inputFile.close();
        }
        else {
            cout << "Error Code: 003(" << i << ")" << "\n" << "Cannot open input file. (name: " << inputFileName << ")" << endl;
            return 0;
        }
 
        // get L(i+1)
        makeL(&L, &C, minSupport);
 
        i++;
    }
    
    // output
    ofstream outputFile(outputFileName);
    if (outputFile.is_open()) {
        printf("\n*** output... ***\n");
        outputFile << fixed << setprecision(2);
        for (int i = 1; i < L.size(); i++) {
            for (int j = 0; j < L.at(i).size(); j++) {    // L.at(i) : {itemset}, {itemset}, {itemset}, ...
                // get all sizes of subset
                set<set<int>> subsets = findSubsets(L.at(i).at(j).itemset);    // L.at(i).at(j) : {itemset}
 
                for each (set<int> subset1 in subsets) {
                    set<int> subset2;
                    set_difference(L.at(i).at(j).itemset.begin(), L.at(i).at(j).itemset.end(), subset1.begin(), subset1.end(), inserter(subset2, subset2.end()));
                    if (subset2.empty()) {
                        continue;
                    }
 
                    // print subset1
                    outputFile << "{";
                    int pos = 0;
                    for each (int item in subset1) {
                        outputFile << item;
                        if (pos < subset1.size() - 1) {
                            outputFile << ",";
                        }
                        else {
                            outputFile << "}\t";
                        }
                        pos++;
                    }
 
                    // print subset2
                    outputFile << "{";
                    pos = 0;
                    for each (int item in subset2) {
                        outputFile << item;
                        if (pos < subset2.size() - 1) {
                            outputFile << ",";
                        }
                        else {
                            outputFile << "}\t";
                        }
                        pos++;
                    }
 
                    // print relative support of original set (subset1 + subset2)
                    outputFile << (L.at(i).at(j).sup / (double)sizeOfTransactions) * 100 << "\t";
 
                    // print confidence (original set's support / subset1's support)
                    outputFile << (L.at(i).at(j).sup / (double)getSupport(&subset1, &L)) * 100 << endl;
                }
            }
        }
 
        outputFile.close();
    }
    else {
        cout << "Error Code: 004" << "\n" << "Cannot open output file. (name: " << outputFileName << ")" << endl;
        return 0;
    }
 
    return 0;
}

● 출처 : 2015년 한양대학교 김상욱 교수님의 데이터마이닝 수업 과제