Korean Convergent Contents on Future Innovations Session 387
1. 서론
형식개념은 어떤 문제에 나타나는 다양한 데이터로부 터 객체와 속성들을 추출하고, 이로부터 개념들의 계층 구조를 형성하여 데이터를 분석하는데 적용될 수 있어, 다양한 컴퓨터 응용과학의 연구 방법에 응용되고 있다. 따라서 형식개념을 생성하는 효율적인 알고리즘에 대한 연구가 진행되고 있으며[1], 퍼지 및 러프집합으로 일반 화한 성질도 연구되고 있다[2]. 또한 기계학습법에 대한 연구에 형식개념분석기법을 이용하기도 하였다[3]. 속성 객체 맛 껍질 수분 시다 달다 두껍다 얇다 없다 많다 적다 사과 × × × × 배 × × × 귤 × × × 레몬 × × × 딸기 × × × 수박 × × × 대추 × × × 표 1. 과일과 그들에 관련된 속성들의 관계 컨텍스트(context)는 객체(object)들과 그들이 갖는 속 성(attribute)들로 구성된다. 표1은 과일과 그들이 갖는 속성들로 구성된 컨텍스트의 한 예를 나타낸 것이다. 이 예에서 어떤 과일이 어떤 속성을 갖는 경우에 그 과일의 행과 그 속성의 열이 교차하는 지점에 ×로 나타내었다. 집합 와 , 그리고 에서 로의 관계 로 구성 된 을 컨텍스트라 하고, 집합 의 원소를 객 체, 의 원소를 속성이라 한다. 위의 정의에서 관계 은 곱집합 × 의 부분집합 이고 객체 ∈ 가 속성 ∈ 를 가질 때 ∈ 또는 로 나타낸다. 가 컨텍스트일 때 각 각의 ⊆ 와 ⊆ 에 대하여 ∈ ∈ ∈, ∈ ∈ ∈ 로 정의하면, 임의의 ⊆ 와 ⊆ 에 대하여 다음 이 성립한다. (P) ⊆ ⇔ ⊆ 컨텍스트 에 대하여 , 를 만족하는 × 의 원소 를 이 컨텍스트의 개념이라 하고, 개념 에서 를 그 개념의 외연, 를 그 개념의 내포라 한다. 컨텍스트와 개념에 관한 정의 및 성질은 [4]에서 찾아볼 수 있다. 컨텍스트와 개념은 완비격자라는 수학적 구조의 한 예 이며, 두 함수 , 에 의해 결정되는 성질 (P)는 갈루아 커넥션의 특성을 그대로 반영하고 있다. 즉, 컨텍스트는 완비격자와 갈루아 커넥션의 이론으로 해석될 수 있다.2. 완비격자에서의 외연과 내포
공집합이 아닌 부분순서집합 의 임의의 부분집합 ⊆ 에 대하여 의 최소상계 ∨ 와 최대하계 ∧ 가 안에 존재할 때, 을 완비격자(complete lattice) 라 한다. 완비격자 의 최대원소를 , 최소원소를 로 나타낸다. 완비격자 , 에 대하여 다음의 성질 (DG)를 만족 하는 감소함수 → 와 → 의 순서쌍형식개념의 외연과 내포격자
Extent and Intent Lattice on Formal Concept
연 용 호 목원대학교
Yon yong-ho Mokwon Univ.
요약
형식개념(Formal Concept)은 외연(extent)과 내포(intent)를 이용하여 어떤 대상에 대한 정의를 내리거나, 그 대상들을 분류하여 군집화하기 위한 논리적 도구로 사용되어왔다. 여기에서 외연이란 객체(Object)들의 집합이고, 내포는 그 객체들이 지니고 있는 속성(Attribute)들의 집합이다. 이러한 형식개념은 어떤 문제에 나타나는 다양한 데이터로부터 객체와 속성들을 추출하고 이로부 터 개념(Concept)들의 계층구조(hierarchy)를 형성하여 데이터를 분석하는데 적용될 수 있다. 본 논문에서는 형식개념의 정의와 성질을 소개하고, 이를 일반화한 완비격자에서의 형식개념을 정의한다. 또한 이 형식개념에서의 외연과 내포격자에 대한 성질을 알아본다.
한국콘텐츠학회 2019 춘계종합학술대회 388 를 과 의 듀얼 갈루아커넥션(dual Galois connection)이라 한다. (DG) ≤ ⇔ ≤ 일반적인 갈루아커넥션은 ≤ ⇔ ≤ 를 만족하는 증가함수의 순서쌍 로 정의된다. 완비격 자와 갈루아커넥션의 정의와 성질은 [4, 5]에서 찾아볼 수 있다. 정리 1. 가 과 에서의 듀얼 갈루아커넥션이 면 임의의 ∈ , ∈ 에 대하여 다음이 성립한다. , 정리 2. 가 과 에서의 듀얼 갈루아커넥션이 면 임의의 ⊆과 ⊆ 에 대하여 다음이 성립한 다. (1) ∨ ∧ ∈, (2) ∨ ∧ ∈. 정리 3. 가 과 에서의 듀얼 갈루아커넥션이 면 , 는 각각최소상계와 최대하계가 ∨ ∨, ∧ ∧ ∨ ∨, ∧ ∧ 인 과 의 완비부분격자이다. 여기에서 ⊆ , ⊆ 이다. 또한, 와 는 크기순서가 역인 동형이다. 완비격자 , 와 함수 →, → 에 대하여 가 듀얼 갈루아커넥션이면, 함수 와 를 이용하여 컨텍스트의 형식개념과 유사한 정의를 내릴 수 있다. 즉 쌍대 갈루아 커넥션 을 갖는 완비격자 과 에서 , 를 만족하는 ∈× 를 개념(concept)이라 정의 하면, × 의 모든 개념들의 집합 는 다음과 같다. 위의 개념 에서 의 외연들의 집합과 내연들의 집 합은 각각 ∈ ∈, ∈ ∈ 이고, 정리 1에 의해 ∈ ∈, ∈ ∈ 이다. , 이고 정리 3에 의해 외연의 집합 와 내연의 집합 는 모두 완비격자이다. 완비격자 에서의 최소원소는 , 최대원소는 이고 의 최소원소 는 , 최대원소는 이다. 또한 와 가 부울 완비격자인 경우에 와 는 모든 원소에 대한 ∨-여원(∨-complement)과 ∧-여원(∧-complement) 을 갖는다. 실제로 임의의 ∈ 와 ∈ 에 대하여 ⊥ , ⊥ ⊥ , ⊥ 라 하면 ⊥∨ , ⊥∨ 이고, ⊥ ∧ , ⊥∧ 를 만족한다. 그러나 일반적으로 ∨ -여원과 ∧-여원은 같지 않으며, 집합 와 가 분배 격자임을 보장할 수 없다.
참 고 문 헌
[1] Kuznetsov S. O. and Obiedkov S. A., “Comparing performance of algorithms for generating concept lattices,” Journal of Experimental & Theoretical Artificial Intelligence, Vol 14, No. 2-3, pp. 189-216, 2002.
[2] Lai H. and Zhang D., “Concept lattices of fuzzy contexts: Formal concept analysis vs. rough set theory,” International Journal of Approximate Reasoning, Vol 50, pp. 695–707, 2009.
[3] Jabin S., “Machine Learning methods and applications using Formal Concept Analysis,” International Journal of New Technologies in Science and Engineering, Vol. 2, No. 3, pp. 152-163, 2015.
[4] Davey B. A. and Priestley H. A., Introduction to Lattices and Order, 2nd Ed., Cambridge University Press, 2002.
[5] Gierz G., Hofmann K. H, Keimel K., Lawson J. D., Misolve M. and Scott D. S., A Compendium of Continuous Lattices, Springer-Verlag, 1980.
