| 1 |
1
그래프 데이터베이스에 저장되어 있는 다수 그래프 사이의 빈발 부분그래프를 생성하는 방법에 있어서,후보 빈발 부분그래프 생성부에서 상기 다수 그래프 사이에서 최소 지지도 이상으로 발현하는 후보 빈발 부분그래프를 생성하는 단계;그룹화부에서 초기 유사 그룹을 구성하는 후보 빈발 부분그래프의 특징 벡터의 평균값으로부터 중심 벡터를 계산하여 상기 중심 벡터와 상기 후보 빈발 부분그래프의 특징 벡터 사이의 유사도를 계산하고, 상기 유사도에 기초하여 가장 높은 유사도를 가지는 초기 유사 그룹에 상기 후보 빈발 부분그래프를 포함시켜 유사 그룹으로 그룹화하는 단계;특징 빈발 부분그래프 생성부에서 상기 각 유사 그룹에서 분류력이 가장 높은 후보 빈발 부분그래프를 특징 빈발 부분그래프로 선택하는 단계; 및빈발 부분그래프 생성부에서 상기 특징 빈발 부분그래프로 상기 다수 그래프의 빈발 부분그래프를 생성하는 단계를 포함하는 것을 특징으로 하는 빈발 부분그래프의 생성 방법
|
| 2 |
2
제 1 항에 있어서, 상기 후보 빈발 부분그래프는정규화 연산을 통해 최소 DFS 코드를 가지는 빈발 부분그래프인 것을 특징으로 하는 빈발 부분그래프의 생성 방법
|
| 3 |
3
제 2 항에 있어서, 상기 그룹화하는 단계는상기 유사 그룹이 동일하게 유지될 때까지 반복하여 유사 그룹을 생성하는 것을 특징으로 하는 빈발 부분그래프의 생성 방법
|
| 4 |
4
삭제
|
| 5 |
5
제 1 항에 있어서, 상기 후보 빈발 부분그래프의 분류력은 레이블 종류별 밀질 정도를 나타내는 분류값에 기초하여 계산되는 것을 특징으로 하는 빈발 부분그래프의 생성 방법
|
| 6 |
6
제 5 항에 있어서, 상기 분류값(I)은 아래의 수학식(1)에 의해 계산되며,[수학식 1]여기서 H(Y)는 그래프의 레이블 종류별 밀집도를 나타내며, H(Y｜fi)는 후보 빈발 부분그래프의 레이블 종류별 밀집도를 나타내며,여기서 H(Y)과 H(Y｜fi) 각각 아래의 수학식(2)와 수학식(3)에 의해 계산되며,[수학식 2] [수학식 3]여기서 n은 그래프의 총수, ca는 제1 레이블을 가지는 그래프의 수, ci는 제2 레이블을 가지는 그래프의 수, Pci, Pdi, nci, caci, cbci, ndi, cadi, cbdi 는 각각 i번째 후보 빈발 부분그래프의 발현 확률, 비발현 확률, 전체 발현 빈도 수, 제1 레이블의 발현 빈도 수, 제2 레이블의 발현 빈도 수, 전체 비발현 빈도 수, 제1 레이블의 발현 빈도 수, 제2 레이블의 발현 빈도 수인 것을 특징으로 하는 빈발 부분그래프의 생성 방법
|
| 7 |
7
제 1 항 내지 제 3 항, 제 5 항, 제 6 항 중 어느 한 항에 있어서, 상기 빈발 부분그래프의 생성 방법은동시 빈발 부분그래프 생성부에서 상기 특징 빈발 부분그래프로 이루어진 후보 동시 빈발 부분그래프를 생성하는 단계; 및상기 빈발 부분그래프 생성부에서 상기 후보 동시 빈발 부분그래프의 분류력에 기초하여 추가 동시 빈발 부분그래프를 결정하는 단계를 더 포함하며,상기 빈발 부분그래프 생성부는 상기 추가 동시 빈발 부분그래프를 상기 빈발 부분그래프에 추가하여 빈발 부분그래프를 생성하는 것을 특징으로 하는 빈발 부분그래프의 생성 방법
|
| 8 |
8
제 7 항에 있어서, 상기 후보 동시 빈발 부분그래프의 분류력이 임계 분류력을 초과하는 경우 추가 동시 빈발 부분그래프로 결정하는 것을 특징으로 하는 빈발 부분그래프의 생성 방법
|
| 9 |
9
그래프 데이터베이스에 저장되어 있는 다수 그래프 사이의 빈발 부분그래프를 생성하는 장치에 있어서,상기 다수 그래프 각각에 대해 정규화 연산을 통해 최소 DFS 코드를 가지는 부분그래프를 생성하며, 생성한 부분그래프에서 최소 지지도 이상으로 발현하는 후보 빈발 부분그래프를 생성하는 후보 빈발 부분그래프 생성부;초기 유사 그룹을 구성하는 후보 빈발 부분그래프의 특징 벡터의 평균값으로부터 중심 벡터를 계산하는 중심 벡터 계산부와, 상기 중심 벡터와 상기 후보 빈발 부분그래프의 특징 벡터 사이의 유사도를 계산하는 유사도 계산부와, 상기 유사도에 기초하여 가장 높은 유사도를 가지는 초기 유사 그룹에 상기 후보 빈발 부분그래프를 포함시켜 유사 그룹을 생성하는 유사 그룹 생성부를 구비하는 그룹화부; 및상기 각 유사 그룹에서 분류력이 가장 높은 후보 빈발 부분그래프를 특징 빈발 부분그래프로 선택하고 상기 특징 빈발 부분그래프로 빈발 부분그래프를 생성하는 빈발 부분그래프 생성부를 포함하는 것을 특징으로 하는 빈발 부분그래프의 생성 장치
|
| 10 |
10
제 9 항에 있어서, 상기 빈발 부분그래프의 생성 장치는상기 특징 빈발 부분그래프로 이루어진 후보 동시 빈발 부분그래프를 생성하는 동시 빈발 부분그래프 생성부를 더 포함하며,상기 빈발 부분그래프 생성부는 상기 후보 동시 빈발 부분그래프의 분류력에 기초하여 추가 동시 빈발 부분그래프를 결정하며, 상기 추가 동시 빈발 부분그래프를 상기 빈발 부분그래프에 추가하여 빈발 부분그래프를 생성하는 것을 특징으로 하는 빈발 부분그래프의 생성 장치
|
| 11 |
11
제 10 항에 있어서, 상기 그룹화부는 상기 초기 유사 그룹과 상기 유사 그룹을 비교하여 서로 동일한지 판단하는 유사 그룹 비교부를 더 포함하며,상기 유사 그룹 비교부는 상기 초기 유사 그룹과 상기 유사 그룹이 동일하지 않은 경우, 상기 유사 그룹을 초기 유사 그룹으로 갱신하여 신규 유사 그룹을 생성 제어하는 것을 특징으로 하는 빈발 부분그래프의 생성 장치
|
| 12 |
12
제 11 항에 있어서, 상기 후보 빈발 부분그래프의 분류력은 레이블 종류별 밀질 정도를 나타내는 분류값에 기초하여 계산되는 것을 특징으로 하는 빈발 부분그래프의 생성 장치
|
| 13 |
13
제 12 항에 있어서, 상기 분류값(I)은 아래의 수학식(4)에 의해 계산되며,[수학식 4]여기서 H(Y)는 그래프의 레이블 종류별 밀집도를 나타내며, H(Y｜fi)는 후보 빈발 부분그래프의 레이블 종류별 밀집도를 나타내며,여기서 H(Y)과 H(Y｜fi) 각각 아래의 수학식(5)와 수학식(6)에 의해 계산되며,[수학식 5] [수학식 6]여기서 n은 그래프의 총수, ca는 제1 레이블을 가지는 그래프의 수, ci는 제2 레이블을 가지는 그래프의 수, Pci, Pdi, nci, caci, cbci, ndi, cadi, cbdi 는 각각 i번째 후보 빈발 부분그래프의 발현 확률, 비발현 확률, 전체 발현 빈도 수, 제1 레이블의 발현 빈도 수, 제2 레이블의 발현 빈도 수, 전체 비발현 빈도 수, 제1 레이블의 발현 빈도 수, 제2 레이블의 발현 빈도 수인 것을 특징으로 하는 빈발 부분그래프의 생성 장치
|
