[빅데이터] 4. Data Generalization by Attribute-Oriented Induction

 Data Generalization by Attribute-Oriented Induction

1.      Concept description : 데이터 일반화의 한 형태이다.

l  Concept는 일반적으로 데이터 집합(예, 구매자의 숫자나 졸업생의 숫자)을 말하지만,

   Concept Description은 단순한 데이터의 배열이 아니라 data characterization and comparison(데이터 묘사 와 비교)에 대한 서술을 생성한다.

l  Characterization(묘사,정의) : 주어진 데이터 집합의 간결하고 간단명료한 요약을 제공한다.

l  Comparison(a.k.a Discrimination)(비교,차이): 두 개 이상의 데이터 집합에 대한 비교를 서술한다.

l  Concept Description에는 두 가지의 접근 방식이 있다. 하나는 Data Cube(or OLAP)과 Attribute-Oriented Induction이 있다.

l  이제까지 살펴본 OLAP은 Complex data types and aggregation 과 User Control versus automation 때문에 한계가 존재. 즉 복잡한 데이터 형태에 적용하기 힘들며, 사용자가 OLAP에서 잘 알아야 하기 때문에 힘든 점이 있다.

2.      Attributed-Oriented Induction for Data Characterization

①     Data Cube Approach가 제안되기 몇 년 전에 제안되었다.

②     쿼리기반(Query-Oriented), generalization-based, 온라인 데이터 분석기법이다.

③     일반적인 처리 방법

l  관계형 데이터베이스 쿼리를 이용해서 작업과 연관된 데이터를 수집(Initial working relation)

l  Attribute 제거와 Attribute 일반화를 통해서 일반화 한다.

l  일반화된 Tuple에서 동일한 것들을 병합하고 각각 그것들의 개수를 누적해서 집합(aggregation)을 만든다.

④     처리 상세

l  Data Focusing : AOI 전에 관계형 데이터베이스 쿼리를 이용해서 연관된 데이터를 먼저 추출해야 한다. 

                     이 추출된 데이터를 initial working relation이라고 말한다.

l  Attribute removal : Attribute의 distinct value가 많이 존재할 때, 일반화 오퍼레이터가 없거나(case1)(즉 개념계층이 존재하지 않을 때) 상위 레벨 개념이 다른 Attribute의 용어에서 나타난다면(case2) 삭제한다.

l  Attribute generalization : Attribute의 distinct value가 많이 존재하고 일반화 오퍼레이터가 있으면 일반화 시킨다.

⑤     Attribute removal과 Attribute generalization은 모두 distinct value가 큰 데이터 셋에서만 적용이 된다. 여기서 얼마나 큰지를 결정하는 것은 지극히 주관적인데 그것을 제어하는 2가지의 방법이 존재한다.

l  Attribute generalization threshold control

I.       모든 Attribute에 적용되는 하나의 일반화 한계를 설정하거나 각각의 Attribute에 하나의 한계를 설정하는 방법이 있다

II.      만약 유일한 값을 가지는 속성들이 한계점보다 개수가 많다면 앞으로의 속성들은 삭제가 되거나 일반화가 된다.

III.    보통 기본적으로 2 에서 8 의 범위로 설정이 되어 있는데 사용자에 따라서 줄이거나 늘릴 수 있다.

IV.    만약 일반화가 너무 높은 레벨까지 진행이 되었다고 느껴졌다면 한계점을 높임으로써 레벨을 조절(낮추다)할 수가 있다.

V.      즉, Attribute Value에 한계점을 설정한다.

l  Generalized relation threshold control

I.       일반화된 연관에 대한 한계치를 설정한다.

II.      만약 일반화된 연관의 tuple의 개수가 한계점보다 많으면 계속 진행이 되며, 그렇지 않을 경우(적으면) 앞으로의 일반화가 수행이 되지 않는다. 즉 한계점의 개수보다 작아질 때 까지 일반화를 수행한다.

III.    시스템에 보통 10~30으로 설정이 되어있다.

IV.    만약 일반화된 연관이 너무 작다면 한계점을 사용자가 높여서 조절이 가능하다.(drilling down), 반대는 rolling up 이 된다

V.      일반화된 Tuple에 대한 한계점을 설정한다.

⑥     일반화를 처리하면 동일한 Tuple이 생성되는데 이것들을 통합해서 Count Attribute를 생성해서 개수를 설정하고 하나만 남기고 나머지들을 삭제한다.

3.      Basic algorithm for attribute-oriented induction

n  Input

n  Output: P, a prime-generalized-relation

 

①     W←get_task_relevant_data(DMQuery,DB)

l  DB에서 작업관 연관된 데이터를 추출해서 W(Working Relation)에 넣는다.(Initial Releation)

②     Prepare_for_generalzation(W)

I.       W를 스캔해서 각각의 Attribute의 distinct value들을 수집한다.

II.      각각의 Attribute에 대해서 삭제할 것인지, 아니면 주어진 값 또는 기본 Attribute의 한계점에 기본으로 해서 일반화 시킬 것인지 판단한다.

③     P←generalization(W)

The Prime-generalization-relation P 는 2번의 결과로 생성된 일반화된 relation의 Tuple에서 동일한 것들은 삭제하고 하나만 남기고 개수를 계산해서 하나의 attribute를 생성한다.

이 과정은 아래의 두 가지 중에서 하나를 사용해서 더 효율적으로 만들 수 있다.

l  각각의 일반화된 tuple에 대해서, 정렬된 prime relation P에 바이너리 검색을 통해서 자료를 입력한다. 이때 이미 있으면 count와 다른 누적되는 값을 계산해주고 없으면 새로 넣어준다.(like hashtable)

l  대부분의 경우에 distinct value들이 개수가 적기 때문에 m-차원 배열로 생성한다. 각각의 배열은 count 와 다른 집합 값이 존재한다. 일반화된 tuple을 입력 시에 해당 배열의 집합 값을 증가시킨다.(like array)

4.      AOI Examples

①     name : 많은 distinct values가 존재하지만 일반화하는 연산자(generalization operator)가 존재하지 않기 때문에 삭제한다. Attribute Removal

②     gender : 2가지의 distinct value 만 존재하기 때문에 일반화도 필요가 없고 그대로 유지시킨다.

③     major : 개념계층이 이미 존재한다고 가정하고, 또한 attribute generalization threshold가 5로 설정이 되어있다고 가정했을 때 이 Attribute에는 20개가 넘는 distinct values가 존재하기 때문에 주어진 개념계층으로 일반화가 진행이 된다.

④     birth_place : 개념 계층이 존재할 때, country의  distinct values가 한계점보다 많으면 삭제되어야 한다. 왜냐하면, 일반화 연산자(country)는 있지만 한계점보다 더 작아질 수 없기 때문이다. 즉 이미 유일한 country의 개수가 한계점보다 높기 때문에 더 상위 개념이 없기 때문에 삭제된다. 만약 한계보다 작다면 birth_country로 일반화 된다.

⑤     birth_date : 개념계층이 존재하고 distinct value가 한계보다 작다면 일반화 된다.

⑥     residence : 특성이 number, street, residence city, residence province or state, and residence country 로 구성되어 있다면 너무나 많은 disctinct value가 존재하기 때문에 삭제되어야 한다. Residence_city로 일반화 시키기 위해서 number와 street를 삭제한다.

⑦     phone#: name과 같으므로 삭제한다.

⑧     gpa: 개념계층이 {3.75–4.0, 3.5–3.75, . } 형식의 구간으로 존재한다고 가정하면 {“excellent”, “very good”, .} 형식의 서술형 값으로 교체해서 일반화 시킨다.

⑨     마지막으로 일반화된 tuple이 동일한 것은 count로 개수를 추가해주고 하나만 남겨준다.

5.      Attributed-Oriented Induction for Class Comparison

n  이전까지는 하나의 class에대해서만 Data Generalization을 했는데 두개 이상의 class를 비교하는 것을 Class Comparison(a.k.a. discrimination)이라고 한다. 주의할 점은 비슷한 dimension 과 attributes를 가지고 있어야 한다. 완전히 다른 것은 비교를 할 수가 없다는 것을 주의해야 한다.

n  수행방법은 아래와 같은 절차로 진행된다. (졸업생과 재학생의 일반적인 특성을 비교한다고 가정하면..)

①     Data Collection

l  Query Processing을 이용해서 연관성 있는 데이터를 수집한다.

l  DMQL은 Relational Database에 맞는 SQL 구문으로 변환이 된다.

l  연관데이터는 target class와 하나 또는 여러 개 집합의 contrasting class로 각각 나뉜다.

②     Dimension relevance analysis

l  많은 차원(dimensions,colums)들이 존재하면 아주 높은 연관성 있는 데이터를 위해서 Correlation 또는 Entropy-based measures 로 연관성 높은 것만 선택을 해준다.

l  name,gender, birth place, residence, and phone# 같이 연관성 적은 것들 것은 삭제가 된다.

③     Synchronous generalization

l  먼저 target class에 대해서 사용자 또는 전문가에 의해서 설정된 Threshold에 의해서 일반화를 한다.(Prime target class relation)

l  Constrasting class에 대해서는 prime target class relation과 같은 레벨로 일반화를 진행한다.

④     Presentation of the derived comparison

l  테이블,그래프,rules 등의 방법으로 visualization을 한다.

l  보통 presentation에는 비교하는 단위인 count%(percentage count)가 포함이 된다.

n  

참고문헌:Data Mining Concepts and Techniques, 3rd Edition, Jiawei Han & Micheline Kamber

저작권 문제가 발생시 삭제될 수 있습니다.