Database Summarization Using Fuzzy ISA Hierarchies

Presentation on theme: "Database Summarization Using Fuzzy ISA Hierarchies"— Presentation transcript:

1 Database Summarization Using Fuzzy ISA Hierarchies
전산학과 이도헌 박사 논문 발표 : 신명근

2 Table of Content 1. Introduction
2. Generalized tuples & Support Degree 3. Fuzzy Domain Knowledge 4. Summary Discovery Process 5. Example 6. Conclusion

3 Introduction Database Summary Database Summarization
임의의 database에서 찾아야 할 지식(knowledge) 사용자가 이해할 수 있는 정보의 요약(essence) Database Summarization A task that reduces a large number of actual database tuples into a relatively small number of generalized descriptions. i.e., generalized tuples

4 Example of Databse Summary
Program usage log in UNIX Database Summary Program User 사용시간 Generalized tuple : < editor, 프로그래머, 자정근처 > 설명 : editor 프로그램을 프로그래머들 이 자정 근처에 많이 사용한다. vi 류형규 23:30 emacs 장준영 23:55 vi 이근우 00:30

5 Fuzzy ISA Hierarchy Crisp ISA Hierarchy Fuzzy ISA Hierarchy
All programs All programs editor Documentation editor documentation 0.1 0.3 emacs vi word emacs vi word

6 Comparison of Crisp and Fuzzy ISA Hierarchies
Computer Uasge Log Using Crisp ISA Hierarchies - emacs : 120 records - vi : 680 records - word : 25 records Editor usage = = 800 Documentation usage = = 825 Using Fuzzy ISA Hierarchies Editor usage = = 800 Documentation usage = 120* * = 241

7 Fuzzy set primer A fuzzy set f on a domain D is defined by its membership function uf(x), which assign a fraction number between 0 and 1. 예, On domain < emacs, vi, word > documentaion = { 0.1, , } f1 is called a subset of f2 and denoted f1 ⊆ f2, iff ∀x ∈ D, uf1(x) ≤ uf2(x). w denotes a special fuzzy set such that ∀x ∈ D, uf(x) = 1

8 Definition: Generalized tuple
An m-ary tuple <f1, ..., fm> on an attribute scheme (A1, ..., Am), where fj’s are suzzy sets and Aj’s are attributes

9 Example of Generalized Tuple
Generalized Tuples <vi, 류형규> <emacs, 장준영> <editor, 프로그래머> Program User vi 류형규 emacs 장준영 Database의 모든 튜플은 generalized tuple이고, 두 개 이상 튜플의 특성을 총괄적으로 표현하는 것도 Generalized Tuple이다.

10 Definition : Support Degree
The support degree of a generalized tuple g = <f1, ..., fm> with respect to a given collection of database tuples C whose attribute scheme is (A1, ..., Am), is defined as SD(g|C) = [∑ti ∈ C [uf1(ti.A1), ..., ufm(ti.Am)]]/|C| wehre  is a t-norm operator, usually MIN. ufj(ti.Aj) denotes the membership degree of an attribute Aj of a tuple ti withrespect to a fuzzy set fj. |C| denotes the cardinality of the collection C 

11 Support Degree Support Degree는 해당 generalized tuple을 지지하는 튜플의 비율이다.
일정 threshold 값 이상의 Support Degree를 가지는 Generalized tuples을 qualified generalized tuples 라고 한다. Database Summarization == qualified generalized tuples를 찾는 것

12 Example of Support Degree
Program User Support <documentation, 사무원> vi 사무원1 (0.3, 1.0) = 0.3 word 사무원2 (1.0, 1.0) = 1.0 vi 류형규 (0.3, 0.0) = 0.0 SD(<documentation, 사무원> | C) = [ (0.3, 1.0) + (1.0, 1.0) ] / 3 = ( ) / 3 = 0.43 = 43 %  is a t-norm operator, 보통 MIN 을 사용

13 Fuzzy Set Hierarchy Fuzzy ISA Hierarchy ==> Fuzzy Set Hierarchy
Fuzzy ISA hierarchy to be used directly. All programs All programs 변환 editor Documentation editor documentation 0.1 0.3 emacs vi word emacs vi word

14 Summary Discovery Process

15 Example Collection & Fuzzy Set Hierarchies

16 Example(1/3) 1. Initail start < -, - > 2. Specialization
<engineering, -> <business, -> <game, -> <-, developer> <-, marketer> 3. Support Degree 계산 (t = 0.4)

17 Example(2/3) The 2’nd specialization of The 1’st specialization of
generalized tuples The 1’st specialization of the root generalized tuple

18 The 3’rd specialization of
Example(3/3) The 3’rd specialization of generalized tuple The final heiearchy of generalized tuples

19 결론 Proposed an Interactive top-down summary discovery process.
Which utilizes fuzzy ISA hierarchies as the domain knowledge. Defined generalized tuples as a representational form of a database summary.

20 Future Work Fuzzy ISA Hierarchy 대신에 KAH를 이용한 database summarization 방법을 찾을 수 있다. KAH에 Fuzzy ISA Hierarchy의 개념을 응용한다.