Decision Tree

난이도 ★★★★☆ (쉽진 않지만 apriori 보다는 쉽다)

목표

information gain을 사용하여 decision tree를 만들고, 그것을 이용하여 test set을 분류하라.

요구사항

● 실행파일 이름 : dt.exe

● 실행프로그램 인자 : training file name, test file name

● 훈련파일 형식

● 테스트파일 형식

● 기타 주의사항

1. Attribute 선택은 information gain값으로 한다.

2. 정확도가 높을 수록 높은 점수를 받는다.

● 결과 테스트용 입력 파일

1. Training file

dt_train.txt

2. Test file

dt_test.txt

● 결과 테스트용 출력 파일

dt_result.txt

● 소스 코드

1. 직접 다운

dt.cpp

2. 소스 보기

#include <stdio.h>
#include <math.h>    // log2
 
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
 
#pragma warning(disable:4996)
 
#define DEBUG_MODE false    // if true, print logs
 
using namespace std;
 
typedef struct {
    vector<string> attributeNames;
    vector<vector<string>> records;
    int classLabelIndex;
} Table;
 
typedef struct Node {
    int attributeIndex;
    vector<struct Child> children;
} Node;
 
typedef struct Child {
    string value;    // attribute value
    struct Node* pNode;
    string classValue;    // only for leaves
} Child;
 
typedef struct {
    string classValue;
    int count;
} ClassValueCountPair;
 
// only for building tree
typedef struct {
    vector<vector<string>*> remainingRecords;
    vector<ClassValueCountPair> classValueCountPairs;    // for majarity voting. If size() == 1, it means that all records for the remaining records belong to the same class.
} ChildData;
 
// only for getting gains
typedef struct {
    string attributeValue;
    vector<ClassValueCountPair> classValueCountPairs;
} AttributeData;
 
// I(pi[])
double getInfo(const vector<int>* pi) {
    double sum = 0.0;
    for (int i = 0; i < pi->size(); i++) {
            sum += pi->at(i);
    }
 
    double ret = 0.0;
    for (int i = 0; i < pi->size(); i++) {
        if (pi->at(i) == 0) {
            continue;
        }
 
        ret += (-1 * pi->at(i) / sum) * log2(pi->at(i) / sum);
    }
 
    return ret;
}
 
// Gain(attribute)
double getGain(const int attributeIndex, const int classLableIndex, const vector<vector<string>*>* remainingRecords) {
    vector<ClassValueCountPair> classValueTotalCountPairs;    // for infoD
    vector<AttributeData> attributeData;    // for infoAD
 
    for (int i = 0; i < remainingRecords->size(); i++) {
        const string classValue = remainingRecords->at(i)->at(classLableIndex);
        const string attributeValue = remainingRecords->at(i)->at(attributeIndex);
 
        // make attributeData
        bool attributeValueFound = false;
        for (int j = 0; j < attributeData.size(); j++) {
            if (attributeData[j].attributeValue.compare(attributeValue) == 0) {
                bool found = false;
                for (int k = 0; k < attributeData[j].classValueCountPairs.size(); k++) {
                    if (attributeData[j].classValueCountPairs[k].classValue.compare(classValue) == 0) {
                        attributeData[j].classValueCountPairs[k].count++;
                        found = true;
                        break;
                    }
                }
 
                if (!found) {
                    ClassValueCountPair classValueCountPair;
 
                    classValueCountPair.classValue = classValue;
                    classValueCountPair.count = 1;
 
                    attributeData[j].classValueCountPairs.push_back(classValueCountPair);
                }
 
                attributeValueFound = true;
                break;
            }
        }
 
        if (!attributeValueFound) {
            AttributeData attributeDatum;
            attributeDatum.attributeValue = attributeValue;
 
            ClassValueCountPair classValueCountPair;
            classValueCountPair.classValue = classValue;
            classValueCountPair.count = 1;
            attributeDatum.classValueCountPairs.push_back(classValueCountPair);
 
            attributeData.push_back(attributeDatum);
        }
 
        // make classValueTotalCountPairs
        bool found = false;
        for (int j = 0; j < classValueTotalCountPairs.size(); j++) {
            if (classValueTotalCountPairs[j].classValue.compare(classValue) == 0) {
                classValueTotalCountPairs[j].count++;
                found = true;
                break;
            }
        }
 
        if (!found) {
            ClassValueCountPair classValueCountPair;
 
            classValueCountPair.classValue = classValue;
            classValueCountPair.count = 1;
 
            classValueTotalCountPairs.push_back(classValueCountPair);
        }
    }
 
    // get infoD
    double infoD;
    {
        vector<int> pi;
        for (int i = 0; i < classValueTotalCountPairs.size(); i++) {
            pi.push_back(classValueTotalCountPairs[i].count);
        }
        infoD = getInfo(&pi);
    }
 
    // get infoAD's sum
    double infoADSum = 0.0;
    for (int i = 0; i < attributeData.size(); i++) {
        vector<int> pi;
        double sum = 0.0;
        for (int j = 0; j < attributeData[i].classValueCountPairs.size(); j++) {
            pi.push_back(attributeData[i].classValueCountPairs[j].count);
            sum += attributeData[i].classValueCountPairs[j].count;
        }
        infoADSum += (sum / remainingRecords->size()) * getInfo(&pi);
    }
 
    if (DEBUG_MODE) {
        printf("[rec_size=%2d, att_id=%d, att_size=%d] infoD=%.3f, infoADSum=%.3f, gain=%.3f\n", remainingRecords->size(), attributeIndex, attributeData.size(), infoD, infoADSum, infoD - infoADSum);
    }
 
    return infoD - infoADSum;
}
 
// get decision tree by recursion
Node* getTree(const vector<vector<string>*> remainingRecords, vector<int> remainingAttributeIndexes, const int classLableIndex) {
    // select an attribute which has max gain
    if (DEBUG_MODE) {
        printf("** getGain **\n");
    }
    int selected = 0;
    double maxGain = getGain(remainingAttributeIndexes[selected], classLableIndex, &remainingRecords);
    for (int i = 1; i < remainingAttributeIndexes.size(); i++) {
        double gain = getGain(remainingAttributeIndexes[i], classLableIndex, &remainingRecords);
        if (gain > maxGain) {
            maxGain = gain;
            selected = i;
        }
    }
    const int selectedAttributeIndex = remainingAttributeIndexes[selected];
    if (DEBUG_MODE) {
        printf("\n\n");
    }
 
    // get new remainingAttributeIndexes which excludes the selectedAttributeIndex
    remainingAttributeIndexes.erase(remainingAttributeIndexes.begin() + selected);
 
    // make node (1) : node allocation and set node.attributeIndex
    Node* node = new Node;
    node->attributeIndex = selectedAttributeIndex;
 
    // make node (2) : make children and childData
    vector<ChildData> childData;
    for (int i = 0; i < remainingRecords.size(); i++) {
        string childValue = remainingRecords[i]->at(selectedAttributeIndex);
        string classValue = remainingRecords[i]->at(classLableIndex);
 
        bool childValueFound = false;
        for (int j = 0; j < node->children.size(); j++) {
            // found : already exists
            if (node->children[j].value.compare(childValue) == 0) {
                childData[j].remainingRecords.push_back(remainingRecords[i]);
 
                // renew classValueCountPairs
                bool classValueFound = false;
                for (int k = 0; k < childData[j].classValueCountPairs.size(); k++) {
                    if (childData[j].classValueCountPairs[k].classValue.compare(classValue) == 0) {
                        childData[j].classValueCountPairs[k].count++;
                        classValueFound = true;
                        break;
                    }
                }
                if (!classValueFound) {
                    ClassValueCountPair classValueCountPair;
 
                    classValueCountPair.classValue = classValue;
                    classValueCountPair.count = 1;
 
                    childData[j].classValueCountPairs.push_back(classValueCountPair);
                }
 
                childValueFound = true;
                break;
            }
        }
 
        // not found : create new child and new childDatum
        if (!childValueFound) {
            // create new child which will be a part of tree
            Child child;
            child.value = childValue;
            node->children.push_back(child);
 
            // create new childDatum which will be used as a parameter when building tree
            ChildData childDatum;
            childDatum.remainingRecords.push_back(remainingRecords[i]);
 
            ClassValueCountPair classValueCountPair;
            classValueCountPair.classValue = classValue;
            classValueCountPair.count = 1;
            childDatum.classValueCountPairs.push_back(classValueCountPair);
 
            childData.push_back(childDatum);
        }
    }
 
    // make node (3) : get children's nodes by recursion
    for (int i = 0; i < node->children.size(); i++) {
        // if all records for a given node belong to the same class
        if (childData[i].classValueCountPairs.size() == 1) {
            node->children[i].classValue = childData[i].classValueCountPairs[0].classValue;
            node->children[i].pNode = NULL;
        }
 
        // if there are no remaining attributes for further partitioning, majority voting is employed for classifying the leaf
        else if (remainingAttributeIndexes.empty()) {
            int maxClassValueIndex = 0;
            for (int j = 1; j < childData[i].classValueCountPairs.size(); j++) {
                if (childData[i].classValueCountPairs[j].count > childData[i].classValueCountPairs[maxClassValueIndex].count) {
                    maxClassValueIndex = j;
                }
            }
 
            node->children[i].classValue = childData[i].classValueCountPairs[maxClassValueIndex].classValue;
            node->children[i].pNode = NULL;
        }
 
        // if normal case
        else {
            node->children[i].pNode = getTree(childData[i].remainingRecords, remainingAttributeIndexes, classLableIndex);
        }
    }
 
    return node;
}
 
// get class value by recursive tree traversal
void makeDecision(vector<string>* record, const Node* node) {
    const string attributeValue = record->at(node->attributeIndex);
 
    if (DEBUG_MODE) {
        cout << attributeValue << "\t";
    }
 
    for (int i = 0; i < node->children.size(); i++) {
        if (node->children[i].value.compare(attributeValue) == 0) {
            if (node->children[i].pNode == NULL) {
                record->push_back(node->children[i].classValue);
            }
            else {
                makeDecision(record, node->children[i].pNode);
            }
 
            break;
        }
    }
}
 
int main(int argc, char** argv) {
    if (argc != 3) {
        cout << "Error Code: 001" << "\n" << "argc should be 3" << endl;
        return 0;
    }
 
    char* trainingFileName = argv[1];
    char* testFileName = argv[2];
 
    // get training table
    Table trainingTable;
    ifstream trainingFile(trainingFileName);
    if (trainingFile.is_open()) {
        string line;
 
        // get names of attributes
        if (getline(trainingFile, line)) {
            stringstream ss(line);
            string s;
 
            while (ss >> s) {
                trainingTable.attributeNames.push_back(s);
            }
        }
 
        // get records
        while (getline(trainingFile, line)) {
            stringstream ss(line);
            string s;
 
            vector<string> record;
            while (ss >> s) {
                record.push_back(s);
            }
 
            trainingTable.records.push_back(record);
        }
 
        trainingFile.close();
    }
    else {
        cout << "Error Code: 002" << "\n" << "cannot open training file. (name: " << trainingFileName << ")" << endl;
        return 0;
    }
 
    // get Decision Tree (1) : fill remainingRecords with whole records
    vector<vector<string>*> remainingRecords;
    for (int i = 0; i < trainingTable.records.size(); i++) {
        remainingRecords.push_back(&trainingTable.records[i]);
    }
 
    // get Decision Tree (2) : fill remainingAttributeIndexes with whole indexes except class label index
    trainingTable.classLabelIndex = trainingTable.attributeNames.size() - 1;
    vector<int> remainingAttributeIndexes;
    for (int i = 0; i < trainingTable.attributeNames.size(); i++) {
        if (i != trainingTable.classLabelIndex) {
            remainingAttributeIndexes.push_back(i);
        }
    }
 
    // get Decision Tree (3) : get decision tree by calling a recursive function
    Node* root = getTree(remainingRecords, remainingAttributeIndexes, trainingTable.classLabelIndex);
 
    // get test sets
    vector<vector<string>> testRecords;
    ifstream testFile(testFileName);
    if (testFile.is_open()) {
        string line;
 
        // skip names of attributes
        if (getline(testFile, line)) {
            // do nothing
        }
 
        // get records
        while (getline(testFile, line)) {
            stringstream ss(line);
            string s;
 
            vector<string> record;
            while (ss >> s) {
                record.push_back(s);
            }
 
            // get class value and save at the last column
            if (DEBUG_MODE) {
                printf("** makeDecision **\n");
            }
            makeDecision(&record, root);
            if (DEBUG_MODE) {
                printf("\n\n");
            }
 
            // push
            testRecords.push_back(record);
        }
 
        testFile.close();
    }
    else {
        cout << "Error Code: 003" << "\n" << "cannot open test file. (name: " << testFileName << ")" << endl;
        return 0;
    }
 
    // output
    const string OUTPUT_FILE_NAME = "dt_result.txt";
    ofstream outputFile(OUTPUT_FILE_NAME);
    if (outputFile.is_open()) {
        // print attribute names
        for (int i = 0; i < trainingTable.attributeNames.size(); i++) {
            outputFile << trainingTable.attributeNames[i];
            if (i < trainingTable.attributeNames.size() - 1) {
                outputFile << "\t";
            }
            else {
                outputFile << endl;
            }
        }
 
        // print attribute values and class values
        for (int i = 0; i < testRecords.size(); i++) {
            for (int j = 0; j < testRecords[i].size(); j++) {
                outputFile << testRecords[i][j];
                if (j < testRecords[i].size() - 1) {
                    outputFile << "\t";
                }
                else {
                    outputFile << endl;
                }
            }
        }
 
        outputFile.close();
    }
    else {
        cout << "Error Code: 004" << "\n" << "cannot open output file. (name: " << OUTPUT_FILE_NAME << ")" << endl;
        return 0;
    }
 
    return 0;
}

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