[논문]빅 데이터의 자율 속성 감축을 위한 확장된 정보 엔트로피 기반 상관척도

박인규

doi:10.7583/jkgs.2018.18.1.105

빅 데이터의 자율 속성 감축을 위한 확장된 정보 엔트로피 기반 상관척도
Extended Information Entropy via Correlation for Autonomous Attribute Reduction of BigData 원문보기

한국게임학회 논문지 = Journal of Korea Game Society, v.18 no.1, 2018년, pp.105 - 114

초록
AI-Helper

고객 유형 분석에 쓰이는 다양한 데이터 분석 방법은 고객들을 위한 맞춤형 콘텐츠를 기획하고, 보다 편리한 서비스를 제공하기 위하여 고객들의 유형과 특성을 정확히 파악하는 것이 매우 중요하다. 본 논문에서는 정보의 손실을 줄이기 위한 일환으로 정보 엔트로피를 확장하여 속성의 불확실성을 이용한 k-modes 군집분석 알고리즘을 제안한다. 따라서 속성에 대한 유사도의 측정은 두 가지의 측면에서 고려되어진다. 하나는 각 분할의 중심에 대한 각 속성간의 불확실성을 측정하는 것이고, 다른 하나는 각 속성이 가지는 불확실성에 대한 확률적 분포에 대한 불확실성을 측정하는 것이다. 특히 속성내의 불확실성은 속성의 엔트로피를 확률적 정보로 변환하여 불확실성을 측정하기 때문에 최종적인 불확실성은 비확률적인 척도와 확률적인 척도에서 고려되어 진다. 여러 실험과 척도를 통하여 제안한 알고리즘의 정확도가 최적의 초기치를 기반으로 군집분석을 수행한 결과에 준수함을 보인다.

Abstract ▼ AI-Helper

Various data analysis methods used for customer type analysis are very important for game companies to understand their type and characteristics in an attempt to plan customized content for our customers and to provide more convenient services. In this paper, we propose a k-mode cluster analysis algorithm that uses information uncertainty by extending information entropy to reduce information loss. Therefore, the measurement of the similarity of attributes is considered in two aspects. One is to measure the uncertainty between each attribute on the center of each partition and the other is to measure the uncertainty about the probability distribution of the uncertainty of each property. In particular, the uncertainty in attributes is taken into account in the non-probabilistic and probabilistic scales because the entropy of the attribute is transformed into probabilistic information to measure the uncertainty. The accuracy of the algorithm is observable to the result of cluster analysis based on the optimal initial value through extensive performance analysis and various indexes.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서 제안하는 확장된 정보 엔트로피를 이용한 분할 알고리즘을 통하여 공간내의 부분적인 정보뿐만 아니라 공간내의 분포를 고려하여 최적화된 속성의 가중치를 측정하고자 한다. 속성이 가지는 불확실성을 정보 엔트로피를 이용하여 측정하고 여기에 잡음 데이터로 인한 속성의 정보를 필터링할 수 있는 확률적 정보 엔트로피를 혼합하여 불확실성을 최적화 한다.
본 논문에서는 군집화에 필수적인 속성간의 유사도를 계측할 수 있는 척도를 비확률적인 조건부 엔트로피를 기반으로 제안하였다. 이에 대한 적용을 두 단계로 구분하여 속성들간에 적용하였고 속성과 모드간에 적용하였다.
본 논문에서는 범주형 데이터의 불확실성을 측정하기 위하여 범주형 데이터에서 임의의 속성의 인접속성들에 대한 각각의 엔트로피와 각 엔트로피의 확률분포를 통하여 유효한 속성과의 관계는 늘리고 그렇지 않은 속성과의 관계는 줄이는 확장된 엔트로피(E)를 다음과 같이 구성하였다.

가설 설정

임의의 분할에서 속성이 가지는 적합성(relevance)을 엔트로피를 이용하여 알아보기 위하여 임의로 세 개의 분할(c1, c2, c3)을 가정한다. c1={x1, x2, x3, x4}, c2={x5, x6, x7}, c3={x8, x9, x10}.

제안 방법

각 군집에 존재하는 각 속성의 유사도에 대한 척도로써 조건부 엔트로피에 기반한 유사도 지수(EIESI)를 구하였다. 결과적으로 임의의 속성의 적합도 지수는 해당 군집 모드에 있는 각 속성값에 대하여 얻어진 엔트로피의 평균에 반비례하였다.
또한 가중치 값과 분할 데이터를 이용하여 분할된 부공간(subspace)을 [Fig. 4,5,6,7,8]과 같이 분할의 정확도를 기준으로 살펴보았다. 각 분할직후에 속성의 개수의 역수(1/m)보다 큰 가중치를 가지는 각각의 데이터 집합에 대하여 서로 다른 분할에 존재하는 부공간의 정보를 추출하여 [Table 4]에 나타내었다.
모드의 범주값 zij와 속성 ah와의 유사도를 측정하기 위하여 모드 zi의 속성 aj∈A의 중심값 zij에 대하여 주어진 분할 ci∈C에서 주어진 범주 속성 ah∈A와 관계하는 조건부 엔트로피를 측정하 는 조건부 엔트로피 함수 ce를 사용하였다.
본 논문에서 제안하는 확장된 정보 엔트로피를 이용한 분할 알고리즘을 통하여 공간내의 부분적인 정보뿐만 아니라 공간내의 분포를 고려하여 최적화된 속성의 가중치를 측정하고자 한다. 속성이 가지는 불확실성을 정보 엔트로피를 이용하여 측정하고 여기에 잡음 데이터로 인한 속성의 정보를 필터링할 수 있는 확률적 정보 엔트로피를 혼합하여 불확실성을 최적화 한다. 제안되는 정보 엔트로피를 k-modes 알고리즘에서 속성에 대한 불확실성(uncertainty)을 측정하고 군집을 수행한다.
본 논문에서는 군집화에 필수적인 속성간의 유사도를 계측할 수 있는 척도를 비확률적인 조건부 엔트로피를 기반으로 제안하였다. 이에 대한 적용을 두 단계로 구분하여 속성들간에 적용하였고 속성과 모드간에 적용하였다. 결과적으로 군집내의 분산도를 평가하는 엔트로피의 변형과 군집간의 상관 정보의 확률정보를 결합하여 부공간의 군집화를 위한 k-modes 분할 알고리즘에 적용하였다.
속성이 가지는 불확실성을 정보 엔트로피를 이용하여 측정하고 여기에 잡음 데이터로 인한 속성의 정보를 필터링할 수 있는 확률적 정보 엔트로피를 혼합하여 불확실성을 최적화 한다. 제안되는 정보 엔트로피를 k-modes 알고리즘에서 속성에 대한 불확실성(uncertainty)을 측정하고 군집을 수행한다.
직관적으로 εi(ah)는 모드 zi의 모든 범주값을 고려하여 ah와 연관된 불확실성, 즉 유사도의 평균을 측정한다.

대상 데이터

제안된 방법의 성능을 검증하기 위하여 기존의 방법들에 대하여 정확도(accuracy), ARI(adjusted rand index)척도를 비교하여 평가하였다. 실험에 사용된 데이터는 Congressional Voting Records, Mushroom, Breast Cancer, Soybean 과 Genetic Promotors이다. 이러한 데이터는 UCI저장소에서 이용하였다.
실험에 사용된 데이터는 Congressional Voting Records, Mushroom, Breast Cancer, Soybean 과 Genetic Promotors이다. 이러한 데이터는 UCI저장소에서 이용하였다. [Table 3]에 실험에 데이터의 특성이 나타나 있다.

데이터처리

제안된 방법의 성능을 검증하기 위하여 기존의 방법들에 대하여 정확도(accuracy), ARI(adjusted rand index)척도를 비교하여 평가하였다. 실험에 사용된 데이터는 Congressional Voting Records, Mushroom, Breast Cancer, Soybean 과 Genetic Promotors이다.

이론/모형

이에 대한 적용을 두 단계로 구분하여 속성들간에 적용하였고 속성과 모드간에 적용하였다. 결과적으로 군집내의 분산도를 평가하는 엔트로피의 변형과 군집간의 상관 정보의 확률정보를 결합하여 부공간의 군집화를 위한 k-modes 분할 알고리즘에 적용하였다.
마지막으로, Λ^(t)에 대하여 W^(t)와 Z^(t)를 고정하고 F(W(t), Z(t+1),∧(t+1)) 부분 최소화하고, F(W(t+1), Z(t+1),∧(t+1)) = F(W(t), Z(t+1),∧(t+1))이면 정지하고, 아니면 t=t+1로 정하고 둘째 단계로 간다. 결국 이러한 부분최소화(partial optimization)를 수행하는 과정을 구현한 k-means 를 기반으로 구현한 것으로 조건부 엔트로피를 기반으로 군집간의 정보를 이용하여 군집내의 각 속 성의 유사도를 측정할 수 있는 k-modes 알고리즘을 [Fig. 1]에 나타내었다.
제안된 척도는 비확률적인 정보와 확률정보를 결합하여 정보의 손실을 최소화하였다. 군집내부의 발산은 조건부 엔트로피라는 비확률 척도를 이용하였고 군집간의 독립성은 군집의 빈도수에 대한 확률척도를 이용하였다.
실험에서는 제안된 알고리즘을 검증하기 위하여 Standard k-modes [7], Entropy Weighting k-modes와 제안된 Extended Entropy Weighting k–modes 알고리즘에 대하여 실험을 수행하였다.

성능/효과

각 군집에 존재하는 각 속성의 유사도에 대한 척도로써 조건부 엔트로피에 기반한 유사도 지수(EIESI)를 구하였다. 결과적으로 임의의 속성의 적합도 지수는 해당 군집 모드에 있는 각 속성값에 대하여 얻어진 엔트로피의 평균에 반비례하였다. 이러한 접근법을 실제적인 데이터에 적용하여 정확도, f-척도와 ARI의 세 가지의 척도에 대하여 성능을 비교분석한 결과, 기존의 방법보다 부분적인 우위를 유지하였다.
확장된 엔트로피에 의한 방법이 기존의 k-modes 알고리즘보다 우수한 결과를 보였다. 또한 제안된 방법이 기존의 엔트로피에 의한 방법보다 몇 가지의 데이터 집합에서 약간의 우수한 결과를 보였다.
결과적으로 임의의 속성의 적합도 지수는 해당 군집 모드에 있는 각 속성값에 대하여 얻어진 엔트로피의 평균에 반비례하였다. 이러한 접근법을 실제적인 데이터에 적용하여 정확도, f-척도와 ARI의 세 가지의 척도에 대하여 성능을 비교분석한 결과, 기존의 방법보다 부분적인 우위를 유지하였다. 이러한 군집 유사도는 범주 값의 크기(cardinality)가 각각 다른 속성들로 구성된 고객 유형 분석을 평가할 때 유용할 것으로 사료된다.
각 데이터에 따른 100번의 실험 결과에서 가장 우수한 결과를 토대로 추출하였다. 제안된 분할 방법에 의한 부공간을 살펴보면 다른 방법에 비하여 비교적 적은 차원이 형성된 것을 알 수 있다. 이는 분할과정에서 수반되는 오버헤드를 줄일 수 있는 근거를 제시하고 있음을 알 수 있다.
유사도 함수에서 첫 번째 항은 군집내부의 발산을 최소화하고, 두 번째 항은 군집간의 독립성을 향상시킨다. 제안된 척도는 비확률적인 정보와 확률정보를 결합하여 정보의 손실을 최소화하였다. 군집내부의 발산은 조건부 엔트로피라는 비확률 척도를 이용하였고 군집간의 독립성은 군집의 빈도수에 대한 확률척도를 이용하였다.
확장된 엔트로피에 의한 방법이 기존의 k-modes 알고리즘보다 우수한 결과를 보였다. 또한 제안된 방법이 기존의 엔트로피에 의한 방법보다 몇 가지의 데이터 집합에서 약간의 우수한 결과를 보였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	군집(clustering)을 통한 데이터 마이닝은 무엇인가?	또한 여러 분야와의 융합을 통하여 무한한 형태의 패러다임을 형성하고 있다. 특히 군집(clustering)을 통한 데이터 마이닝은 비슷한 속성을 가지고 있는 데이터를 합치면서 의미 있는 군집을 형성하는 과정이며 다양한 기법들이 개발되어 왔다[1,2]. 특히, 게임에서 고객이 어떤 행동 패턴을 보이는지, 시간이 흐름에 따라 그 패턴이 어떻게 변화하는지, 그리고 긴밀한 관계를 맺고 있는 집단은 어떠한지를 통해 고객의 유형을 세분화와 같은 데이터 분석 방법에는 여러 가지 방법이 존재한다.
	최근 데이터의 영역에 포괄하는 과정은 무엇인가?	데이터의 단순한 저장이나 수집외에 대용량의 데이터를 저장, 수집, 발굴, 분석, 비즈니스화하는 빅데이터가 도래되었다. 최근 데이터의 영역은 각종 디지털 디바이스들을 통해 저장 수집된 데이터 속에서 가치 있는 정보를 찾아내어 알기 쉽게 전달하고, 정보를 원하는 사람이나 기관에 판매하는 비즈니스 과정을 포괄한다. 또한 여러 분야와의 융합을 통하여 무한한 형태의 패러다임을 형성하고 있다.
	소프트 가중치방법의 단점은 무엇인가?	이와 같은 속성의 가중치를 결정하는 과정에는 목적함수를 통하여 각 공간의 속성이 가지는 정수 가중치를 통하여 공간내에 존재하는 데이터를 재배치하여 공간을 재구성하는 소프트 가중치(soft weighting)방법이 있다[6,7]. 이러한 방법은 데이터가 많을 경우에는 복잡성이 증가하게 된다. 반면에 하드 가중치 (hard weighting)방법에서는 속성의 가중치가 부동소수점으로 운용되어 진다.

참고문헌 (15)

Sang-Hyun Lee, "A Study on Determining Factors for Manufacturers to Distributors Warehouse in Supply Chain", Journal of the Korea Convergence Society, Vol. 4, No. 2, pp. 15-20, 2013.
E. Y. Chan, W. K. Ching, M. K. Ng and J. Z. Huang, "An optimization algorithm for clustering using weighted dissimilarity measures", Pattern Recognition, Vol. 37, No. 5, pp. 943-952, 2004.

상세보기
L. Bai, J. Liang, C. Dang, and F. Cao, "A novel attribute weighting algorithm for clustering high-dimensional categorical data", Pattern Recognition, Vol. 44, No. 12, pp. 2843-2861, 2011.

상세보기
F. Cao, J. Liang, D. Li and X. Zhao, "A weighting k-modes algorithm for subspace clustering of categorical data", Neurocomputing, Vol. 108, pp. 23-30, 2013.

상세보기
L. Jing, M.K. Ng, and J. Z. Hunag, "An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparce data", Knowledge and Data Engineering, IEEE Transactions on, Vol. 19, No. 8, pp. 1026-1041, 2007.

상세보기
D. Barbara, Y. Li, and J. Couto, Coolcat: "an entropy-based algorithm for categorical clustering", in Proceedings of the 11th international conference on Information and knowledge management, ACM, pp. 582-589, 2002.
Z. Huang, "Extensions to the k-means algorithm for clustering large data sets with categorical values", Data mining and Knowledge Discovery, Vol.2, No. 3, pp. 283-304, 1998.
F. Cao, J. Liang, D. Li, L. Bai and C. Dang, "A dissimilarity measure for the k-Modes clustering algorithm, Knowledge-Based Systems", Vol. 26, pp. 120-127, 2012.

상세보기
In-Kyu Park. "The generation of control rules for data mining", The Journal of Digital Policy & Management, Vol. 11, No.1, pp.343-349, 2013.
J. L. Carbonera and M. Abel, "Categorical data clustering: a correlation-based approach for unsupervised attribute weighting", in Proceedings of ICTAI, 2014.
G. Gan and J. Wu, "Subspace clustering for high dimensional categorical data", ACM SIGDD Explorations Newsletter, Vol. 6, No. 2, pp.87-94, 2004.

상세보기
M. J. Zaki, M. Peters I. Assent, and T. Seidl, "Clicks: An effective algorithm for mining subspace clusters in categorical datasets", Data & Knowledge Engineering, Vol. 60, No. 1, pp. 51-70, 2007.

상세보기
E. Cesario, G. Manco and R. Ortale, "Top-down parameter-free clustering fo high-dimensional categorical data", IEEE Trans. on Knowledge and Data Engineering, Vol. 19, No. 12, pp. 1607-1624, 2007.

상세보기
H.-P. Kriegel, P. Kroger and A. Aimek, "Subspace clustering", Wisley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, Vol. 2, No. 4, pp. 351-364, 2012.

상세보기
J. L. Carbonera and M. Abel, "An entropy-based subspace clustering algorithm for categorical data", 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, pVol. 48, No. 26, pp. 272-277, 2014.

저자의 다른 논문 :

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

연합인증