[논문]트랜잭션 데이터 분석을 위한 확률 그래프 모형

안길승; 허선

doi:10.7232/jkiie.2016.42.4.249

트랜잭션 데이터 분석을 위한 확률 그래프 모형
Probabilistic Graphical Model for Transaction Data Analysis 원문보기

대한산업공학회지 = Journal of the Korean Institute of Industrial Engineers, v.42 no.4, 2016년, pp.249 - 255

안길승 (한양대학교 산업경영공학과) , 허선 (한양대학교 산업경영공학과)

Abstract ▼ AI-Helper

Recently, transaction data is accumulated everywhere very rapidly. Association analysis methods are usually applied to analyze transaction data, but the methods have several problems. For example, these methods can only consider one-way relations among items and cannot reflect domain knowledge into analysis process. In order to overcome defect of association analysis methods, we suggest a transaction data analysis method based on probabilistic graphical model (PGM) in this study. The method we suggest has several advantages as compared with association analysis methods. For example, this method has a high flexibility, and can give a solution to various probability problems regarding the transaction data with relationships among items.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

이에 본 연구에서는 연관분석의 문제점을 보완할 수 있도록 대표적인 확률 그래프 모형인 마코프 네트워크(Markov network) 기반의 트랜잭션 분석 방법론을 제안한다. 그리고 본 연구에서 제안하는 방법론의 활용 방안과 성능 평가 방안에 대해 제시한다. 특히, 성능 평가는 비지도 학습(unsupervised learning)인 연관분석에서 불가능한 내용이다.
본 연구는 트랜잭션 데이터를 분석하는데 주로 쓰여왔던 방법론인 연관분석이 가지고 있는 여러 문제를 확률 그래프 모형을 이용하여 해결하였다는 데 그 의의가 있다. 구체적으로, 일반화가 불가능하여 분류나 예측할 수 없다는 문제, 도메인 지식을 반영하기 어렵다는 문제, 특정 규칙을 일관되게 평가할 기준이 없다는 문제를 해결하였다.
본 연구에서는 최근 다양한 분야에서 엄청난 속도로 축적되고 있는 트랜잭션 데이터를 분석하기 위해, 마코프 네트워크 기반의 방법론을 제안하였다. 해당 방법론에서 아이템 간의 유사도를 PMI를 이용하여 계산하여 유사도 행렬을 구성하였고, 이를 바탕으로 이웃과 클리크를 정의하였다.
예를 들어, Han(2009)에서는 단백질의 기본 단위체인 도메인의 조합을 찾아내는데 연관분석을 적용하였다. 이 연구에서는 연관분석은 단방향의 규칙만 생성하기 때문에, 도메인 조합이 제한적일 수밖에 없다는 사실을 지적하였다. 그들은 이러한 문제를 해결하기 위해 all-confidence를 정의함으로써 양방향성의 규칙을 생성할 수 있는 연관분석을 수행하였다.
이에 본 연구에서는 연관분석의 문제점을 보완할 수 있도록 대표적인 확률 그래프 모형인 마코프 네트워크(Markov network) 기반의 트랜잭션 분석 방법론을 제안한다. 그리고 본 연구에서 제안하는 방법론의 활용 방안과 성능 평가 방안에 대해 제시한다.

제안 방법

‘Anonymous Microsoft Web Data’는 임의로 선정된 4,183명의 사용자가 일주 일간 방문한 사이트 목록이며, 본 연구에 제안한 방법론에 적용하기 위해 데이터의 구조를 [Table 1]과 같이 트랜잭션 데이터 세트 형태로 변경하였다.
이 장에서는 본 연구에서 제안하는 알고리즘을 예시한다. 또한, 그 성능을 판단하기 위해 실제 데이터에 적용하여 실험하고 그 결과를 평가한다.
마지막으로 각 클리크에 포텐셜 함수를 정의하고 학습시킴으로써 마코프 네트워크를 완성하였다. 또한, 방법론 제시에서 그치는 것이 아니라 본 연구에서 제안한 모형을 실제로 적용하는 데 도움이 될 수 있도록 관련 예제를 제시하였다.
즉, 아이템 i₁과 i₂를 같이 구매한 비율을 나타낸다. 본 연구에서는 이러한 개념을 아이템 간의 유사도를 계산하는 데 활용한다.
이에 유사도 임계치 α를 0.6으로 설정하여 유사도가 임계치 이상인 두 사이트를 이웃으로 정의한 뒤, 최대클리크를 탐색하였다.
본 연구에서는 최근 다양한 분야에서 엄청난 속도로 축적되고 있는 트랜잭션 데이터를 분석하기 위해, 마코프 네트워크 기반의 방법론을 제안하였다. 해당 방법론에서 아이템 간의 유사도를 PMI를 이용하여 계산하여 유사도 행렬을 구성하였고, 이를 바탕으로 이웃과 클리크를 정의하였다. 마지막으로 각 클리크에 포텐셜 함수를 정의하고 학습시킴으로써 마코프 네트워크를 완성하였다.

대상 데이터

실험에 사용한 데이터 세트는 ‘Anonymous Microsoft Web Data’와 ‘Extend Bakery Dataset’으로 각각 UCI Machine Learning Repository(https://archive.ics.uci.edu/ml/datasets)와 Trac(https://wiki. csc.calpoly.edu/datasets/wiki/apriori)에서 획득하였다.
원 데이터에는 총 1,000개의 레코드를 포함하고 있으나, 본 연구에서 제안한 방법론의 성능을 객관적으로 평가하기 위해 70%와 30%의 비율로 나누어 학습데이터 세트와 검증데이터 세트를 구성하였다.

이론/모형

이 때 최적화해야 하는 함수에 포함된 변수가 206개나 되므로 내리막(또는 오르막) 경사법 등을 비롯한 분석적 풀이를 적용하기에는 현실적으로 어려운 점이 많다. 따라서 본 연구에서는 대표적인 메타 휴리스틱 알고리즘인 시뮬레이티드 어닐링(simulated annealing)을 사용하여 가중치를 추정하였으며, 추정한 결과 일부를 [Table 3]에 제시하였다.

성능/효과

계산 결과에서 보듯이, 본 연구에서 제안하는 방법론과 다르게 연관분석의 결과는 데이터에 매우 민감한 것을 알 수 있다. 즉, 학습 데이터 세트에서 계산한 지지도(0.
본 연구는 트랜잭션 데이터를 분석하는데 주로 쓰여왔던 방법론인 연관분석이 가지고 있는 여러 문제를 확률 그래프 모형을 이용하여 해결하였다는 데 그 의의가 있다. 구체적으로, 일반화가 불가능하여 분류나 예측할 수 없다는 문제, 도메인 지식을 반영하기 어렵다는 문제, 특정 규칙을 일관되게 평가할 기준이 없다는 문제를 해결하였다.
셋째, 포텐셜 함수(potential function)를 통해 도메인 지식을 반영할 수 있다. 넷째, 각 포텐셜 함수에 부여된 가중치를 통해 일관되게 규칙을 평가할 수 있다.
둘째, 결합확률분포를 제공하기 때문에 이를 변형하면 특정 아이템의 등장 확률과 조건부 확률 등을 계산하는데 응용할 수 있다. 셋째, 포텐셜 함수(potential function)를 통해 도메인 지식을 반영할 수 있다. 넷째, 각 포텐셜 함수에 부여된 가중치를 통해 일관되게 규칙을 평가할 수 있다.
0162)의 차이가 크다. 이에 반해 본 연구에서 제안한 방법론을 사용하면 학습 데이터 세트에서 계산한 지지도는 0.0021이고 신뢰도는 0.0153으로, 평가데이터 세트에서 계산한 지지도 및 신뢰도와의 차이가 매우 작아서 데이터에 비교적 강건하다고 할 수 있다.
확률 그래프 모형을 다음과 같은 이유로 연관분석 대신 트랜잭션 데이터 분석에 적용할 수 있다. 첫째, 도메인이 같다면 일반화가 가능하며, 이러한 점을 이용하여 예측이나 분류를 수행할 수 있다. 둘째, 결합확률분포를 제공하기 때문에 이를 변형하면 특정 아이템의 등장 확률과 조건부 확률 등을 계산하는데 응용할 수 있다.
6으로 설정하여 유사도가 임계치 이상인 두 사이트를 이웃으로 정의한 뒤, 최대클리크를 탐색하였다. 탐색결과, 최대클리크는 총 100개였으며, 대부분의 최대클리크 크기는 3이었다. 아이템 간 연결을 나타내는 네트워크 구조는 [Figure 3]에 제시하였다.

후속연구

상품 추천 시스템 설계와 관련된 연구로, 연관규칙을 이용하여 웹상에서의 상품 추천 시스템을 구현한 연구(Park, 2005)를 들 수 있다. 그러나 이 연구에서는 트랜잭션 내 출현횟수가 적은 아이템에 관해서는 추천을 수행하지 못했다는 한계가 있다.
첫째, 도메인이 같다면 일반화가 가능하며, 이러한 점을 이용하여 예측이나 분류를 수행할 수 있다. 둘째, 결합확률분포를 제공하기 때문에 이를 변형하면 특정 아이템의 등장 확률과 조건부 확률 등을 계산하는데 응용할 수 있다. 셋째, 포텐셜 함수(potential function)를 통해 도메인 지식을 반영할 수 있다.
따라서 추후 연구에서는 제안된 방법을 실제 분석에 응용하기 위해, 유사도 임계치를 객관적으로 설정하는 방법과 가능한 확률들을 계산하고 그 값을 내림차순으로 정렬하여 산출하는 등의 자동화된 방법을 개발하여 본 연구에서 제안된 방법을 보완한다. 이 방법은 관심 있는 다양한 확률들을 계산할 뿐 아니라 지지도나 신뢰도를 기준으로 상위 규칙을 정리하여 보여줄 수 있다.
하지만 본 연구에서 제안하는 방법은 이웃을 정의하기 위한 유사도 임계치를 객관적으로 설정하기 어렵다는 한계가 있다. 마지막으로 본 연구에서 제안하는 방법은 규칙을 평가하기에만 적합하다는 한계가 있는데, 이는 연관분석의 apriori 알고리즘과 비교하여 보면 빈발 항목 집합 생성에서 멈춘 것과 같다. 물론 관심 있는 다양한 확률값을 계산할 수 있는 모델을 생성할 수 있으나, 그 관심 대상을 정하는 부분이 없으므로 규칙 생성에는 부적합하다.
하지만 본 연구에서 제안하는 방법은 이웃을 정의하기 위한 유사도 임계치를 객관적으로 설정하기 어렵다는 한계가 있다. 마지막으로 본 연구에서 제안하는 방법은 규칙을 평가하기에만 적합하다는 한계가 있는데, 이는 연관분석의 apriori 알고리즘과 비교하여 보면 빈발 항목 집합 생성에서 멈춘 것과 같다.

질의응답

핵심어	질문	논문에서 추출한 답변
	세계 전자 상거래의 시장이 클 수 있었던 이유는?	트랜잭션 데이터(transaction data)란 은행에서의 고객의 입출금, 상점에서의 고객의 주문, 웹에서의 사용자의 클릭 등을 기록한 데이터를 말한다. 스마트폰의 활성화와 핀테크의 출현 등으로 세계 전자 상거래의 시장이 꾸준히 커가고 있으며(전자 상거래를 이용한 세계 B2C 거래액은 2013년 1조 2천억 달러, 2014년 1조 5천억 달러이며 2018년에는 2조 4천억 달러까지 증가할 전망(eMarketer, 2014)), 이로 인해 트랜잭션 데이터는 엄청난 속도로 쌓여갈 것이라 기대된다.
	연관분석을 이용한 트랜잭션 데이터 분석에는 어떠한 문제가 있을 수 있는가?	그러나 연관분석을 이용한 트랜잭션 데이터 분석에는 몇 가지 문제가 있다. 예를 들어, 연관분석은 탐색적 자료 분석 방법이므로 수리적인 모형이 존재하지 않아 일반화가 불가능하다. 또한, 특정 분야의 도메인 지식(domain knowledge)을 반영하기 어려우며, 연관분석의 결과로 생성되는 규칙을 일관되게 평가할 만한 기준이 없다.
	트랜잭션 데이터란?	트랜잭션 데이터(transaction data)란 은행에서의 고객의 입출금, 상점에서의 고객의 주문, 웹에서의 사용자의 클릭 등을 기록한 데이터를 말한다. 스마트폰의 활성화와 핀테크의 출현 등으로 세계 전자 상거래의 시장이 꾸준히 커가고 있으며(전자 상거래를 이용한 세계 B2C 거래액은 2013년 1조 2천억 달러, 2014년 1조 5천억 달러이며 2018년에는 2조 4천억 달러까지 증가할 전망(eMarketer, 2014)), 이로 인해 트랜잭션 데이터는 엄청난 속도로 쌓여갈 것이라 기대된다.

참고문헌 (15)

Ahn, G.-S. and Hur, S. (2015), Prediction of New Customer's Degree of Loyalty of Internet Shopping Mall Using Continuous Conditional Random Field, Journal of Korean Institute of Industrial Engineers, 41(1), 10-16.

원문보기 상세보기
Bron, C. and Kerbosch, J. (1973), Algorithm 457 : Finding All Cliques of an undirected Graph, Communications of the ACM, 16(9), 575-577.

상세보기
Chen, Y. and Welling, M. (2014), Bayesian structure learning for Markov random fields with a spike and slab prior, arXiv preprint, arXiv : 1408.2047.
eMarketer (2014), Worldwide E-commerces Sales to increase Nearly 20% in 2014.
Fuguang, B. (2015), A Novel Method of Interestingness Measures for Association Rules Mining Based on Profit, Discrete Dynamics in Nature and Society, 1-10.
Han, D.-S. (2009), Identification of Conserved Protein Domain Combination based on Association Rule. Journal of KIISE : Computing Practices and Letters, 15(5), 375-379.
Informationweek (2012), Catalina Marketing Aims For the Cutting Edge of 'Big Data.'
Jordan, M. I. (1999), Learning in Graphical Models, MIT Press, Massachusetts, USA.
Kim, N.-K. (2008), Effect of Market Basket Size on the Accuracy of Association Rule Measures, Asia Pacific Journal of Information Systems, 18(2), 95-114.
Kolaczyk, E. (2009), Statistical Analysis of Network Data, Springer, Boston, USA.
Park, D.-S. (2005), A Visualization on Data Mining for Association based on Web, Journal of Korean Institute of Information Technology, 3(4), 1-9.
Rajtmajer, S. M. (2012), Introduction to Markov Random Fields.
Son, J.-E., Kim, S.-B., Kim, H.-J., and Cho, S.-Z. (2015), Review and Analysis of Recommender Systems, Journal of Korean Institute of Industrial Engineers, 41(2), 185-208.

원문보기 상세보기
Turney, P. D. (2002), Thums up or thums down?: semantic orientation applied to unsupervised classification of reviews, In Proceedings of the 40th annual meeting on association for computational linguistics, 417-424.
Yang, S.-M. (2003), Discovery of Association Rules Based on items of Categorical Attribute and Quantitative Attribute, Proceedings of Korean Institute of Information Technology, 456-461.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증