• 아래 소개할 모든 Algorithm Script는 Python으로 작성되었습니다.

해당 프로젝트는 수많은 Transaction에 대해 서로 겹치는 ItemSet(Support) 및 연관관계 ItemSet(Confidence)를 조사하여, 사용자가 설정한 목표치보다 높은 Confidence 및 Support를 갖는 ItemSet을 반환하는 작업을 시행하는 Apriori Algorithm을 만드는 것을 목표로 하였다.

프로젝트에 있어서 Input은 Transaction의 Itemset 항목들로 주어졌으며 ItemSet은 공백으로, Transaction은 줄바꿈으로 구분하고 있으며, 그 형태는 아래와 같다.

7	14
9
18	2	4	5	1
15	7	6	11	18	9	12	19	14
9
10
1	13	8	9	3	16	4
......

이에 대해 Output은 위에서 이야기한대로 Itemset의 Confidence 및 Support를 반환하며 형태 상 아래와 같다.

 A  ⊂    B    support  confidence
{3}	{16}	25.2	 84.0
{16}	{3}	25.2	 59.43
{3}	{17}	7.6	 25.33
......

프로그램은 (숫자),(input name),(output name) 순서로 3개의 인자를 받는다. 이 때 main함수에서는 첫번째 인자를 support, confidence 기준치로 삼으며 그 후 input file을 읽어 transaction Itemset을 transactions 전역변수에 집어넣는다. 이 때 지역변수 items를 선언해 새로운 Item을 집어넣을 때마다 해당 item을 items 변수에도 넣어주어 전체 Itemset의 어떤 item 종류가 있는지 표기하도록 한다. (Line 326-348)

그 뒤 items 변수를 이용해 itemset_sup class 객체를 만든다. 이렇게 생성되는 Itemset 객체는 크기가 1인 itemset에 대한 support를 구할 수 있으며 이를 이용, Scan function을 통해 support를 계산하도록 한다. (Line 350-361)

scan function은 Support를 구해야 하는 itemset 모음과 해당 Scan function이 몇번째로 실행된지 표시하는 iteration 인자를 갖는다. 우선 itemset 모음에서 하나씩 itemset을 뽑아 전체 transaction과 비교를 진행, support 기준치를 만족하면 satisfied_itemset에 이를 넣고 그렇지 않은 경우 unsatisfied_itemset에 집어 넣는다. 이 때 구한 support를 기록하기 위해 기존 객체를 새로운 itemset 객체로 만들어서 집어넣는다. (Line 141-152)

그 뒤 satisfied, unsatisfied인 itemset 배열을 get_next_itemset function에 인자로 넣어주어 다음 크기 itemset 모음을 구한다. 여기서 satisfied itemset을 순회하는 두 변수를 선언, 이를 이용해 O(N^2) 속도로 새로운 itemset을 만든다.
이렇게 만든 itemset이 unsatisfied itemset 중 하나라도 가지고 있으면 support를 만족할 수 없으므로(Frequent Pattern의 부분집합은 전부 Frequent pattern으로 이루어지기 때문) 제외하도록 한다. 이렇게 구한 itemset은 new_itemset에 집어넣고 탐색이 종료되면 반환한다. (Line 168-215)

scan function은 반환한 itemset을 인자로 받아 다시 scan function을 진행하여 support를 구한다. 이러한 재귀실행은 satisfied itemset이 2개 이상인 경우에 대해 계속 반복하며 그렇지 않은 경우 프로그램을 종료하게 된다.

scan function에서 인자로 받은 itemset들의 크기가 2 이상이면 연관관계를 만들 수 있으며, support 조건을 만족해야 confidence도 구하기로 했으므로 satisfied_itemset에 대해서 association을 구하는 함수, get_association_support을 실행한다. (Line 155)

우선 인자로 받은 itemset 객체 모음에 접근, 객체 하나를 꺼내 item 중 하나를 left, 나머지를 right에 놓은 tuple형태로 만들어서 tuple_list에 집어넣는다.
이렇게 만든 tuple_list는 반복문을 이용, left item을 가지는 Transaction을 전체 transaction에 찾아 기록(A)하며 이들 중 right item을 가진 transaction 숫자(B)를 기록해 confidence(B/A)를 구한다.
이렇게 구한 confiednce가 목표치를 만족하면 save_association 함수를 이용해 output file에 저장한다.

탐색을 마친 tuple에 대해서는 right item 하나를 꺼내 left item에 집어넣는 방식으로 새로운 tuple을 생성, 이를 다시 tuple_list에 집어 넣는다. 이 때 tuple은 내부 index를 이용해 중복된 형태의 tuple을 만들지 않게 된다. 해당 작업과 위 작업을 반복해 더 이상 tuple_list에 꺼낼 수 있는 tuple이 존재하지 않는 경우 get_association_support 함수를 종료하도록 한다.

해당 프로젝트는 복수의 Attribute 값 및 Class 값을 가지는 element data set을 학습해, Class값이 없는 새로운 element들에 대해 Class를 구분하는 작업을 시행하는 Decision Tree Algorithm을 만드는 것을 목표로 하였다.

프로젝트에 있어서 Input은 2개 주어졌으며 이는 Train data, 실제 계산할 element가 존재하는 Test data로 나누어 진다.

attribute1    attribute2 ...... attributeN Class(Test data에는 Class 항목이 존재하지 않음)

attr1valueA   attr2valueA   ... attrNvalueC  class A
attr1valueB   attr2valueA   ... attrNvalueA  class B
........

이에 대해 Output은 Test Data에 대해 Class 항목을 추가한 형태로 저장된다.

우선 main 함수는 train data의 첫번째 줄을 읽어 해당 프로그램에서 사용할 attribute name과 Class name을 기록한다. 그 뒤 나머지 줄을 차례대로 읽으면서 element들이 어떤 attribute와 class 값을 가졌는지 elem(element 클래스)객체를 생성, 이를 train_data 배열에 집어넣는다.

또한 해당 작업을 실행하면서 각 attribute와 Class value에는 어느 값들이 있는지 attribute_list 2차원 배열 및 attribute_label 배열에 중복 값을 제외하고 넣어주면서 이를 기록한다. (Line 290-325)

그 뒤 attribute의 종류가 기록된 attribute_list의 크기를 이용해 tree의 root node를 생성하며 여기에 train_data의 index 값들인 train_data_number를 멤버변수 elements에 집어넣어 준다.

그 뒤 make_tree 함수를 통해 root node를 아래로 확장하며, 이렇게 만들어진 Tree에 대해 test data의 element를 집어넣는 것으로 Class 값을 생성한다. 그 후 output file에 대해 결과값을 작성, 이를 모든 element에 대해 반복한 뒤 프로그램을 종료한다. (Line 329-368)

우선 make_tree function은 node 객체를 인자로 받으며, 해당 객체에는 node에 속한 train data들에 index가 존재한다. 우선 index를 이용해 각 element들에 Class 값을 확인, 그 후 node 객체에 있는 upward_attribute 배열 값을 확인한다.
여기에 대해 Class 값이 모두 같거나, upward_attribute 값이 모두 True이면 해당 node는 Tree에서 자식을 갖지 못하는 leaf node로 인식, node의 class 값을 부여해주도록 한다.
이 값은 위 test data의 특정 element가 해당 node에 도달하는 경우 가지게 될 class 값이 된다. 만약 바로 위에서 언급한 두 경우 모두 아닐경우에는 해당 node는 branch node가 되며 child node를 아래와 같이 만들게 된다. (Line 106-150)
(upward_attribute가 무엇인지는 보다 아래에서 설명한다.)

child node를 만들 때, Decision Tree는 얼마나 Class 값을 잘 구분하여 child를 만들 수 있는지가 중요하게 여겨진다.
이를 위해 기존 parent node 내 element의 class value가 어떻게 분포하는지, child node를 만들었을 때 각 node들의 element class value는 어떻게 분포하는지 조사하여 최적의 child node를 만들어야 한다.
이를 위해 parent node의 entropy와 child node의 entropy합을 뺀 Information Gain을 구하고, 모든 child node 경우의 수에 대해 가장 큰 Information Gain을 얻는다. 그리고 이를 통해 Decision Tree는 최적의 child node를 찾을 수 있게 된다. (이는 아래 이미지와 같다)

이를 위해 우선 parent node에 대한 entropy를 구해야하므로 배열 numerator에 내부 element들의 class 분포를 기록, 이를 인자로 준 information_gain 함수를 통해 entropy를 구한다. (Line 152-164)

그 후 attribute_list와 upward_attribute를 이용해 child node를 만들 수 있는 attribute를 선정, 해당 attribute의 종류만큼 element를 배분할 수 있는 coefficient 2차원 배열을 만들고, 그 안에는 현재 element들이 가질 수 있는 class 종류만큼 0 값을 집어 넣는다. 그 뒤 element에서 해당 attribute의 값에 따라 coefficient 배열에서 이동하게 될 위치 및 class value의 위치를 구해 child node에 대한 class 분배 상태를 구한다. (Line 170-190)

그리고 이를 이용해 해당 attribute에 대한 child node entropy를 도출, 모든 attribute 경우의 수에 대한 information gain을 구해 최적의 attribute기준을 도출한다. (Line 192-201)

그리고 이렇게 구한 attribute로 child node를 생성 및 element를 분배, make_tree function으로 각 child node에 대한 child node를 만들어서 전체 Decision tree를 만든다. (Line 204-245)

여기서 사용한 attribute의 index를 이용, child node의 upward_attribute에 해당 값을 True로 만들어 주는데 이는 child의 parent가 해당 attribute를 이용해서 이미 나눠졌다는 것을 표시하고 있다. 따라서 node의 upward_attribute 값이 모두 true이면 더 이상 나눠질 수 없다는 것을 의미, 다수결을 통해 node의 class value를 구해준다.

프로그램은 인자로 input file과 Cluster 갯수, Radius, Minimum point를 순서대로 받는다. 그리고 Input file에 있는 데이터를 Radius, Minimum point를 이용해 DBSCAN Clustering을 진행, Cluster 갯수만큼 나누어 output file에 출력하는 작업을 진행한다.

프로젝트에 있어서 input file은 아래와 같은 형태로 주어지며, output은 Cluster 갯수만큼 작성하며 그 내용은 Cluster에 따라 나눈 object id를 표시한다.

object_id  x_position   y_position
   0	   84.768997	33.368999
   1	   569.791016	55.458
   2	   657.622986	47.035
   3	   217.057007	362.065002

우선 input file에 object data를 집어 넣을 수 있는 2차원 matrix를 생성해야 한다. 이를 위해 우선 input file을 읽어 각 object를 프로그램 메모리에 기록하며, 이 때 최소 x, 최대 x, 최소 y, 최대 y도 같이 프로그램에 기록한다. (Line 245-298)

그 뒤 matrix를 생성해야 하는데, 그 격자를 matrix 2차원 배열에 집어넣는 방식으로 할 것이다. 해당 격자는 matrix_element 클래스 객체로 나타나며 각각 left(min_x), right(max_x), down(min_y), up(max_y) 지점을 가진다. 또한 이 안에 존재하는 point를 담을 수 있는 배열 points 및 point의 숫자, count 변수도 객체에 선언한다. (Line 67-89)

우선 가로로 격자를 넣을 때 얼마나 넣을 지 구하기 위해 위에서 구한 최대 x에서 최소 x를 뺀 뒤 radius로 나누도록 한다.(세로는 이를 y로 계산하도록 한다.) 그리고 2중 반복문을 이용해 격자 객체를 생성, 이를 matrix 배열에 넣어주며 결론적으로 아래와 같은 그림처럼 matrix는 나타나게 된다. (Line 307-329)

point를 격자에 넣어줄 때, 2차원 배열 matrix에서 격자를 넣어줄 때 사용한 비율로 x, y 값을 보정하는 작업이 필요하다. 이를 위해 각 point에 접근, point 내 x,y에 대해 최소 x,y를 빼준 뒤 radius로 나눠서 보정한 값을 구한다. 그리고 이를 이용해 matrix 내 격자에 해당 point를 집어넣어주도록 한다. (Line 91-109)

그 뒤 db_scan을 진행해야 하는데 우선 db_scan_core_point 함수를 이용해 core point를 찾도록 한다. 해당 함수는 우선 point에 접근, 해당 point의 cluster가 할당되지 않았으면서 outlier인 경우이면 주변 point 탐색을 진행한다. 이러한 탐색은 해당 point가 존재하는 격자 및 주변 8방향 격자 내 point를 조사하여 거리를 구하는 방식으로 진행되며, 그 거리가 radius 이하인 point가 minimum point 숫자 이상인 경우 core point로 지정한다. 그리고 자기 자신 및 주변 point의 cluster를 cluster number로 지정해준다. (Line 129-163)

위 core point 주변 point를 저장한 배열 cluster_pt_area에 대해 db_scan_check_point를 진행한다. db_scan_check_point도 core point 탐색과 같이 8방향 및 자신의 격자 내 point를 조사해 조건을 만족하는 point를 찾아 minimum point를 넘는지 확인하도록 한다. 그런 경우이면 이 놈도 core point가 되지만 cluster는 이미 할당되어 있으므로, 자기 주변 point 중 cluster가 할당되지 않은 point를 찾아 cluster 할당, cluster_pt_area에 집어 넣어주도록 한다. (Line 180-226)

그 뒤 db_scan_core_point는 cluster_pt_area의 다음 point를 찾아 db_scan_check_point를 진행, 이를 cluster_pt_area 내 모든 point에 대해 시행한다. 그리고 모든 point를 순회했으면 output file을 생성해 cluster에 속한 object_id를 file에 기록해준다. 이러한 과정을 목표로 하는 cluster 숫자를 충족할 때 까지 반복한다. (Line 166-176)