[논문]PCA 기반 군집화를 이용한 해슁 기법

박정희

doi:10.3745/ktsde.2014.3.6.215

PCA 기반 군집화를 이용한 해슁 기법
A Hashing Method Using PCA-based Clustering 원문보기

정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학, v.3 no.6, 2014년, pp.215 - 218

초록
AI-Helper

해슁(hashing)을 기반으로 한 근사 최근접 이웃 탐색(approximate nearest neighbors search, ANN search) 방법에서는 데이터 샘플들을 k-비트 이진 코드로 변환하는 해쉬 함수들을 이용함으로써 근접 이웃 탐색이 이진변환 공간에서 이루어지게 된다. 본 논문에서는 PCA 기반 군집화 방법인 Principal Direction Divisive Partitioning(PDDP)를 이용한 해슁 방법을 제안한다. PDDP는 가장 큰 분산을 가지는 클러스터를 선택하여 그 클러스터의 첫 번째 주성분 방향을 이용하여 두 개의 클러스터로 분할하는 과정을 반복적으로 시행하는 군집화 방법이다. 제안하는 해슁 방법에서는 PDDP에서 분할을 위해 사용하는 주성분방향을 바이너리 코딩을 위한 사영벡터로서 사용한다. 실험결과는 제안하는 방법이 다른 해슁 방법들과 비교하여 경쟁력 있는 방법임을 입증한다.

Abstract ▼ AI-Helper

In hashing-based methods for approximate nearest neighbors(ANN) search, by mapping data points to k-bit binary codes, nearest neighbors are searched in a binary embedding space. In this paper, we present a hashing method using a PCA-based clustering method, Principal Direction Divisive Partitioning(PDDP). PDDP is a clustering method which repeatedly partitions the cluster with the largest variance into two clusters by using the first principal direction. The proposed hashing method utilizes the first principal direction as a projective direction for binary coding. Experimental results demonstrate that the proposed method is competitive compared with other hashing methods.

주제어

AI 본문요약
AI-Helper

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

문제 정의

PDDP에서는 이러한 척도들 중 하나로 평균을 0으로 이동시킨 데이터행렬의 Frobenius norm으로 정의되는 클러스터의 분산을 이용한다. 반복적으로 가장 큰 분산을 가진 클러스터를 분할함으로써 결국에는 비슷한 수의 원소들을 가진 클러스터들로 구성되는 군집화를 이루고자 한다.
이 논문에서는, PCA 기반 군집화 방법인 Principal Direction Divisive Partitioning(PDDP)[6]를 이용하여 근사 최근접 이웃 탐색에 활용 가능한 해슁 방법을 제안한다. PDDP는 PCA를 이용하여 클러스터들을 더 작은 사이즈의 클러스터들로 반복적으로 분할하는 분열 계층(divisive hierarchical) 군집화방법이다.

가설 설정

해슁에서는 가까이 있는 데이터 샘플들의 충돌(collision) 가능성을 멀리 떨어져 있는 것들에 대해서보다 크게 할 수 있는 해쉬 함수를 사용하는 것이 핵심이다. Locality sensitive hashing(LSH)에서는 데이터들이 p-stable 분포(예를 들어, 가우시안 분포)를 따른다고 가정한다[3]. 이 분포로부터 랜덤 사영벡터를 추출하여 해쉬함수 h_i(x) = sign(#) 를 구하고, k-비트 이진코드 H = [h₁,⋯,h_k ] 를 구성한다.

제안 방법

PCA 기반 군집화 방법인 PDDP를 이용한 해슁 방법을 제안하고, 다른 해슁 방법들과 비교하였다. 실험결과는 제안한 방법이 약간 긴 코드 길이에서 다른 해슁 방법들에 비해 나은 성능을 가짐을 보였고, 특히 k-Means를 이용한 군집화를 이용한 해슁방법에 대해서도 경쟁력이 있음을 보 였다.
PDDP는 PCA를 이용하여 클러스터들을 더 작은 사이즈의 클러스터들로 반복적으로 분할하는 분열 계층(divisive hierarchical) 군집화방법이다. 가장 큰 분산을 가지는 클러스터를 선택하여 그 클러스터의 첫 번째 주성분 방향을 이용하여 두 개의 클러스터로 분할하는 과정을 반복함으로써 전체적으로 균형이 맞는 분할을 추구한다. 제안하는 해슁 방법에서는 PDDP에서 분할을 위해 사용하는 주성분방향을 바이너리 코딩을 위한 사영벡터로서 사용한다.
테스트 집합에 있는 각 데이터를 큐어리로 사용하여 가장 작은 해밍 거리를 가진 500개의 데이터를 트레이닝 데이터로부터 구한다. 각 큐어리에 대해 정확도와 재현률을 구한 후, 모든 큐어리에 대해 평균을 취함으로써 성능을 평가한다. 큐어리에 대한 근접 이웃은 논문[7]에서처럼 숫자 라벨을 이용하여 같은 클래스의 원소로서 정의한다.
표준정규분포를 따르는 2차원 데이터 샘플 200개를 생성하여 평균이 (-9,0)이 되도록 x축으로 평행이동하였다. 같은 과정으로 각각 평균이 (-3,0), (3,0), (9,0)이 되는 세 개의 집합을 더 생성한 후, PCAH, SH, PDDPH를 적용하여 바이너리 코드를 구성하였다. 그래프(a)에서 PCAH 는 두 개의 주성분에서 얻어지는 경계함수 # 에 의한 분할된 영역을 보여준다.
사이즈 28x28의 그레이 레벨 이미지로서 각 이미지는 784차원의 벡터로 저장된다. 데이터를 69000개의 트레이닝 데이터와 1000개의 테스트 데이터로 나눈 후, 트레이닝 데이터를 이용하여 해쉬함수들을 구하여 모든 데이터를 바이너리 코드로 변환한다. 테스트 집합에 있는 각 데이터를 큐어리로 사용하여 가장 작은 해밍 거리를 가진 500개의 데이터를 트레이닝 데이터로부터 구한다.
제안된 방법을 LSH, PCAH, SH, DSH와 비교하였다. DSH(Density sensitive hashing)는 k-Menas 군집화에 기반한 해슁 방법이다[7].
가장 큰 분산을 가지는 클러스터를 선택하여 그 클러스터의 첫 번째 주성분 방향을 이용하여 두 개의 클러스터로 분할하는 과정을 반복함으로써 전체적으로 균형이 맞는 분할을 추구한다. 제안하는 해슁 방법에서는 PDDP에서 분할을 위해 사용하는 주성분방향을 바이너리 코딩을 위한 사영벡터로서 사용한다. 2절에서는 관련연구를 살펴보고, 3절에서 PDDP를 이용한 해슁 방법을 제안한다.

대상 데이터

전체 기사에서 50번보다 적게 나타나는 term을 제거한 후, 6165차원의 19944개의 다큐먼트 벡터들을 가지게 된다. 데이터는 19000개의 트레이닝 데이터와 1000개의 테스트 데이터로 나눈다. 각 큐어리에 대해 가장 작은 해밍 거리를 가지는 200개의 다큐먼트를 트레이닝 데이터에서 추출하는 점을 제외하고 나머지 실험 환경은 첫 번째 실험과 동일하게 하였다.
DSH(Density sensitive hashing)는 k-Menas 군집화에 기반한 해슁 방법이다[7]. 성능 비교 실험을 위하여 두 개의 데이터 집합을 이용하였다. 첫 번째는 0부터 9까지 숫자를 손으로 쓴 70000개의 숫자이미지들로 구성된 MNIST 데이터이다[8].
실험에 사용한 다른 데이터는 20 뉴스그룹으로부터 취한약 20000개의 기사를 포함하는 20 newsgroup 데이터이다. 전체 기사에서 50번보다 적게 나타나는 term을 제거한 후, 6165차원의 19944개의 다큐먼트 벡터들을 가지게 된다.
성능 비교 실험을 위하여 두 개의 데이터 집합을 이용하였다. 첫 번째는 0부터 9까지 숫자를 손으로 쓴 70000개의 숫자이미지들로 구성된 MNIST 데이터이다[8]. 사이즈 28x28의 그레이 레벨 이미지로서 각 이미지는 784차원의 벡터로 저장된다.
데이터를 69000개의 트레이닝 데이터와 1000개의 테스트 데이터로 나눈 후, 트레이닝 데이터를 이용하여 해쉬함수들을 구하여 모든 데이터를 바이너리 코드로 변환한다. 테스트 집합에 있는 각 데이터를 큐어리로 사용하여 가장 작은 해밍 거리를 가진 500개의 데이터를 트레이닝 데이터로부터 구한다. 각 큐어리에 대해 정확도와 재현률을 구한 후, 모든 큐어리에 대해 평균을 취함으로써 성능을 평가한다.

데이터처리

트레이닝 데이터와 테스트 데이터로 나눔을 임의로 30번 되풀이하여 실행하여 평균정확도(왼쪽 그래프)와 재현률(오른쪽 그래프)을 그림3에 나타내었다. x축에 있는 숫자는 k-비트 코드 길이인 k값을 나타내며 5부터 100까지 5씩 증가 시키면서 성능을 평가하였다. 10에서 20 사이의 짧은 코드 길이에서는 SH와 PCAH가 좋은 성능을 나타내나, 30 이상의 코드 길이를 이용할 때는 제안한 방법이 다른 방법들에 비해 더 나은 성능을 보였다.

이론/모형

k-비트 바이너리 코딩을 위해 전체 데이터 집합이 k+1개의 클러스터로 나누어질 때까지 분기를 계속함으로써 k개의 해쉬 함수를 얻을 수 있다. 제안된 알고리즘을 PDDPH(PDDP-based Hashing)라고 축약해서 표시하고, 그림 1에 요약하였다.

성능/효과

x축에 있는 숫자는 k-비트 코드 길이인 k값을 나타내며 5부터 100까지 5씩 증가 시키면서 성능을 평가하였다. 10에서 20 사이의 짧은 코드 길이에서는 SH와 PCAH가 좋은 성능을 나타내나, 30 이상의 코드 길이를 이용할 때는 제안한 방법이 다른 방법들에 비해 더 나은 성능을 보였다. 이는 그림2에서도 볼 수 있듯이 PDDPH에서는 충분한 수의 클러스터로 분할됨이 필요하기 때문이다.
PCA 기반 군집화 방법인 PDDP를 이용한 해슁 방법을 제안하고, 다른 해슁 방법들과 비교하였다. 실험결과는 제안한 방법이 약간 긴 코드 길이에서 다른 해슁 방법들에 비해 나은 성능을 가짐을 보였고, 특히 k-Means를 이용한 군집화를 이용한 해슁방법에 대해서도 경쟁력이 있음을 보 였다.
그림4에서 30번의 실험을 반복하여 얻은 평균정확도와 평균재현률을 보이고 있다. 첫 번째 실험과 달리 PCAH 방법이 가장 좋은 성능을 보이고 있다. 이는 고차원 데이터에서 PCA에 의해 얻어지는 큰 분산에 해당하는 주성분 방향들의 직교성에 의해 비트들의 중복성(redundancy)를 효과적으로 줄일 수 있었기 때문이라 분석된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	해슁 기반 방법은 어디에서 이루어지는가?	해슁 기반 방법들에서는 데이터 샘플들을 k-비트 이진 코드로 변환하는 해쉬 함수(hash function)들을 이용함으로써 근접 이웃 탐색이 이진변환 공간에서 이루어진다. Locality sensitive hashing(LSH)[3]에서는 해쉬 함수로서 임의 사영 (random projection)을 사용한다.
	PDDP란?	PDDP는 전체 데이터를 한 개의 클러스터로 설정한 후 반복적인 클러스터의 분할을 통해 군집화를 하는 하향식 계층적 군집화 방법이다[6]. 한 클러스터를 두 개의 클러스터로 나누기 위해 가장 큰 분산을 갖는 주성분을 이용한다.
	SH 알고리즘이 PCA를 이용하여 구현되는 세 단계는 무엇인가?	1) PCA를 이용하여 데이터의 주성분들을 구한다. 2) 각 주성분 방향으로 사영된 데이터에서 k개의 작은 고유값에 해당하는 일차원 해석적 고유함수(analytic eigenfunction) 를 구한다. 3) 전체에서 가장 작은 k개의 고유값에 해당하는 고유함수를 구한 후, 바이너리 코드를 얻기 위해 고유함수를 0에서 임계치 처리한다.

참고문헌 (8)

P. Indyk and R. Motwani, "Approximate nearest neighbors: Towards removing the curse of dimensionality", Proceedings of ACM Symposium on theory of computing, 1998.
M. Muja and D. Lowe, "Fast approximate nearest neighbors with automatic algorithm configuration", Proceedings of International Conference on Computer Vision Theory and Applications, 2009.
A. Gionis and P. Indyk and R. Motwani, "Similarity search in high dimensions via hashing", Proceedings of VLDB, 518-529, 1999.
X.-J. Wang and L. Zhang and F. Jing and W.-Y. Ma, "Annosearch: Image auto-annotation by search", Proceedings of CVPR, 1483-1490, 2006.
Y. Weiss and A. Torralba and R. Fergus, "Spectral Hashing", Proceedings of Advances in Neural Information Processing Systems, 21, 1753-1760, 2008.
D. Boley, "Principal direction divisive partitioning", Data mining and knowledge discovery, 2(4), 325-344, 1998.

상세보기
Y. Lin and D. Cai and C. Li, "Density sensitive hashing", Proceedings of CoRR, 2012.
http://yann.lecun.com/exdb/mnist

저자의 다른 논문 :

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

연합인증