[논문]엔트로피 가중치 및 SVD를 이용한 군집 특징 선택

이영석; 이수원

엔트로피 가중치 및 SVD를 이용한 군집 특징 선택
Cluster Feature Selection using Entropy Weighting and SVD 원문보기

정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용, v.29 no.4, 2002년, pp.248 - 257

초록
AI-Helper

군집화는 객체들의 특성을 분석하여 유사한 성질을 갖고 있는 객체들을 동일한 집단으로 분류하는 방법이다. 전자 상거래 자료처럼 차원 수가 많고 누락 값이 많은 자료의 경우 입력 자료의 차원축약, 잡음제거를 목적으로 SVD를 사용하여 군집화를 수행하는 것이 효과적이지만, SVD를 통해 변환된 자료는 원래의 속성 정보를 상실하기 때문에 군집 결과분석에서 원본 속성의 가치 해석이 어렵다. 따라서 본 연구는 군집화 수행 후 엔트로피 가중치 및 SVD를 이용하여 군집의 중요한 속성을 발견하기 위한 군집 특징 선택 기법 ENTROPY-SVD를 제안한다. ENTROPY-SVD는 자료의 속성들과 유사객체 군과의 묵시적인 은닉 구조를 활용하기 위하여 SVD를 이용하고 유사객체 군에 포함된 응집도가 높은 속성들을 발견하기 위하여 엔트로피 가중치를 사용한다. 또한 ENTROPY-SVD를 적용한 모델 기반의 협력적 여과기법의 추천 시스템 CFS-CF를 제안하고 그 효용성 및 효과를 평가한다.

Abstract ▼ AI-Helper

Clustering is a method for grouping objects with similar properties into a same cluster. SVD(Singular Value Decomposition) is known as an efficient preprocessing method for clustering because of dimension reduction and noise elimination for a high dimensional and sparse data set like E-Commerce data set. However, it is hard to evaluate the worth of original attributes because of information loss of a converted data set by SVD. This research proposes a cluster feature selection method, called ENTROPY-SVD, to find important attributes for each cluster based on entropy weighting and SVD. Using SVD, one can take advantage of the latent structures in the association of attributes with similar objects and, using entropy weighting one can find highly dense attributes for each cluster. This paper also proposes a model-based collaborative filtering recommendation system with ENTROPY-SVD, called CFS-CF and evaluates its efficiency and utilization.

주제어

AI 본문요약
AI-Helper

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

문제 정의

그러나 자료를 재구성하는 방법은 원본 속성 자료를 축약하는 특성이 있어 결과분석 단계에서 원본 자료와 군집화 결과의 객체 소속 정보를 바탕으로 군집을 형성하는 기준 속성들을 재분석해야한다. 본 연구는 군집 결과의 분석 및 응용을 위한 중간 단계의 자동화 과정으로 SVD와 같은 기법을 사용하는 군집화의 후처리 결과를 재분석하여 군집을 형성하는데 기준이 된 대표 속성 집합을 발견하고 군집 내에서의 속성의 가치와 중요도를 가중치로 설정하는 기법의 연구이다.
본 연구는 군집화 알고리즘의 후처리 작업으로 군집 결과를 분석하여 군집의 대표속성을 추출하는 방법이다. 사용되는 군집화 알고리즘은 K-Means로서, K-Means 알고리즘은 각 자료와 각 군집 중심과의 거리를 고려한 유사도 측정에 기초한 목적함수의 최적화 방식을 사용한다.
군집 대표 속성들의 가중치를 부여하는 기법을 군집 특징 선택이라 한다. 본 연구에서는 군집 속성들의 가중치 재설정을 위하여 속성의 엔트로피 가중치 (Entropy Weighting) 및 SVD 를 이용한 군집 특징 선택 알고리즘 ENTROPY-SVD를 구현하고, 이 선택 기법에 의해 발견된 대표 속성들의 효용성을 평가하기 위한 방안으로 군집 대표 속성 집합을 사용하는 추천시스템 CFS-CF 를 구현한다.
본 연구에서는 유사한 성질을 가지는 군집의 속성 (Attribute)들 중에서 군집을 대표하는 속성들의 집합을 군집의 특징(Feature)으로 보고 특징을 구성하는 속성들의 중요도(Importance) 및 가치 (Value)를 위한 속성가중치(Attribute Weighting)* 설정한다. 군집 대표 속성들의 가중치를 부여하는 기법을 군집 특징 선택이라 한다.
본 연구에서는 후처리 단계에서의 ENTROPY-SVD 군집 특징선택 방법의 평가를 위해서 군집 대표 속성 집합을 사용한 소속 군집 판정 정확도 측정과 모델 기반 협력적 여과 기법의 CFS-CF 추천 시스템을 통하여 평가하였다. 소속 군집 판정 정확도 측정은 군집의 대표속성 집합에 가중치를 높게 주었을 경우 군집화의 군집중심점과 같은 역할을 할 수 있음을 보이는 내용이며 CFS-CF와 같은 추천 시스템에서는 상품을 속성으로 인식하는 자료에서 선택된 군집의 대표 속성이 가치가 있음을 증명하는 내용이다.

가설 설정

과정3 : 형성된 군집 내 객체들올 대상으로 개념적으로 유사한 혹은 근접한 속성을 발견한다 (Attribute Similarity).
개수를 말한다. 이 기법의 기본 가정은 빈도수가 낮은 속성은 정보가치가 떨어지며 전체 수행 성능에 큰 영향을 미치지 않는다고 보는데 있다. DF 임계치 방법은 주로 문서 분류 혹은 군집화 방법에서 사용되어 DF가 낮은 단어를 제거하여 입력 자료의 차원을 축소하는데 사용된다.

제안 방법

ENTROPY-SVD의 효용성을 평가하기 위하여 군집의 대표 속성 집합을 이용한 추천 시스템, CFS-CF 를 구현하였다. ENTROPY-SVD에 의해 선택된 군집의 대표 속성을 유사 고객군의 대표 상품으로 인식하고 이러한 상품을 대상으로 추천 시스템은 상품을 추천한다. 상품 추천에 있어서 ENTROPY-SVD 특징 선택에 의한 상품 추천 시스템 CFS-CF의 추천 정확도가 기존추천 시스템(Original-CF)에 비해 높았으며 또한 군집의 성향 분석을 통한 추천 시스템으로도 발전할 수 있는 특성을 가지고 있었다.
ENTROPY-SVD의 효용성을 평가하기 위하여 군집의 대표 속성 집합을 이용한 추천 시스템, CFS-CF 를 구현하였다. ENTROPY-SVD에 의해 선택된 군집의 대표 속성을 유사 고객군의 대표 상품으로 인식하고 이러한 상품을 대상으로 추천 시스템은 상품을 추천한다.
단계 2. n번 반복하면서 입력 자료들과 군집 중심점과의 거리를 계산하여 가장 가까운 군집으로 입력 자료를 분류한다. 일반적으로 입력 자료 X와 군집 중심 이과의 거리는
따라서 원본 자료 속성의 직접적인 해석을 가능하게 하기 위해서 SVD를 통한 군집화 방법의 후처리 단계에서 속성의 엔트로피 가중치와 SVD 정보를 기반으로 속성과 군집의 유사도를 측정하여 군집 특징 선택을 한다. 군집 특징 선택에 의해 선택된 군집 대표 속성 집합의 효용성을 평가하기 위해서 SVD 벡터 성분으로 구성된 군집 중심점을 사용하지 않고 선택된 군집 대표 속성 가중치를 기반으로 입력 자료의 군집을 결정하였다. 발견된 군집의 대표 속성 집합의 가치를 평가하기 위한 실험방법으로 입력 자료의 소속 군집 발견정확도 측정하였으며 이를 통해서 ENTROPY-SVD와 기존의 특징 선택 기법들과 성능을 비교하였다.
자료를 이용하여 군집화를 수행한다. 군집화 결과인 입력 자료의 클래스 정보와 SVD 처리로 변형된 자료를 바탕으로 각 군집의 대표 속성을 결정하고 SVD 에 의해 변환된 자료와 입력자료의 클래스 정보, 군집중심점과 같은 군집 모델, 군집 대표 속성들을 데이터베이스화한다.
그림 6에서처럼 임의의 클래스가 주어진 입력 자료를 소속 군집 발견 정확도를 측정하기 위한 입력 자료로 사용하고 특징 선택 기법에 의해 선택된 군집 대표 속성 집합을 군집의 중심점 대신 사용하여 주어진 클래스로 재분류되는 정확도를 측정하였다. 실험에 사용된 특징 선택 기법들로는 ENTROPY-SVD, 엔트로피 가중치(ENTROPY), Mutual Information(MI), x2 Statistic (CHI)을 사용하였다.
다만 군집 중심점을 이용한 입력 고객의 소속 군집을 결정할 수 있을 뿐이다. 따라서 원본 자료 속성의 직접적인 해석을 가능하게 하기 위해서 SVD를 통한 군집화 방법의 후처리 단계에서 속성의 엔트로피 가중치와 SVD 정보를 기반으로 속성과 군집의 유사도를 측정하여 군집 특징 선택을 한다. 군집 특징 선택에 의해 선택된 군집 대표 속성 집합의 효용성을 평가하기 위해서 SVD 벡터 성분으로 구성된 군집 중심점을 사용하지 않고 선택된 군집 대표 속성 가중치를 기반으로 입력 자료의 군집을 결정하였다.
군집 특징 선택에 의해 선택된 군집 대표 속성 집합의 효용성을 평가하기 위해서 SVD 벡터 성분으로 구성된 군집 중심점을 사용하지 않고 선택된 군집 대표 속성 가중치를 기반으로 입력 자료의 군집을 결정하였다. 발견된 군집의 대표 속성 집합의 가치를 평가하기 위한 실험방법으로 입력 자료의 소속 군집 발견정확도 측정하였으며 이를 통해서 ENTROPY-SVD와 기존의 특징 선택 기법들과 성능을 비교하였다.
이러한 객체군집 정보를 사용하여 객체군(즉, 유사 문서 집합)과 가장 근접한 속성(즉, 단어)을 추출할 수 있다. 변환된 유사 객체군의 Pseudo-Term 벡터 d, 를 사용하여 SVD 문서 벡터 공간상에서 근접한 유사 속성들을 발견하기 위해서 Pseudo-Term 벡터 d, 와 SVD 단어 벡터 U 간의 유사도를 측정한다. 유사도 측정은 Cosine, Euclidean Distance, Jaccard와 같은 함수를 사용하여 측정할 수 있다⑹.
본 연구에서는 군집화 알고리즘 결과를 통해서 군집에서 대표할 수 있는 속성들을 발견하는 기법으로 군집특징 선택 기법 ENTROPY-SVD> 제안한다.
K-Means는 지역적 최소해에 잘 빠지며, 잡음에 민감하다는 단점이 있으나 수행속도가 빠르므로 광범위하게 이용되고 있다. 본 연구에서는 잡음제거, 차원축소의 이점을 얻기 위해서 SVD를 사용하여 단어-문서 행렬을 분해하고 얻어진 분해행렬들 중 SVD 문서 벡터를 K-Means 군집화 알고리즘으로 처리하여 문서들을 군집화한다[1].
실험 내용이다. 입력 자료는 M과 C의 두 클래스 영어 단문 9문장을 사용하였으며 SVD를 통해 입력 행렬을 변환한 후 변환 된 SVD 문서벡터를 군집화 알고리즘을 통해 군집 화하였다. 군집 수를 2개로 정하고 K- Means 알고리즘을 수행하여 표 1과 같은 결과를 얻었다.

대상 데이터

본 연구에서 사용되는 실험 자료는 EachMovie 자료로서 고객이 본 영화목록과 시청 영화에 대한 점수 (Score)가 포함된 자료이다. 대부분의 추천 시스템에서 사용되는 평가 방법을 살펴보면, 추천의 정확도를 평가하기 위해서 고객 시청영화 목록의 일정 부분을 취하여 입력자료로 사용하고 나머지 부분은 추천 시스템의 예측 및 추천의 정확도를 판별하기 위한 테스트 자료로서 활용한다.

이론/모형

“자동차”, “차”, “아분f테”, “티코” 등과 같은 단어들은 모두 자동차 관련 단어로서 모두 같은 의미로 해석할 수 있다. LSI방법을 적용하기 위해서는 먼저 TFIDFd'erm Frequency Inverse Document Frequency) 가중치 부여 기법을 사용하여 단어-문서 행렬을 구성한다. 이 기법은 한 문서 내 발생 빈도가 높은 단어의 가중치를 낮게 책정하고 전체 문서에서 골고루 분포되어 있고 발생 빈도가 높은 단어의 가중치를 높개 책정하는 특징이 있다.
입력 자료는 M과 C의 두 클래스 영어 단문 9문장을 사용하였으며 SVD를 통해 입력 행렬을 변환한 후 변환 된 SVD 문서벡터를 군집화 알고리즘을 통해 군집 화하였다. 군집 수를 2개로 정하고 K- Means 알고리즘을 수행하여 표 1과 같은 결과를 얻었다.
있다. 군집화 알고리즘을 사용하는 방법은 고객 기반 협력적 여과 기법에서 사용되는 K-Nearest Neighborhood 방법의 확장이라 할 수 있는데 먼저 유사 고객군을 형성하고 예측 및 추천에 필요한 정보를 모델로 구축한 후 입력 고객이 포함되는 군집의 모델 정보를 사용하여 추천한다. 연관 규칙 탐사 알고리즘을 사용하는 방법은 고객기반 협력적 여과 기법의 확장으로 전체 자료를 바탕으로 상품간의 연관 규칙을 발견하여 모델을 구축하고 구축된 연관 규칙 모델을 사용하여 추천한다
방법이다. 사용되는 군집화 알고리즘은 K-Means로서, K-Means 알고리즘은 각 자료와 각 군집 중심과의 거리를 고려한 유사도 측정에 기초한 목적함수의 최적화 방식을 사용한다. K-Means는 지역적 최소해에 잘 빠지며, 잡음에 민감하다는 단점이 있으나 수행속도가 빠르므로 광범위하게 이용되고 있다.
재분류되는 정확도를 측정하였다. 실험에 사용된 특징 선택 기법들로는 ENTROPY-SVD, 엔트로피 가중치(ENTROPY), Mutual Information(MI), x2 Statistic (CHI)을 사용하였다. 이러한 특징 선택 기법은 각각의 클래스에 포함된 속성과 클래스의 상관관계 혹은 클래스 내에서 속성의 중요도 가치를 가중치로 나타낼 수 있다.
제공하지 못하고 있다. 이러한 문제를 해결하기 위해서 LSI/LSA(Latent Semantic Indexing/Latent Semantic Analysis) 방법을 사용하여 객체들의 구조적 정보에 내포된 속성의 개념적 정보를 획득한다. 군집화 알고리즘을 수행한 후 얻어진 정보는 유사 객체군이다.

성능/효과

표 6은 여러 특징 선택 기법들과 ENTROPY- SVD의 성능 비교 실험 결과이다. ENTROPY-SVD 방법이 다른 방법에 비해 재 분류율이 높았다.
또한, ENTROPY-SVD에 의해 선택된 군집의 대표속성을 사용하여 입력 고객의 군집 소속 판정 정확도 실험을 수행하였으며 그 결과 선택된 대표 속성의 가중치가 각 군집의 중심점 역할을 수행할 수 있는 프로파일로 효용성이 있음을 발견하였다.
실험 결과이다. 본 기법에 의해 선택된 군집 대표 속성을 기반으로 추천항목을 정한 추천 시스템의 성능이 기존의 방법 보다 향상된 결과를 보였다.
ENTROPY-SVD에 의해 선택된 군집의 대표 속성을 유사 고객군의 대표 상품으로 인식하고 이러한 상품을 대상으로 추천 시스템은 상품을 추천한다. 상품 추천에 있어서 ENTROPY-SVD 특징 선택에 의한 상품 추천 시스템 CFS-CF의 추천 정확도가 기존추천 시스템(Original-CF)에 비해 높았으며 또한 군집의 성향 분석을 통한 추천 시스템으로도 발전할 수 있는 특성을 가지고 있었다.

참고문헌 (16)

Yang, Y., Pedersen, J.O., A Comparative Study on Feature Selection in Text Categorization, Proc.of the 14th International Conference on Machine Learning ICML97, pp. 412-420, 1997
Jachims, T., A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization, Proc. of the 14th International Conference on Machine Learning ICML97, pp. 143-151, 1997
Lewis, D. D., Feature selection and feature extraction for text categorization, Proceedings of Speech and Natural Language Workshop, pp. 212-217, 1992
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., and Harshman, R., Indexing by latent semantic analysis, Journal of the American Society for Information Science, 41(6), pp. 391-407, 1990

상세보기
Berry, M. W., Dumais, S. T., and O'Brien G. W., Using linear algebra for intelligent information retrieval, SIAM Review, 37(4), pp. 573-595, 1995

상세보기
Kolda, T. G. and O'Leary, D. P., A semidiscrete matrix decomposition for latent semantic indexing in information retrieval, ACM Trans. Inf. Syst., 16, pp. 322-346, 1998

상세보기
M.W. Berry, Z. Drmac, E.R. Jessup, Matrices, vector spaces, and information retrieval, SIAM Rev., 41(2), pp. 335-362, 1999

상세보기
Landauer, T. K., Foltz, P. W., and Laham, D., An introduction to Latent Semantic Analysis, In Discourse Processes 25, pp. 259-284, 1998
Sarwar, B. M., Karypis, G., Konstan, J. A., and Riedl J., Application of Dimensionality Reduction in Recommender System-A Case Study, In ACM WebKDD 2000 Web Mining for E-Commerce Workshop, 2000
Sudipto Guha, Rajeev Rastogi, and Kyuseok Shim., ROCK : a robust clustering algorithm for categorical attributes, In Information Systems, 25(5), pp.345-366, 2000

상세보기
Strehl, A., Ghosh and J., Mooney, R., Impact of similarity measures on web-page clustering, In Proc. AAAI Workshop on AI for Web Search, pp. 58-64, 2000
M. Devaney and A. Ram., Efficient feature selection in conceptual clustering, In Machine Learning: Proceedings of the Fourteenth International Conference, pp. 92-97, Nashville, TN, 1997
Paul Resnick ,Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom and John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the conference on Computer supported cooperative work, pp. 22-26, October 1994
Sarwar, B. M., Karypis, G., Konstan, J. A., Riedl, J., Item-based Collaborative Filtering Recommender Algorithms, In WWW10 Conference, pp. 285-295, May 2001
D. Billsus and M. J. Pazzani, Learning collaborative information filters, In Proceedings of the Fifteenth International Conference on Machine Learning, pp. 46-54, July 1998
Sonny HS Chee, RecTree: A Linear Collaborative Filtering Algorithm, M.S thesis, Computing Science, Simon Fraser University, 2000

저자의 다른 논문 :

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

연합인증