бд. Построение формальных понятий на БД. Методические указания к лабораторной работе Цель работы научиться реализовывать инструменты Анализа формальных понятий в базах данных
 Скачать 0.79 Mb.
|
|
Построение формальных понятий в базах данных Методические указания к лабораторной работе Цель работы: научиться реализовывать инструменты Анализа формальных понятий в базах данных. 2. КРАТКАЯ ТЕОРЕТИЧЕСКАЯ СПРАВКА 2.1. Объектно-признаковое представление данных Одной из наиболее часто применяемых в информационных системах структур данных является их объектно-признаковое представление. Пусть G – множество объектов, а M – множество их признаков, атрибутов, параметров – любые названия элементов множества M здесь допустимы. Объектно-признаковое представление – это, в общем случае, отношение, заданное на множествах G и M : I G M ⊆ × (1) Как всякое отношение, объектно-признаковое представление данных может быть представлено в виде матриц. При этом состав матрицы отношения (1) определяется конкретной задачей, решаемой на данных из множеств G и M. Поскольку реляционные базы данных строятся на основе теории отношений, данные их таблиц могут служить примером объектно- признакового представления, например, сведения о студентах, показанные на рис. 1. Здесь множество объектов – это студенты конкретной группы, множество признаков – сведения о студентах, составляющие поля таблицы. Рис. 1. Объектно-признаковое представление данных в виде таблицы базы данных. Как видно из рис.1, объектно-признаковое представление данных допускает данные различной природы – как числовые, так и символьные. 2.2. Формальные контексты и понятия Одним из вариантов объектно-признакового представления данных является формальный контекст. Он задаёт бинарное отношение (1). Формальный контекст имеет представление в виде матрицы инцидентности отношения I, состоящей из нулей и единиц, в которой ненулевые элементы обозначают факт принадлежности атрибута m M ∈ объекту g G ∈ На рис. 2 показана матрица формального контекста, построенного на множествах: G = { Lada Vesta Sport, Lada XRAY Cross, Audi Q8, BMW X7, Subaru Ascent, Lexus UX, Mazda F FL, Audi A6, Lada 4x4 II, Honda Accord 10 }, M = { Передний привод, Задний привод, Полный привод, Дизельный двигатель, Бензиновый двигатель, Отечественный, Иномарка } Рис. 2. Формальный контекст «Автомобили и их признаки» Формальные понятия. Связи между объектами и атрибутами в формальном контексте = ( , , ) G M I K определяются следующим образом. Для подмножеств A G ⊆ и B M ⊆ объектов и атрибутов задаются отображения(функции) : A A B ′ → и : B B A ′ → со следующими свойствами: : { | : , } : { | : , } A m M для всех g A g m I B g G для всех m B g m I ′ = ∈ ∈ < >∈ ′ = ∈ ∈ < >∈ (2) Пара множеств (A, B), таких, что , A B B A ′ ′ = = называется формальным понятием контекста K. Множества A и B замкнуты в силу композиции отображений: '' , '' A A B B = = . Множество A образует объем формального понятия (A, B), а множество B – его содержание. Если для понятий (A 1 , B 1 ) и (A 2 , B 2 ) 1 2 A A ⊆ , что эквивалентно 2 1 B B ⊆ , то (A 1 , B 1 ) ≤ (A 2 , B 2 ). В этом случае логично считать понятие (A 1 , B 1 ) менее общим, чем понятие (A 2 , B 2 ). Существует наглядный способ нахождения формальных понятий в матрице контекста: в матрице формального контекста формальные понятия (A, B) задаются максимальными по вложению подматрицами с ненулевыми элементами. Понятия – подстроки и понятия – подстолбцы в матрице контекста допустимы. Также допустимы перестановки строк и столбцов матрицы контекста. Поэтому в формальном контексте на рис. 2 существует формальное понятие: (A, B) = ({ Audi Q8, BMW X7, Subaru Ascent, Lexus UX, Mazda F FL, Audi A6, Honda Accord 10 }, { Иномарка }) (3) Это понятие задаётся подмножеством автомобилей и их признаками, для которых в правом крайнем столбце матрицы контекста указаны единицы (крестики). 2.3. Решетки понятий Решетки понятий применяются в направлении современного анализа данных, известном как Анализ формальных понятий [1]. Анализ формальных понятий имеет строгое математическое обоснование. Он основан на математической теории решеток [2]. Решетка понятий – это модель, отражающая структуру формальных понятий в формальном контексте. Она определяется следующей теоремой. ТЕОРЕМА [1]. Частично упорядоченное по вложению объемов множество формальных понятий формального контекста K образует математический объект - решетку, которая называется решетка понятий. В Приложении 1 помещены сведения об упорядоченных множествах и решетках, поясняющие эти понятия. На рис. 3 изображена решетка понятий контекста на рис. 2. Для иллюстрации контекста и решетки понятий использовано программное средство [3]. Рис. 3. Решетка понятий формального контекста на рис. 2. Каждое формальное понятие представляет собой сочетание данных из множеств G и M. Вырожденные, тривиальные понятия, в которых есть только объекты или только атрибуты, помещаются в особые, верхний и нижний узлы решётки. Так на рис. 3 верхний узел задает понятие, в котором только признаки автомобилей, а нижний узел – понятие, в котором только названия автомобилей. Внутренние узлы решётки понятий могут быть окрашены полностью, наполовину или не окрашены совсем. Этим определяется компактное представление объектов и атрибутов в решётке понятий. В каждом внутреннем узле решётки показаны только те атрибуты или объекты, которые добавляются в него из тех узлов, с которыми он связан маршрутом. При движении по диаграмме вверх в каждый последующий узел добавляются объекты из расположенных ниже узлов, связанных с данным узлом маршрутами. Соответственно, при движении по диаграмме вниз от верхнего узла графа решётки в последующие узлы-понятия «собираются» атрибуты из расположенных выше узлов, связанных с ними маршрутами. Неокрашенные узлы являются «техническими» - они нужны для объединения других узлов, чтобы корректно связывать их с другими узлами, не нарушая свойств решётки на её диаграмме. На рис. показан фрагмент решётки на рис. 3 – её подрешётка понятий с выделенными атрибутами «Иномарка» и «Задний привод». Рис. 4. Подрешётка понятий с атрибутами «Иномарка» и «Задний привод». Из рис. 3 видно, что атрибут «Иномарка» попадает во все понятия, где есть выделенные названия иностранных автомобилей. В то же время, он не попадает в понятия, в которых есть названия отечественных автомобилей, поскольку туда не ведёт ни один маршрут из понятия с атрибутом «Иномарка». Кроме выделенных на рис. 4 атрибутов, в понятия, содержащие названия иностранных автомобилей, входят атрибуты, «доставленные» в них из других узлов, связанных с ними маршрутами. Например, это атрибут «Бензиновый двигатель», доставляемый автомобилям Honda Accord 10 и Audi Q8. Решетка понятий, построенная на формальном контексте, является инструментом представления и извлечения знаний из данных контекста. В роли знаний выступают понятия, организованные иерархично. Это позволяет представлять знания, выражающиеся понятиями, характеризующимися меньшей и большей общностью, меньшими и большими объемом и содержанием. Инструментом извлечения знаний на решетках понятий являются методы Data Mining, использующие модели в виде: • импликаций, • функциональных зависимостей, • ассоциативных правил. Импликации X Y → на подмножествах признаков , X Y M ⊆ имеют место, если ' ' X Y ⊆ , т.е. каждый объект, обладающий всеми признаками из множества X, также обладает всеми признаками из множества Y. В решетке на рис. 3 имеем импликации: Рис. 5. Импликации, соответствующие решётке понятий на рис. 3. Ассоциативные правила отличаются от импликаций. Они также строятся на множествах сочетаний атрибутов, но имеют ограничения в виде параметров, среди которых основными являются поддержка и доверие. Ассоциативным правилом называется выражение X Y → при условии , X Y M ⊆ Поддержка ассоциативного правила вычисляется следующим образом: | ( )' | ( ) | | X Y s X Y G ∪ → = , (4) где модули |.| означают число элементов в множествах. Доверие ассоциативного правила вычисляется по-другому: | ( )' | ( ) | ' | X Y c X Y X ∪ → = (5) Смысл параметра поддержка заключается в нахождении заданного (обычно в процентном отношении) числа наборов данных, содержащих подмножества , X Y . Формально поддержка вычисляется в виде количества объектов, удовлетворяющих выражению (4). Параметр доверие вычисляется уже на правилах, а не на наборах данных. Смысл его в том, насколько можно доверять правилам, аргументами которых являются наборы X. Также как и поддержка, доверие вычисляется в виде количества объектов, удовлетворяющих выражению (5). На рис. 6 показаны ассоциативные правила, построенные на решётке на рис. 3 с доверием больше 60%. Рис. 6. Ассоциативные правила, соответствующие решётке понятий на рис. 3. На основе множества импликаций и ассоциативных правил на решетках понятий строится система навигации, позволяющая находить частные и общие понятия для заданного входа – узла решетки. В этом состоит большое преимущество решеток понятий как концептуальных моделей извлечения знаний. 3. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ РАБОТЫ 3.1. В работе используется СУБД SAP-Sybase и средство разработки приложений Sybase PowerBuilder. 3.2. Также для построения решёток понятий, импликаций и ассоциативных правил необходимо применять свободно распространяемое программное средство ConceptExplorer [3]. Запуск программы ConceptExplorer из программы на языке Powerscript: OleObject wsh wsh = CREATE OleObject; wsh.ConnectToNewObject( "WScript.Shell" ) wsh.Run('conexp-ng-0.7.0.jar .\'+filename) wsh.disconnectobject( ) 4. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ. 1. Ознакомиться с теоретической справкой. 2. В используемой в предыдущих работах базе данных определить таблицы, для которых целесообразно строить формальный контекст. 3. Построить бинарный формальный контекст для таблиц базы данных, найденных в предыдущем пункте. 4. На формальном контексте построить решётку понятий и её подрешётки для выделенных понятий. 5. Исследовать системы импликаций и ассоциативных правил на построенной решётке понятий. 6. Ответить на контрольные вопросы. КОНТРОЛЬНЫЕ ВОПРОСЫ. 1. В формальном контексте на рис. 2 не хватает данных. Каких? 2. Известно, что полный привод – это передний и задний. Как это можно определить из решётки понятий на рис.3? 3. Является ли понятием подматрица – строка (столбец) в матрице формального контекста? 4. В чем различие в определении импликаций и ассоциативных правил? 5. Объясните набор импликаций на рис. 3. Что означают числа в столбцах слева? 6. Объясните, чем отличаются ассоциативные правила на рис. 6 от импликаций на рис. 5? 7. Объясните содержимое 4-й строки ассоциативных правил на рис. 6. 8. Всегда ли решетка задает отношение включения? Приведите примеры. 9. Доказать эквивалентность обоих определений решетки 10. Что такое OLE ? СПИСОК ЛИТЕРАТУРЫ 1. Электронный ресурс: https://bi.hse.ru/data/2013/01/30/1304788259/ИгнатовАФП.pdf 2. Биркгоф Г. Теория решеток. М.: Наука, 1984. 284 с. 3. Электронный ресурс: http://conexp.sourceforge.net/download.html 4. Электронный ресурс: https://www.java.com/ru/ 5. Ganter, Bernhard; Stumme, Gerd; Wille, Rudolf, eds., Formal Concept Analysis: Foundations and Applications, Lecture Notes in Artificial Intelligence, No. 3626, Springer-Verlag, 2005. 6. Michael Bogatyrev and Alexey Kolosoff. Using Conceptual Graphs for Text Mining in Technical Support Services. Pattern Recognition and Machine Intelligence. - Lecture Notes in Computer Science, 2011, Volume 6744/2011, p.p. 466-471. Springer-Verlag. Heidelberg. 2011. Приложение 1. Упорядоченные множества и решетки Упорядоченным множеством P называется непустое множество, на котором определено бинарное отношение ≤ , удовлетворяющее для всех P z y x ∈ , , следующим условиям: 1. Рефлексивность: x x ≤ 2. Антисимметричность. Если y x ≤ и x y ≤ , то y x = 3. Транзитивность. Если y x ≤ и z y ≤ , то z x ≤ Если y x ≤ и y x ≠ , то говорят, что x меньше y или y больше x , и пишут y x < или x y > . Примеры упорядоченных множеств: 1. Множество целых положительных чисел, а y x ≤ означает, что x делит y 2. Множество всех действительных функций ) (x f на отрезке ] ; [ b a и g f ≤ означает, что ) ( ) ( x g x f ≤ для ] ; [ b a x ∈ ∀ Цепьюназывается упорядоченное множество, на котором для любых y x, имеет место y x ≤ или x y ≤ . Используя отношение порядка, можно получить графическое представление любого конечного упорядоченного множества P. Изобразим каждый элемент множества P в виде небольшого кружка, располагая x выше y, если y x > . Соединим x и y отрезком. Полученная фигура называется диаграммой упорядоченного множества P. Примеры диаграмм упорядоченного множества приведены на рис. 1: Рис. П1. Диаграммы упорядоченных множеств. Верхней гранью подмножества Х в упорядоченном множестве Р называется элемент a из Р, больший или равный всех x из X. Точная верхняя грань подмножества X упорядоченного множества P – это такая его верхняя грань, которая меньше любой другой его верхней грани. Обозначается символом sup X и читается «супремум X». Согласно аксиоме антисимметричности упорядоченного множества, если точная верхняя грань существует, то она единственна. Понятия нижней грани и точной нижней грани (которая обозначается inf X и читается «инфимум») определяются двойственно. Также, согласно аксиоме антисимметричности упорядоченного множества, если точная нижняя грань X существует, то она единственна. Решёткой , L < ≤ > называется упорядоченное множество L, в котором любые два элемента x и y имеют точную нижнюю грань, обозначаемую y x ∧ , и точную верхнюю грань, обозначаемую y x ∨ [1] Примечание. Любая цепь является решёткой, т.к. y x ∧ совпадает с меньшим, а y x ∨ с большим из элементов y x, Характерные примеры показаны на рис. 2. Наибольший элемент, то есть элемент, больший или равный каждого элемента упорядоченного множества, он обозначен 1, а наименьший элемент, то есть меньший или равный каждого элемента упорядоченного множества, обозначен 0. Рис. П2. Примеры диаграмм решеток На решётке можно рассматривать две бинарные операции: b a b a ∨ = + - сложение и b a b a ∧ = ⋅ - произведение Эти операции обладают следующими свойствами: 1. a a a = + , a a a + ⋅ идемпотентность; 2. a b b a + = + , a b b a ⋅ = ⋅ коммутативность; 3. ) ( ) ( c b a c b a + + = + + , ) ( ) ( c b a c b a ⋅ ⋅ = ⋅ ⋅ ассоциативность; 4. a b a a = + ⋅ ) ( , a b a a = ⋅ + законы поглощения. ТЕОРЕМА 1. Пусть L - множество с двумя бинарными операциями ⋅ + , , обладающими свойствами (1) – (4). Тогда отношение b b a b a = + ⇔ ≤ (или a b a = ⋅ ) является порядком на L, а возникающее упорядоченное множество оказывается решёткой, причём: b a b a ∨ = + и b a b a ∧ = ⋅ Приложение 2. Краткая инструкция по применению программы Concept Explorer. Система Concept Explorer работает на платформе Java. Это означает, что на компьютере, где запускается Concept Explorer, должна быть установлена виртуальная машина Java. Установить ее можно, используя ресурс [4]. После установки виртуальной машины Java Concept Explorer запускается инициализацией файла conexp.jar или файла conexp.bat. Главное окно системы Concept Explorer показано на рис. 6. Система имеет интуитивно понятный интерфейс, элементы которого показаны на рисунке. Система Concept Explorer имеет следующие функции: • построение и редактирование контекстов; • построение решеток понятий; • построение базиса импликаций, допускаемых решеткой понятий; • построение базиса ассоциативных правил, допускаемых решеткой понятий. Рис. П3. Главное окно системы Concept Explorer. Построение и редактирование контекстов выполняется в редакторе контекстов. Система стартует, предъявив пустой контекст. Строки и столбцы матрицы контекста размечены как пронумерованные объекты (Obj*) и атрибуты (Attr*). Задание элементов контекста выполняется двойным кликированием клетки контекста, что приводит к появлению знака «Х» в клетке. Этим устанавливается факт принадлежности атрибута Attr* объекту Obj*. Редактор контекстов Вызов построителя решеток Окно параметров |