최근, 개인 데이터의 프라이버시 보호에 대한 문제가 대두됨에 따라 대용량 데이터를 대상으로 하는 데이터 마이닝 분야에서도 프라이버시 보호 문제에 대한 활발한 연구가 진행되고 있다. 데이터 마이닝에서의 프라이버시 보호 문제는 정보제공자에 의해 제공된 정보 중 민감한 개인 정보의 노출이 없이도 가능한 정확한 마이닝 결과를 얻는 것이다. 데이터 마이닝의 프라이버시 보호 기법에서는 데이터의 보호뿐만 아니라 결과의 정확도 또한 중요한 요인이다. 이에 따라, 본 논문에서는 시계열 데이터클러스터링을 기반으로 랜덤 데이터 교란 기법에서 결과의 정확도를 높이는 기법으로 노이즈 평준화 개념을 제시한다. 기존의 랜덤 데이터 교란 기법은 데이터의 프라이버시는 잘 보호하지만 시계열간의 거리-순서가 보존되지 않아 결과의 정확도가 크게 떨어지는 문제점을 가진다. 이를 위해, 본 논문에서는 PAA를 기반으로 하는 노이즈 평준화 개념을 제시하고, 구체적인 예를 통해, 제안한 노이즈 평준화 개념이 랜덤 데이터 교란 기법에서 클러스터링 결과의 정확도를 높일 수 있음을 체계적으로 설명한다.
최근, 개인 데이터의 프라이버시 보호에 대한 문제가 대두됨에 따라 대용량 데이터를 대상으로 하는 데이터 마이닝 분야에서도 프라이버시 보호 문제에 대한 활발한 연구가 진행되고 있다. 데이터 마이닝에서의 프라이버시 보호 문제는 정보제공자에 의해 제공된 정보 중 민감한 개인 정보의 노출이 없이도 가능한 정확한 마이닝 결과를 얻는 것이다. 데이터 마이닝의 프라이버시 보호 기법에서는 데이터의 보호뿐만 아니라 결과의 정확도 또한 중요한 요인이다. 이에 따라, 본 논문에서는 시계열 데이터 클러스터링을 기반으로 랜덤 데이터 교란 기법에서 결과의 정확도를 높이는 기법으로 노이즈 평준화 개념을 제시한다. 기존의 랜덤 데이터 교란 기법은 데이터의 프라이버시는 잘 보호하지만 시계열간의 거리-순서가 보존되지 않아 결과의 정확도가 크게 떨어지는 문제점을 가진다. 이를 위해, 본 논문에서는 PAA를 기반으로 하는 노이즈 평준화 개념을 제시하고, 구체적인 예를 통해, 제안한 노이즈 평준화 개념이 랜덤 데이터 교란 기법에서 클러스터링 결과의 정확도를 높일 수 있음을 체계적으로 설명한다.
Recently, there have been many research efforts on privacy-preserving data mining. In privacy-preserving data mining, accuracy preservation of mining results is as important as privacy preservation. Random perturbation privacy-preserving data mining technique is known to well preserve privacy. Howev...
Recently, there have been many research efforts on privacy-preserving data mining. In privacy-preserving data mining, accuracy preservation of mining results is as important as privacy preservation. Random perturbation privacy-preserving data mining technique is known to well preserve privacy. However, it has a problem that it destroys distance orders among time-series. In this paper, we propose a notion of the noise averaging effect of piecewise aggregate approximation(PAA), which can be preserved the clustering accuracy as high as possible in time-series data clustering. Based on the noise averaging effect, we define the PAA distance in computing distance. And, we show that our PAA distance can alleviate the problem of destroying distance orders in random perturbing time series.
Recently, there have been many research efforts on privacy-preserving data mining. In privacy-preserving data mining, accuracy preservation of mining results is as important as privacy preservation. Random perturbation privacy-preserving data mining technique is known to well preserve privacy. However, it has a problem that it destroys distance orders among time-series. In this paper, we propose a notion of the noise averaging effect of piecewise aggregate approximation(PAA), which can be preserved the clustering accuracy as high as possible in time-series data clustering. Based on the noise averaging effect, we define the PAA distance in computing distance. And, we show that our PAA distance can alleviate the problem of destroying distance orders in random perturbing time series.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
셋째, 클러스터링 정확도 비교를 위해, 프라이버시 보호 기법의적용 전후 시 계열들의 상대적인 유사성을 거리-순서라정의하였다. 따라서, 본 논문에서는 랜덤 데이터 교란기법의 거리-순서 보존율을 높이는 기법올 제안하였다. 마지막으로, 본 논문에서 제안한 PAA 거리 기법의 실용성을 실제로 기존의 랜덤 데이터 교란 기법에 적용함으로써 확인하였다.
본 논문에서는 시계열 데이터를 대상으로 하는 프라이버시 보호클러스터링 기법 중 랜덤 데이터 교란 기법의 클러스터링 정확도를 높이는 기법을 제안하였다, 본 논문의 공헌은 다음과 같이 요약할 수 있다. 첫째, 백색 잡음의 특성을 분석하여 노이즈 평준화 개념을 제시하였다.
특히, 프라이버시 보호를 위해 원본 시계열에 노이즈를 많이 더할수록 정확도는 더 떨어진다. 본 논문에서는 이 문제를 해결하기 위해 노이즈 평준화개념을 제안한다. 랜덤화 기법에서 사용하는 백색 잡음의 평균은 0이기 때문에 이들 노이즈들의 합계는 0에 가깝게 된다.
데이터 마이닝에서의 프라이버시 보호 문제는 정보제공자에 의해 제공된 정보 중 민감한 개인정보의 노출이 없이도 가능한 정확한 마이닝 결과를 얻는 것이다. 본 논문에서는 이 중 시계열 데이터 클러스터링을 기반으로 랜덤 데이터 교란 기법을 다룬다.
본 논문에서는 프라이버시 보호 마이닝 기법에서 좀더 정확한 마이닝 결과를 얻기 위한 방법을 제안하고있다. 즉, 기존의 프라이버시 보호 마이닝 기법을 적용한 클러스터링 결과와 본 논문에서 제안한 기법을 적용한 데이터에서 얻은 클러스터링 결과에 대한 비교가 필요하다.
이 기법은 웨이블릿 필터 공격에도 견고하다는 장점이 있다. 본 장에서는 웨이블릿 기반의 노이즈 생성 기법에 PAA 거리를 적용하는 wavelet_PAA 알고리즘을 제안하고자 한다. Wavelet_PAA 알고리즘은 3.
본 장에서는 클러스터링 정확도를 높이기 위하여 PAA 거리를 실제 랜덤 데이터 교란 기법에 적용하는 알고리즘을 제안하고자한다. 즉, 기존의 랜덤화 기법을 그대로사용하면서 클러스터링을 수행할 때, PAA 거리를 사용하는 것이다.
PAA 거리를 웨이블릿 기반의 노이즈 생성기법에 적용한 결과에서는 노이즈의 양과 거리-순서가 상충(trade-off) 관계를 가지는것으로 분석되었다. 이를 토대로 향후에는 웨이블릿 기반의 노이즈 생성 기법에서 거리-순서의 보존 정도를높여 클러스터링 결과의 신뢰성을 높이기 위한 연구를진행하고자 한다.
가설 설정
PAA 거리는 프라이버시 보호 기법을 적용한 후, 클러스터링을 위한 거리 계산 시에 사용되는 기법으로 기존의 프라이버시 보호 기법을수정하지 않고 사용할 수 있다는 장점이 있다. 셋째, 클러스터링 정확도 비교를 위해, 프라이버시 보호 기법의적용 전후 시 계열들의 상대적인 유사성을 거리-순서라정의하였다. 따라서, 본 논문에서는 랜덤 데이터 교란기법의 거리-순서 보존율을 높이는 기법올 제안하였다.
제안 방법
첫째, 백색 잡음의 특성을 분석하여 노이즈 평준화 개념을 제시하였다. 둘째, 노이즈 평준화 개념을 기반으로 하여 PAA 거리를 제안하였다. PAA 거리는 프라이버시 보호 기법을 적용한 후, 클러스터링을 위한 거리 계산 시에 사용되는 기법으로 기존의 프라이버시 보호 기법을수정하지 않고 사용할 수 있다는 장점이 있다.
거리-순서 보존 정도는 원본 데이터에서 객체들의 상대적 순서가 프라이버시 보호된 이후에도 유지되는정도로써, 이를 사용하여 클러스터링의 정확도를 대신할수 있다. 마지막으로 기존의 랜덤 데이터 교란 기법인랜덤화 기법과 웨이블릿 기반의 노이즈 생성 기법에 PAA 거리를 적용하여 PAA 거리의 실용성을 확인한다.
본 논문에서는 먼저 랜덤 데이터 교란 기법에서 사용되는 백색 잡음(white noise)의 특성을 분석한 후, 노이즈 평준화 개념을 제시한다. 노이즈 평준화는 백색 잡음의 평균이 0이기 때문에 노이즈들의 합이 0에 가까워진다는 특성에 기반을 둔다.
부분 집계 근사법 (Piecewise Aggregation Approximation: PAA)은 시계열 분석에서 주로 사용하는 저차원 변환 기법으로 시계열을 몇 개의 구간으로 나눈 후 그 구간에 대한 평균값을 계산하여고차원의 시계열을 저차원의 시계열로 변환한다[4]. 본논문에서는 이러한 백색 잡음의 특성을 기반으로 프라이버시 보호된 시계열들의 거리 계산에 PAA를 적용한다. 즉, 클러스터링을 위해 객체들의 거리를 계산할 때 엔트리 각각에 대한 거리 계산 대신 엔트리들의 묶음의 평균에 대한 거리 계산을 수행한다.
즉, 기존의 프라이버시 보호 마이닝 기법을 적용한 클러스터링 결과와 본 논문에서 제안한 기법을 적용한 데이터에서 얻은 클러스터링 결과에 대한 비교가 필요하다. 이를 위한 가장 간단한 방법은 원본 및 프라이버시 보호된 데이터에 대해 각각 클러스터링을 수행한후 그 결과를 직접 비교하는 것이다. 그러나 이 방법을사용하기 위해서는, 시간이 많이 소모되는 클러스터링작업을 여러 프라이버시 보호 기법 및 여러 데이터 집합 각각에 대해 매번 수행해야 하는 어려움이 따른다.
그러나 이 방법을사용하기 위해서는, 시간이 많이 소모되는 클러스터링작업을 여러 프라이버시 보호 기법 및 여러 데이터 집합 각각에 대해 매번 수행해야 하는 어려움이 따른다. 이에 따라, 본 논문에서는 클러스터링 결과를 직접 비교하는 대신, 다음과 같이 시계열간 유사성의 상대적 순서를 나타내는 거리-순서의 개념을 제시하고, 이를 클러스터링 결과의 정확도 대신 사용한다〔5].
러스터링을 수행할 때, 엔트리 각각에 대한 거리 계산 대신에 몇 개의 객체의 평균에 대한 거리 계산을 수행하면노이즈의 값들이 0에 가까운 값으로 평준화 될 것이라는개념이다. 즉, 본 논문에서 제안하는 노이즈 평준화 개념은 프라이버시 보호 클러스터링을 수행할 때, 시계열 내의 몇 개 객체의 평균에 대해 거리 계산을 수행하면 클러스터링 정확도가 향상될 것이라는 직관에 기반한다. 본 논문에서는 PAA의 노이즈 평준화 효과를 사용한다.
본논문에서는 이러한 백색 잡음의 특성을 기반으로 프라이버시 보호된 시계열들의 거리 계산에 PAA를 적용한다. 즉, 클러스터링을 위해 객체들의 거리를 계산할 때 엔트리 각각에 대한 거리 계산 대신 엔트리들의 묶음의 평균에 대한 거리 계산을 수행한다. 이 개념을 본 논문에서는 PAA 거리(PAA distance)로 정의하였다.
첫째, 백색 잡음의 특성을 분석하여 노이즈 평준화 개념을 제시하였다. 둘째, 노이즈 평준화 개념을 기반으로 하여 PAA 거리를 제안하였다.
대상 데이터
실험에서는 길이가 2048인 랜덤 워크 데이터를사용하였다. 각 시계열마다 PAA 특성은 32개를 추출하
데이터처리
였다. 실험 결과는 PAA 거리의 적용전과 후의 거리-순서 보존 결과를 백분율로 환산하였다. 그림을 보면, PAA 거리를 사용한 경우가 거리-순서를 더 잘 보존하는 것으로 나타났다.
이론/모형
다음으로, 본 논문에서는 클러스터링 정확도를 비교하기 위하여 거리-순서(distance-order)의 개념을 제시한다[5]. 거리-순서 보존 정도는 원본 데이터에서 객체들의 상대적 순서가 프라이버시 보호된 이후에도 유지되는정도로써, 이를 사용하여 클러스터링의 정확도를 대신할수 있다.
즉, 본 논문에서 제안하는 노이즈 평준화 개념은 프라이버시 보호 클러스터링을 수행할 때, 시계열 내의 몇 개 객체의 평균에 대해 거리 계산을 수행하면 클러스터링 정확도가 향상될 것이라는 직관에 기반한다. 본 논문에서는 PAA의 노이즈 평준화 효과를 사용한다. PAA는 시계열분석에서 주로 사용하는 저차원변환기법으로 계산이 간단하고 성능이 우수하다고 알려져있다.
그림 6은 그림 5에서 설명한 절차에 따라 프라이버시 보호된시계열을 생성한 후, PAA 거리를 적용하여 측정한 wavelet_PAA의 거리-순서 보존 정도에 대한 실험 결과이다. 실험결과를 보면 PAA 거리를 사용하는 웨이블릿 기반의 노이즈 생성 기법은 PAA 거리를 사용하는랜덤화 기법에 .비해 거리-순서 보존 정도가 급격하게감소하는 것으로 나타났다.
이러한 과정을 나타내는 알고리즘 rando-mization_PAA이 그림 2이다. 알고리즘을 보면, 평균이 0이고 표준편차가。인 가우시안 분포를 통해 임의의 값을 생성하는 함수 GaussRand(Qo)를 사용하여 원본 시계열을 왜곡시킨다. 이 결과로 생성된 시계열 Xp7\ 클러스터링에서 사용된다.
성능/효과
즉, PAA 거리의 노이즈평준화 효과를 확인할 수 있었다. PAA 거리를 웨이블릿 기반의 노이즈 생성기법에 적용한 결과에서는 노이즈의 양과 거리-순서가 상충(trade-off) 관계를 가지는것으로 분석되었다. 이를 토대로 향후에는 웨이블릿 기반의 노이즈 생성 기법에서 거리-순서의 보존 정도를높여 클러스터링 결과의 신뢰성을 높이기 위한 연구를진행하고자 한다.
따라서, 본 논문에서는 랜덤 데이터 교란기법의 거리-순서 보존율을 높이는 기법올 제안하였다. 마지막으로, 본 논문에서 제안한 PAA 거리 기법의 실용성을 실제로 기존의 랜덤 데이터 교란 기법에 적용함으로써 확인하였다. 적용 결과, 랜덤화 기법의 경우, 거리-순서 보존율이 향상되었다.
즉, 절대값이。미만인 계수들을 제외하고 나머지계수들을 역변환하는 것이다. 실제 실험결과, 복원된 시계열에는 48%의 노이즈만이 남아있었다.
마지막으로, 본 논문에서 제안한 PAA 거리 기법의 실용성을 실제로 기존의 랜덤 데이터 교란 기법에 적용함으로써 확인하였다. 적용 결과, 랜덤화 기법의 경우, 거리-순서 보존율이 향상되었다. 즉, PAA 거리의 노이즈평준화 효과를 확인할 수 있었다.
적용 결과, 랜덤화 기법의 경우, 거리-순서 보존율이 향상되었다. 즉, PAA 거리의 노이즈평준화 효과를 확인할 수 있었다. PAA 거리를 웨이블릿 기반의 노이즈 생성기법에 적용한 결과에서는 노이즈의 양과 거리-순서가 상충(trade-off) 관계를 가지는것으로 분석되었다.
후속연구
즉, 기존의 프라이버시 보호 마이닝 기법을 적용한 클러스터링 결과와 본 논문에서 제안한 기법을 적용한 데이터에서 얻은 클러스터링 결과에 대한 비교가 필요하다. 이를 위한 가장 간단한 방법은 원본 및 프라이버시 보호된 데이터에 대해 각각 클러스터링을 수행한후 그 결과를 직접 비교하는 것이다.
참고문헌 (9)
R. Agrawal and R. Srikant, "Privacy Preserving Data Mining," In Proc. of the Int'l Conf. on Management of Data, Dallas, Texas, pp.439-450, May 2000.
Y. Lindell and B. Pinkas, "Privacy Preserving Data Mining," Advances in Cryptology, vol.1807, pp.35-53, Dec. 2000.
A. V. Evfimievski, R. Srikant, R. Agrawal, and J. Gehrke, "Privacy Preserving Mining of Association Rules," In Proc. of the 8th Int'l Conf. on Knowledge Discovery and Data Mining, Edmonton, Canada, pp.217-228, July 2002.
W.-S. Han, J. Lee, Y.-S. Moon, H. Jiang, "Ranked Subsequence Matching in Time-Series Databases," In Proc. of the 33th Int'l Conf. on Very Large Data Bases, Vienna, Austria, pp.423-434, Sept. 2007.
H.-S. Kim, Y.-S. Moon, "Privacy-Preserving Clustering on Time-Series Data Using Fourier Magnitudes," Journal of KIISE: Databases, vol.35, no.6, pp.481-494, Dec. 2008. (in Korean)
S. Rizvi and J. R. Haritsa, "Maintaining Data Privacy in Association Rule Mining," In Proc. of the 28th Int'l Conf. on Very Large Data Bases, Hong Kong, China, pp.682-693, Sept. 2002.
S. Papadimitriou, F. Li, G. Kollios, and P. S. Yu, "Time Series Compressibility and Privacy," In Proc. of the 33th Int'l Conf. on Very Large Data Bases, Vienna, Austria, pp.459-470, Sept. 2007.
J. Vaidya and C. Clifton, "Privacy-Preserving k-Means Clustering over Vertically Partitioned Data," In Proc. of the 9th Int'l Conf. on Knowledge Discovery and Data Mining, Washington D.C., pp.24-27, Aug. 2003.
S. Mukherjee and Z. Chen, "A Privacy-Preserving Technique for Euclidean Distance-based Mining Algorithms Using Fourier-Related Transforms," The VLDB Journal, vol.15, no.4, pp.293-315, Nov. 2006.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.