[논문]데이터마이닝을 위한 사후확률 정보엔트로피 기반 군집화알고리즘

박인규

doi:10.14400/jdc.2014.12.12.293

데이터마이닝을 위한 사후확률 정보엔트로피 기반 군집화알고리즘
Clustering Algorithm for Data Mining using Posterior Probability-based Information Entropy 원문보기

디지털융복합연구 = Journal of digital convergence, v.12 no.12, 2014년, pp.293 - 301

초록
AI-Helper

본 논문에서는 데이터 마이닝에 필요한 클러스터링과정에서 불필요한 정보를 감축하기 위하여 베이지언 사후확률의 신뢰도를 이용한 새로운 척도를 제안한다. 데이터 감축을 위한 속성의 중요도가 클러스터링의 결과에 지배적이기 때문에 많은 속성의 변별력을 향상시키기 위하여 사후확률의 신뢰도에 정보 엔트로피를 적용하였다. 제안된 사후확률을 기반으로 한 러프 엔트로피 척도에 의한 속성의 신뢰도의 중복성은 엔트로피의 자연로그에 의하여 상당히 줄어든다. 따라서 제안된 척도에 의하여 생성된 군집화 알고리즘은 속성값의 변별력을 향상시켜 기존의 리덕트를 최소화하였고, 이는 분할의 효율성을 향상시킬 수 있었다. 제안된 알고리즘의 검증을 위해 패턴분류 문제에 적용되는 ACME 데이터에 대하여 속성간의 변별력, 분할결과에 따른 분할의 순정도를 기존의 알고리즘과 비교 분석하였다.

Abstract ▼ AI-Helper

In this paper, we propose a new measure based on the confidence of Bayesian posterior probability so as to reduce unimportant information in the clustering process. Because the performance of clustering is up to selecting the important degree of attributes within the databases, the concept of information entropy is added to posterior probability for attributes discernibility. Hence, The same value of attributes in the confidence of the proposed measure is considerably much less due to the natural logarithm. Therefore posterior probability-based clustering algorithm selects the minimum of attribute reducts and improves the efficiency of clustering. Analysis of the validation of the proposed algorithms compared with others shows their discernibility as well as ability of clustering to handle uncertainty with ACME categorical data.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 베이지언 사후확률을 기반으로 한 러프엔트로피를 이용하여 범주형 데이터에서 중요한 정보를 추출하는 알고리즘을 제안한다. 제안된 알고리즘에서는 속성간의 중요도를 사후확률의 신뢰도를 정보 엔트로피 개념으로 정의하여 속성간의 변별력을 향상시켜 데이터를 분할하고자 한다.
속성의 범주 개수는 공히 2가지(yes/no)이다. 실험의 목적은 10개의 객체들을 유사한 객체끼리 분류하는 실험이다. [Table 1]은 ACME회사의 신용카드 판촉 데이터베이스의 일부로써 잡지판촉(MP: magazine promotion), 시계판촉(WP: watch promotion), 생명보험 판촉(LIP: insurancne life promotion), 신용카드 보험 판촉(CCI: credit card insurance promotion)와 성별(S: sex)로 구성되어 있다.
이는 속성의 변별력을 떨어트리는 원인으로 작용하여 객체들의 원래의 클러스터에 대해 분할된 틀러스터의 순정도(purity)가 떨어지게 되어 시간복잡도(time complecity)가 증가하는 결과를 초래하게 된다. 이러한 단점을 극복하기 위하여 본 논문에서는 사후확률의 신뢰도에 정보 엔트로피(information entropy)를 적용하여 속성의 변별력을 향상시켰다[8].
그러나 이러한 기준에 의한 속성은 동일한 값을 가지는 경우가 발생하여 속성간의 변별력이 저조하게 된다. 이러한 단점을 극복하기 위하여 사후확률과 엔트로피 개념을 이용한 새로운 척도를 제안한다. 조건부 확률에서는 새로운 정보를 알았을 경우에 확률의 개선이 발생하게 된다.

제안 방법

객체의 분할을 위하여 본 논문에서는 분할정복(divide and conquer)을 이용하여 각각의 알고리즘에 따라서 세번의 분할을 수행한 결과를 [Table 9]부터 [Table 15]까지 나타내었다. 예를 들어, MMR 에서는 속성별로 거침이 작은 값을 기준으로 분할속성을 추출하는 과정에서 속성에 대한 척도가 동일한 값에 대하여 인접하는 다른 값을 기준으로 판별하기 때문에 [Table 3]에서와 같이 분할속성은 {CCI} – {LIP} - ({MP} – {S} – {WP}) 순으로 추출된다.
데이터들이 가지고 있는 속성의 수가 대량으로 존재하는 빅데이터의 경우에는 이들을 효과적으로 줄이는 게 관건이다. 방대한 데이터 베이스의 효율적인 운영방안으로 속성감축을 위한 일환으로써 범주형 데이터를 구성하는 여러 가지의 속성에서 보다 지배적인 속성을 추출하기 위하여 사후확률을 기반으로 하는 새로운 엔트로피척도를 정의하였다. 속성간에 숨어있는 불필요한 정보를 효과적으로 제거하여 가장 영향력이 있는 속성을 추출하기 위하여 엔트로피 개념을 적용하여 변별력을 향상시켰다.
방대한 데이터 베이스의 효율적인 운영방안으로 속성감축을 위한 일환으로써 범주형 데이터를 구성하는 여러 가지의 속성에서 보다 지배적인 속성을 추출하기 위하여 사후확률을 기반으로 하는 새로운 엔트로피척도를 정의하였다. 속성간에 숨어있는 불필요한 정보를 효과적으로 제거하여 가장 영향력이 있는 속성을 추출하기 위하여 엔트로피 개념을 적용하여 변별력을 향상시켰다. 또한 제안된 척도의 효율성을 검증하기 위하여 제안된 척도를 이용한 속성 감축 알고리즘을 기존의 여러 가지 방법들과 비교하였다.
결국, 속성의 중복성은 분할의 안정도와 관계가 밀접하다고 할 수 있다. 순정도는 두 번째(2nd)와 세 번째(3rd)의 분할에 대하여 측정하였고 전체적인 순정도를 구하였다. 특히, MMR 의 경우에는 속성의 동일한 값에 의하여 0.
따라서 분할속성은 PPE^mi에 의하여 {LIP}가 된다. 이와 같이 분할속성이 결정되면 속성에 대해 이분 분할(binary split)이 경험적인(heuristic) 방법으로 진행되는데, 본 논문에서는 최소값을 이용하여 가장 작은 PPE를 가지는 범주를 하나의 범주로 결정하고 다른 범주를 통합하여 다른 하나의 범주로 결정한다.
제안된 방법에서는 {LIP} – {S} – {MP} – {CCI} –{WP} 이다.
실험결과로는 속성간의 대표적인 속성을 추출하기 위하여 각각의 방법에 따른 척도의 결과와 속성의 중요도에 따른 분할결과 뿐만 아니라 분할된 결과에 대한 분할 순정도(purity)의 결과를 보인다. 제안된 방법의 비교우위를 위하여 사용한 기존의 방법들은 MMR(minimum minimum roughness), SDR(standard deviation of roughness), SSDR(standard deviation of standard deviation of roughness), SSDD(standard deviation of standard deviation of degree of dependency)의 네 가지의 알고리즘으로 구성되어 있다.
본 논문에서는 베이지언 사후확률을 기반으로 한 러프엔트로피를 이용하여 범주형 데이터에서 중요한 정보를 추출하는 알고리즘을 제안한다. 제안된 알고리즘에서는 속성간의 중요도를 사후확률의 신뢰도를 정보 엔트로피 개념으로 정의하여 속성간의 변별력을 향상시켜 데이터를 분할하고자 한다.
클러스터링을 위한 분할속성을 결정하기 위하여 속성 간의 정성적인 기준(quality metric)으로 Mazlak은 전체적인 거침(total roghness)을 이용하였고, Parmar는 평균 거침(mean roughness)을 제안하였다. 그러나 이러한 기준에 의한 속성은 동일한 값을 가지는 경우가 발생하여 속성간의 변별력이 저조하게 된다.

대상 데이터

본 연구에서 제안하는 PPE알고리즘에 대한 분할을 검증하기 위하여 패턴분류에 대한 데이터로 [Table 1]의 신용카드 판촉 데이터를 선정하였다. 실험을 위하여 구현한 프로그램은 Windows 8환경에서 Matlab R2014a를 사용하였다.

데이터처리

속성간에 숨어있는 불필요한 정보를 효과적으로 제거하여 가장 영향력이 있는 속성을 추출하기 위하여 엔트로피 개념을 적용하여 변별력을 향상시켰다. 또한 제안된 척도의 효율성을 검증하기 위하여 제안된 척도를 이용한 속성 감축 알고리즘을 기존의 여러 가지 방법들과 비교하였다. ACME 신용카드회사의 데이터를 통한 분석결과 속성간의 변별력이 기존의 방법보다 우수하여 양호한 분할결과를 얻을 수 있었다.

성능/효과

또한 제안된 척도의 효율성을 검증하기 위하여 제안된 척도를 이용한 속성 감축 알고리즘을 기존의 여러 가지 방법들과 비교하였다. ACME 신용카드회사의 데이터를 통한 분석결과 속성간의 변별력이 기존의 방법보다 우수하여 양호한 분할결과를 얻을 수 있었다.
PPE가 적을수록 클러스터링의 안정성이 높아진다. PPE^mi를 통하여 안정성이 높은 속성의 범주를 알 수 있고, PPE^mm가 가장 안정성이 우수한 속성을 결정한다. [Table 2]의 PPE^mm알고리즘을 실험하기 위한 데이터가 [Table 1]에 나타나있다.
SDR 과 SSDR 에서는 동일한 분할 결과를 보였고 {LIP} 를 제외한 모든 속성 값이 동일하기 때문에 분할의 안정성이 떨어질 수 있다. SSDS 와 SSDD 의 경우와 제안된 방법에서는 속성값의 중복성을 발경할 수 없었다. 이는 SSDS와 SSDD의 경우는 표준편차에 의해서 변별력을 유지하였고 제안한 방법의 경우에는 엔트로피를 이용하여 변별력을 유지하였다.
70까지 다양한 순정도를 나타내었다. 결과적으로 [Fig. 2]를 통하여 볼 때, 기존의 방법에 비하여 제안된 방법이 0.788로 전체적인 순정도가 향상되어 MMR의 불안정한 경우를 제외하면 기존의 방법에 비하여 제안된 방법이 우수함을 확인 할 수 있었다.
이러한 일환으로 러프집합의 roughness에 의한 범주형 데이터를 분할하는 Minimum Minimum Roughness(MMR) 알고리즘이 Parmar 에 의하여 제안되었다[7]. 또한 이 알고리즘은 Tripathy 에 의하여 여러 가지 이질적인 데이터를 다룰 수 있도록 Minimum Mean Roughness(MMeR)로 확장되었고, 이는 SDR(standard deviation roughness)과 SSDR(standard deviation of standad deviation roughness) 으로 확장되었다. 또한 SDR을 기반으로 속성간의 중요도(significance)와 의존도(dependency)를 이용한 SSDS(standard deviation of standad deviation significance)와 SSDD(standard deviation of standad deviation dependency)가 제안되었다[11,12,13].
SSDS 와 SSDD 의 경우와 제안된 방법에서는 속성값의 중복성을 발경할 수 없었다. 이는 SSDS와 SSDD의 경우는 표준편차에 의해서 변별력을 유지하였고 제안한 방법의 경우에는 엔트로피를 이용하여 변별력을 유지하였다. SDR과 SSDR에 의한 속상의 분할 순서는 {LIP} – ({MP} – {WP} - {CCI} – {S}) 이고, SSDS 에서는 {WP} – {MP} – {LIP} – {S} – {CCI} 이고 SSDD에서는 {MP} – {WP} – {LIP} – {CCI} – {S} 이다.

후속연구

또한 제안된 사후확률에 의한 엔트로피 척도는 의사 결정 시스템이 일관적인(consistent) 시스템은 물론이고 비일관적인(incinsistent) 시스템에도 적용가능하기 때문에 학생들의 취업지도와 역량강화와 같은 분야에 적용하면 메타데이터로서의 정보를 제시할 수 있을 것이다. 향후 제안된 척도를 불완전한 시스템으로 확장하여 분석할 필요가 있다고 사료된다.
또한 제안된 사후확률에 의한 엔트로피 척도는 의사 결정 시스템이 일관적인(consistent) 시스템은 물론이고 비일관적인(incinsistent) 시스템에도 적용가능하기 때문에 학생들의 취업지도와 역량강화와 같은 분야에 적용하면 메타데이터로서의 정보를 제시할 수 있을 것이다. 향후 제안된 척도를 불완전한 시스템으로 확장하여 분석할 필요가 있다고 사료된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	데이터마이닝이란 무엇인가?	데이터마이닝은 방대한 양의 데이터에 존재하는 관계, 패턴, 규칙과 같은 정보를 찾아내어 이를 기반으로 한 모형화(modeling)를 통하여 의사결정에 관계하는 정보로 일련의 변환과정이라고 말할 수 있다. 이는 임의의 의사결정을 위한 정보추출 과정으로써 추출된 정보는 많은 양의 데이터를 설명하는 역할을 하고 있으며 예측적 모델링과 탐색적 모델링에서 여러 가지 방법으로 사용되어 진다.
	범주형 데이터를 처리하기 위한 알고리즘으로 제안된 것은 무엇인가?	반면에 범주형의 데이터는 다치논리(multi-valued logic)를 가지기 때문에 속성간의 거리가 존재하지 않기 때문에 범주형 데이터를 처리하기 위한 알고리즘으로는 Expectation-Maximization, K-means 와 Fuzzy c-means 알고리즘이 제안되었다. 또한, 클러스터 해석을 기반으로 하는 알고리즘으로 MMR(min-min robustness), STIRR(sieving through iterated relational reinforcement)과 Rock(robust clustering using links) 등이 제안되었지만[4], 클러스터간의 경계가 확실하지 않기 때문에 불확실성(uncertainty)을 처리하는 데에는 어려움이 있다.
	데이터마이닝은 어디에 사용되는가?	데이터마이닝은 방대한 양의 데이터에 존재하는 관계, 패턴, 규칙과 같은 정보를 찾아내어 이를 기반으로 한 모형화(modeling)를 통하여 의사결정에 관계하는 정보로 일련의 변환과정이라고 말할 수 있다. 이는 임의의 의사결정을 위한 정보추출 과정으로써 추출된 정보는 많은 양의 데이터를 설명하는 역할을 하고 있으며 예측적 모델링과 탐색적 모델링에서 여러 가지 방법으로 사용되어 진다. 특히 탐색적 모델링에서는 의사결정나무(decioin tree), 회귀분석(regression analysis), 인공신경망(artificial intelligence) 과 클러스터링(clustering) 등이 있다[1].

참고문헌 (16)

Dempster A P., Laird N M., Rubin D B., Maximum likelihood from incomplete data via the EM algirithm, Journal of the Royal Statistical Society, Vol. 39, No. 1, pp. 1-38, 1977
Gibson D., Kleindeberg J., Raghvan P., Clustering categorical data: An approach based on dynamical systems, The Very Large Data Bases Journal, vol. 8, no. 3-4, pp. 222-236, 2000

상세보기
Jiang D., Tang C., Zhang A., Cluster analysis for gene expression data: A survey, IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 11, pp. 1370-1386, 2004

상세보기
Herawan T., Ghazali R., Yanto I., Deris M., Rough set approach for cateforical data clustering, International Journal of Database Theory and Application, vol. 3, no. 1, pp. 33-52, 2010
Huang Z, Extensions to the k-means algorithm for clustering large data sets with cateforical values. Data Mining and Knowledge Discovery, vol. 2, no. 3, pp. 283-304, 1998
Kim D., Lee K., Lee D., Fussy clustering of categorical data using fuzzy centroids, Pattern Recognition Letters, vol. 25, no. 11, pp. 1263-1271, 2004

상세보기
Parmar D., Wu T., Blackhurst J., MMR: An algorithm for clustering categorical data using rough set throry, Data and Knowledge Engineering, vol. 63, pp. 879-893, 2007

상세보기
Sun, L., Xu, J., Xue, Z. and Zhang, L., Rough entropy-based feature selection and its application, Journal of Information and Computational Science, pp. 1525-1532, 2011
Anjana K., Study on Naive Bayesian classifier and its relaton to information gain, International Journal on Recent and Innovation Trends in Computing and Communication, vol. 2, pp. 601-603, 2014
Pawlak, Z. Rough set Theory and Its Applications to Data Analysis, Cyberdynamics and Systems: An International Journal, pp. 661-688, 1998
Tripathy B. K., Ghosh A., A SDR: An algorithm for clustering categorical data using rough set theory, Private communication at the International IEEE Conference held in Kerala, 2011
Tripathy B. K., Ghosh A., A SSDR: An algorithm for clustering categorical data using rough set theory, Advances in Applied Science Research, vol. 2, no. 3, pp. 320-324, 2011
Hassanein W. A., Elmelegy A. A., Clustering algorithm for categorical data using concepts of significance and dependence of attributes, European Scientific Jouranl, vol. 10, no. 3, pp. 381-400, 2014
Fuyuan C., Jiye L., Deyu L., Chuangyin D., A dissimility measure for the k-Modes clustering algorithm, Knowledge-Based Systems Journal, vol. 26, pp. 120-127, 2012

상세보기
Tian B. Kulikowski C.A., Leiguang G., Bin Y., Lan H., Chunguang Z., Chinese Journal of Electronics, vol. 21, no. 3, pp. 460-465, 2012
Mete Ciilngirturk A., Ergut O., Hierarchical clustering with simple matching and joint entropy dissimility measure, Journal of Modern Applied Statiscal Methods, vol. 13, no. 1, pp. 329-338, 2013

저자의 다른 논문 :

표제어: 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

연합인증