1 |
1
데이터 마이닝 시스템이 데이터를 K-평균 클러스터링하는 방법으로서,좌표 정보로 이루어진 복수의 데이터의 분포를 쿼드 트리를 이용하여 미리 설정된 수만큼 분할하여 복수의 초기 버킷을 생성하는 단계,상기 생성한 초기 버킷에 각각 포함된 데이터 수에 카운트 노이즈를 반영하고, 미리 계산된 제1 임계값과 제2 임계값을 토대로 상기 복수의 초기 버킷 중 적어도 하나의 초기 버킷을 분할하여 복수의 버킷으로 생성하는 단계,상기 생성된 복수의 버킷 각각에 대한 구간 정보와, 상기 카운트 노이즈가 반영된 버킷 각각에 포함된 데이터 수를 포함하여, 차분 프라이버시를 만족하는 히스토그램을 생성하는 단계, 그리고상기 차분 프라이버시를 만족하는 히스토그램을, 외부로부터 수신한 클러스터 개수를 토대로 K-평균 클러스터링을 실행하는 단계를 포함하고,상기 제1 임계값은 복수의 버킷에 포함될 데이터 수를 제한하기 위한 임계값이고, 상기 제2 임계값은 동일한 버킷을 분할하기 위한 분할 횟수를 제한하기 위한 임계값인 클러스터링 방법
|
2 |
2
제1항에 있어서,상기 초기 버킷을 생성하는 단계는,상기 좌표 정보로 이루어진 복수의 데이터, 상기 데이터를 토대로 생성되는 복수의 버킷에 대한 제1 정보와 제2 정보를 보호하기 위한 정보 보호 수준, 상기 제1 정보와 제2 정보를 어느 정도의 비율로 보호할지 나타내는 정보 보호 수준 비율 그리고 상기 K-평균 클러스터링을 실행하기 위한 클러스터 개수를 포함하는 입력 정보를 수신하는 단계를 포함하는 클러스터링 방법
|
3 |
3
삭제
|
4 |
4
제1항에 있어서,상기 제1 임계값은 상기 데이터의 수를 토대로 계산되고, 상기 제2 임계값은 상기 데이터의 수와 상기 복수의 데이터를 이루를 좌표의 차원(dimension)을 토대로 계산되는 클러스터링 방법
|
5 |
5
제4항에 있어서,상기 복수의 버킷으로 생성하는 단계는,상기 생성한 복수의 초기 버킷 각각에 상기 카운트 노이즈를 반영하고, 카운트 노이즈가 반영된 초기 버킷 각각 포함된 데이터 수가 상기 제1 임계값보다 많은지 확인하는 단계,임의의 초기 버킷에 포함된 데이터 수가 상기 제1 임계값보다 많으면, 상기 임의의 초기 버킷이 분할된 횟수가 상기 제2 임계값보다 많은지 확인하는 단계, 그리고상기 임의의 초기 버킷이 분할된 횟수가 상기 제2 임계값 보다 적다면, 상기 임의의 초기 버킷을 분할하여 복수의 새로운 버킷으로 생성하는 단계를 포함하는 클러스터링 방법
|
6 |
6
제5항에 있어서,상기 새로운 버킷으로 생성하는 단계는 각각의 버킷 내 데이터 수가 상기 제1 임계값보다 적고, 각각의 버킷이 분할되는 경우 분할된 횟수가 상기 제2 임계값보다 적을 경우 반복 실행하여 새로운 버킷을 생성하고,상기 생성된 새로운 버킷 각각은 복수의 버킷의 구간과 상기 복수의 버킷 각각에 포함된 데이터 수가 상이한 클러스터링 방법
|
7 |
7
제2항에 있어서,상기 입력 정보를 수신하는 단계는,상기 정보 보호 수준과 상기 정보 보호 수준 비율을 이용하여, 상기 제1 정보를 보호하기 위한 제1 정보 보호 수준을 계산하고, 상기 제2 정보를 보호하기 위한 제2 정보 보호 수준을 계산하는 단계를 포함하고,상기 제1 정보는 상기 복수의 버킷 각각에 대한 구간 정보를 보호하기 위하여 버킷을 나누는 기준 정보이고, 상기 제2 정보는 상기 복수의 버킷 각각에 포함되는 데이터 수를 보호하기 위하여 상기 카운트 노이즈를 생성하는 기준 정보인 클러스터링 방법
|
8 |
8
삭제
|
9 |
9
데이터 마이닝 시스템으로서,좌표 정보로 이루어진 복수의 데이터, 상기 데이터를 토대로 생성되는 복수의 버킷에 대한 제1 정보와 제2 정보를 보호하기 위한 정보 보호 수준, 상기 제1 정보와 제2 정보를 어느 정도의 비율로 보호할지 나타내는 정보 보호 수준 비율 그리고 K-평균 클러스터링을 실행하기 위한 클러스터 개수를 포함하는 입력 정보를 수신하고, 상기 수신한 정보들을 이용하여 상기 복수의 데이터를 쿼드 트리를 이용하여 복수의 버킷을 생성하며, 생성한 복수의 버킷에 대한 정보를 보호하여 차분 프라이버시를 만족하는 히스토그램을 생성하는 히스토그램 생성 모듈, 그리고상기 차분 프라이버시를 만족하는 히스토그램과 상기 복수의 데이터를 상기 클러스터 개수만큼의 클러스터에 분류하는 K-평균 클러스터링 모듈을 포함하는 데이터 마이닝 시스템
|
10 |
10
제9항에 있어서,상기 히스토그램 생성 모듈은,상기 데이터를 통해 생성되는 복수의 버킷에 포함될 데이터 수를 제한하기 위한 제1 임계값과, 동일한 버킷이 분할되는 분할 횟수를 제한하기 위한 제2 임계값을 계산하며,상기 제1 임계값은 상기 데이터의 수를 토대로 계산하고, 상기 제2 임계값은 상기 데이터의 수와 상기 복수의 데이터를 이루를 좌표의 차원(dimension)을 토대로 계산하는 데이터 마이닝 시스템
|
11 |
11
제10항에 있어서,상기 히스토그램 생성 모듈은,상기 정보 보호 수준과 상기 정보 보호 수준 비율을 이용하여, 상기 제1 정보를 보호하기 위한 제1 정보 보호 수준을 계산하고, 상기 제2 정보를 보호하기 위한 제2 정보 보호 수준을 계산하며,상기 제1 정보는 상기 복수의 버킷 각각에 대한 구간 정보를 보호하기 위하여 분할 대상인 버킷의 구간에 대한 기준 정보이고, 상기 제2 정보는 상기 복수의 버킷 각각에 포함되는 데이터 수를 보호하기 위하여 카운트 노이즈를 생성하는 기준 정보인 데이터 마이닝 시스템
|
12 |
12
제11항에 있어서,상기 히스토그램 생성 모듈은,상기 수신한 데이터의 분포를 확인하고 확인한 데이터 분포를 미리 설정된 수로 분할하여 복수의 초기 버킷을 생성하며, 상기 복수의 초기 버킷 각각에 포함된 데이터 수에 상기 카운트 노이즈가 반영된 데이터 수가 상기 제1 임계값보다 많은지, 상기 복수의 초기 버킷이 분할된 횟수가 상기 제2 임계값 보다 적은지 확인하여 복수의 새로운 버킷으로 생성하는 데이터 마이닝 시스템
|
13 |
13
제12항에 있어서,상기 생성한 복수의 새로운 버킷은 복수의 버킷의 구간과 상기 복수의 버킷 각각에 포함된 데이터 수가 상이한 데이터 마이닝 시스템
|
14 |
14
제12항에 있어서,상기 히스토그램 생성 모듈은,분할되어 생성된 각각의 버킷에 포함되어 있는 카운트 노이즈가 반영된 데이터 수와 상기 분할되어 생성된 각각의 버킷에 대한 구간 정보를 포함하여, 차분 프라이버시를 만족하는 히스토그램을 생성하는 데이터 마이닝 시스템
|