암호화 연산 프로토콜 및 데이터 분포 기반 중심점 선정을 이용한 개인 정보 보호 k-Means 클러스터링 알고리즘 (Privacy-preserving k-Means Clustering Algorithm using a Secure Comparison Operation Protocol and Data Distribution-based Center Selection)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 24권 / 10호 / 505 ~ 512페이지
· 저자명 : 김형진, 장재우

초록

아웃소싱 데이터베이스 상에서 개인정보를 보호 클러스터링 알고리즘이 활발히 연구되었다.
Rao. et. al. 은 paillier 암호화 시스템을 이용하여 정보 보호를 지원하는 k-Means 클러스터링 알고리즘을 제안하였다. 그러나 해당 알고리즘은 초기 중심점을 임의로 선정함으로써 Clustering의 결과가 불규칙하다. 아울러, 비트 배열 기반 비교 연산자를 사용하기 때문에 배열의 크기에 비례하여 계산 비용이 크게 증가하는 단점이 존재한다. 이러한 문제점을 해결하기 위해. 본 논문에서는 정보 보호를 지원하는 효율적인 k-Means 클러스터링 알고리즘을 제안한다. 이를 위해, 암호화된 데이터의 비교를 수행하는 암호화 연산 프로토콜을 제안한다. 또한 전체 데이터 분포를 반영하여 초기 중심점을 선정함으로써 효율적인 클러스터링을 수행한다. 마지막으로, 성능평가를 통해 제안하는 알고리즘이 기존 알고리즘에 비해 평균적으로 약150～250% 성능이 향상됨을 보인다.

영어초록

Privacy-preserving clustering algorithms in outsourced databases have been actively studied. Rao. et. al. proposed a k-Means clustering algorithm that supports the protection of information by using a paillier crypto system. However, since the algorithm selects initial center points randomly, the result of clustering is irregular. Because it uses a comparison operator based on bit arrays, it has a disadvantage in that its computation cost greatly increases in proportion to the size of the array. To solve this problem, we propose an efficient k-Means clustering algorithm that supports the protection of information. To do this, we propose a cryptographic operation protocol that compares encrypted data. In addition, we performs efficient clustering by selecting initial center points in terms of the entire data distribution. Finally, we show through our performance evaluation that the proposed algorithm outperforms the existing algorithm by 150 to 250% on the average.

참고자료

· 없음