[논문]다자간 환경에서 프라이버시를 보호하는 효율적인 DBSCAN 군집화 기법

김기성; 정익래

doi:10.13089/jkiisc.2010.20.3.105

다자간 환경에서 프라이버시를 보호하는 효율적인 DBSCAN 군집화 기법
Practical Privacy-Preserving DBSCAN Clustering Over Horizontally Partitioned Data 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.20 no.3, 2010년, pp.105 - 111

김기성 (고려대학교 정보경영공학전문대학원) , 정익래 (고려대학교 정보경영공학전문대학원)

초록
AI-Helper

본 논문은 다자간 환경에서 프라이버시를 보호하는 효율적인 DBSCAN 군집화 기법을 제안한다. 기존 DBSCAN 군집화 기법에 가짜 데이터 삽입을 통한 프라이버시 보호 기법을 적용해 다자간 환경에서 프라이버시를 보호하는 기법으로 확장했다. 기존의 프라이버시를 보호하는 다자간 환경의 군집화 기법들은 비효율적이어서 실제 환경에 적용하기 힘들지만 제안한 기법은 이러한 문제를 해결한 매우 효율적인 기법이다. 본 기법은 다자간 환경뿐만 아니라 비 다자간 환경에도 적용 가능한 효율적인 기법이다.

Abstract ▼ AI-Helper

We propose a practical privacy-preserving clustering protocol over horizontally partitioned data. We extend the DBSCAN clustering algorithm into a distributed protocol in which data providers mix real data with fake data to provide privacy. Our privacy-preserving clustering protocol is very efficient whereas the previous privacy-preserving protocols in the distributed environments are not practical to be used in real applications. The efficiency of our privacy-preserving clustering protocol over horizontally partitioned data is comparable with those of privacy-preserving clustering protocols in the non-distributed environments.

주제어

AI 본문요약
AI-Helper

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

문제 정의

실시한다. 또한, 지금까지 연구된 다른 기법들과의 비교를 해봄으로써 본 기법의 우수성을 말한다.
본 논문에서는 다자간 환경에서 프라이버시를 보호하는 효율적인 DBSCAN 군집화 기법을 제안했다. 기존의 프라이버시 보존군집화 기법에 한 번 도 시도되지 않은 가짜 데이터 삽입 기법을 통해 밀도 차이에 기반으로 실행되는 DBSCAN 군집화 기법을 다자간환경에서 프라이버시를 보호하는 효율적인 기법으로 확장했다.
이에 본 논문에서는 프라이버시를 보호하는 군집화 분야에 한 번도 시도된 적이 없는 가짜 데이터 삽입기법을 통해 다자간 환경에서 프라이버시를 보호하는 효율적인 군집화 기법을 제안한다. 본 기법은 기존의 다자간 환경 기법들이 사용하는 암호학적 기법이나 안전한 다자간 계산을 사용하지 않아 매우 효율적이고, 비 다자간 환경에도 적용 가능한 매우 현실적인 기법이다.

가설 설정

1. P느 가짜 데이터 개수 叫를 설정한다.
데이터 소유주 P는 각각 자신의 데이터베이스 D, 를 가지고 있다. p=(py, Pd)는 데이터베이스에 속하는 d 차원의 데이터를 나타내며, % <Pi의 범위를 갖는다고 가정한다.

제안 방법

4. P느 모든 를 수집하여 (也'U... UZ為')을 생성하여 DBSCAN 군집화를 실행한다.
본 장에서는 여러 데이터베이스를 바탕으로 실제 가짜 데이터 삽입 알고리즘을 실행해보고 그에 따른 분석을 실시한다. 또한, 지금까지 연구된 다른 기법들과의 비교를 해봄으로써 본 기법의 우수성을 말한다.
실시하는 실험은 군집화 알고리즘은 R 언어로 시뮬레이션하며, 가짜 데이터 삽입은 C로 실시했다. 사용한 데이터베이스는 http://cs.

대상 데이터

실시했다. 사용한 데이터베이스는 http://cs.joensuu.fi/si- pu/datasets/을 이용하였다. 실험 컴퓨터는 Intel Pentium4 3.

성능/효과

1. 데이터 /와 g가 2쎄서 군집화 후 같은 군집에 속하는 점일 때, 데이터 p와 q는 疗에서도 군집화후 같은 군집에 속해야 한다.
A2와 S3은그보다 약간 불분명한 데이터베이스였다. 결과에서 알 수 있듯이 군집화가 뚜렷하게 가능한 데이터베이스의 경우에 보다 많은 가짜 데이터 삽입이 가능했고 그에 따른 높은 프라이버시를 보장 할 수 있었다. 따라서 본 기법은 군집의 경계가 뚜렷한 환경에서 보다 높은 성능을 발휘함을 알 수 있다.
제안했다. 기존의 프라이버시 보존군집화 기법에 한 번 도 시도되지 않은 가짜 데이터 삽입 기법을 통해 밀도 차이에 기반으로 실행되는 DBSCAN 군집화 기법을 다자간환경에서 프라이버시를 보호하는 효율적인 기법으로 확장했다. 본 기법은 기존의 다자간 환경에서 제안된 기법들이 주로 사용하는 안전한 다자간 계산과 암호학적 기법을 하지 않아 매우 효율적이며, 비 다자간 환경에서도 활용 가능한 실용적인 기법이다.
결과에서 알 수 있듯이 군집화가 뚜렷하게 가능한 데이터베이스의 경우에 보다 많은 가짜 데이터 삽입이 가능했고 그에 따른 높은 프라이버시를 보장 할 수 있었다. 따라서 본 기법은 군집의 경계가 뚜렷한 환경에서 보다 높은 성능을 발휘함을 알 수 있다.
따라서 본 기법은 사용자의 요구에 따라 프라이버시가 조절 가능한 효율적인 기법으로 요구에 따라 일정 수준의 프라이버시까지 보장할 수 있다.
본 기법은 DBSCAN의 입력 변수인 硕s와 MnPt 값을 조절함으로써 프라이버시값을 향상 시킬 수 있다. £切값은 작게, MmPt값은 크게 입력할 경우 보다 높은 프라이버시를 얻어낼 수 있다.
군집화 기법을 제안한다. 본 기법은 기존의 다자간 환경 기법들이 사용하는 암호학적 기법이나 안전한 다자간 계산을 사용하지 않아 매우 효율적이고, 비 다자간 환경에도 적용 가능한 매우 현실적인 기법이다.
제안한 기법은 가짜 데이터를 삽입함으로써 공격자가 어느 것이 진짜 데이터인지를 판단하기 힘든 점에 안전성으로 두고 있다. 하지만 공격자가 얻을 수 있는 정보는 존재한다.
〔7〕은 비 다자간 기법 중 처음으로 제안된 논문으로 기하학적 변환 방법인 이동(shift), 확대(scale), 변환(rotation) 등을 통해 원본 데이터를 변형함으로써 데이터의 프라이버시를 보호하는 기법을 제안했다. 하지만 제안된 기법은 알려진 원본 데이터와 변형된 데이터 쌍에 의해 쉽게 공격 가능하다.

참고문헌 (14)

J. Han and M. Kamber, Data Mining: Concepts and Techniuqes, 2th Ed., Morgan Kaufmann Publishers, Jan. 2006.
A.K. Jain and R.C. Dubes, Algorithms for Clustering Data, Prentice-Hall, Mar. 1998.
R. Agrawal and R. Srikant, "Privacy-preserving data mining," In Proceedings of the 2000 ACM SIGMOD Conference on Management of Data, pp. 439-450, May 2000.
Y. Lindell and B. Pinkas, "Privacy preserving data mining," In Advances in Cryptology - CRYPTO 2000, pp. 36-54, Aug. 2000.
D. Agrawal and C.C. Aggarwal, "On the design and quantification of privacy preserving data mining algorithms," In Proceedings of the 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 247-255, Mar. 2001.
A. Evfimevski, J. Gehrke, and R. Srikant, "Limiting privacy breaches in privacy preserving data mining," In Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 211-222, June 2003.
S. Oliveira and O. Zaiane, "Privacy Preserving Clustering By Data Transformation," In Proceedings of the 18th Brazilian Symposium on Databases, pp. 304-318, Oct. 2003.
Z. Huang, W. Du, and B Chen, "Deriving Private Information from Randomized Data," In ACM SIGMOD, pp. 37-48 , June 2005.
S.R.M. Oliveira and O.R. Zaiane, "Achieving Privacy Preservation When Sharing Data For Clustering," In Proc. of the Workshop on Secure Data Management in a Connected World (SDM'4) in conjunction with VLDB'004, pp. 67-82, Aug. 2004.
K. Liu and H. Kargupta, "Random Projection-Based Multiplicative Data Perturbation for Privacy Preserving Distributed Data Mining," IEEE TKDE, vol. 18, no. 1, pp. 92-106 , Nov. 2006.
J. Vaidya and C. Clifton, "Privacy-Preserving K-Means Clustering Over Vertically Partitioned Data," In Proc. of the 9th ACM SIGKDD Intl. Conf. on Knowlegde Discovery and Data Mining, pp. 206-215, Aug. 2003.
A. Inan, S.V. Kaya, Y. Saygin, E. Savas, A.A. Hintoglu, and A. Levi, "Privacy preserving clustering on horizontally partitioned data," Data & Knowledge Engineering (DKE), vol. 63, no. 3, pp. 646-666, Oct. 2007.

상세보기
S. Jha, L. Kruger, and P. McDaniel, "Privacy preserving clustering," In Proceedings of 10th European Symposium on Research in Computer Security (ESORICS '5), Milan, pp. 397-417, Sep. 2005.
M. Ester, H.P. Kriegel, J. Sander, and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise," Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, pp. 226-231, Aug. 1996.

저자의 다른 논문 :

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증