РАЗДЕЛ 2
РАЗРАБОТКА МЕТОДА ПОСТРОЕНИЯ АГРЕГИРОВАННЫХ АССОЦИАТИВНЫХ правил МЕЖДУ
ДИСКРЕТНЫМИ ПРИЗНАКАМИ
Проведенный анализ методов поиска ассоциативных правил показывает, что все
вышеперечисленные методы и алгоритмы их реализующие, работают только с
бинарными признаками (т.е. признак либо присутствует в записи – принимает
значение единица, либо нет – принимает значение нуль). В реальных же базах
данных часто признаки могут принимать значения из некоторого набора (множества
значений), т.е. являются небинарными величинами. Бинарные признаки являются
лишь частным случаем более общего подхода – множество значений состоит из двух
элементов – 0 и 1. Безусловно, различные типы баз данных могут содержать разное
количество подобных признаков. Например, в базе данных крупного универмага
фиксируется сам факт наличия или отсутствия покупки данного наименования товара
(бинарный случай). Однако, например, для базы данных страховых компаний
небинарные величины достаточно актуальны: уровень образования клиентов
(неполное среднее, среднее, высшее), вкладчиком какого банка является клиент,
его местожительство, размер вклада и т.д. Медицинские БД, содержащие записи о
состоянии здоровья пациентов, также имеют дело с признаками, которые могут
принимать значения из множества возможных: уровень гемоглобина в крови,
артериальное давление, температура и т.д. Следует отметить, что немало
непрерывных величин могут сводиться к небинарным: врач, измеряя артериальное
давление, отмечает границы – верхнее давление до 90, от 90 до 140, от 140 до
200, выше 200. Попытка разбивать непрерывные величины на интервалы была
предпринята американским ученым Шрикантом [70]. Однако предлагаемый им подход
плохо применим к дискретным небинарным признакам, т.к. предполагает объединение
только соседних интервалов, например: "уровень кровяного давления от 120 до
140" и "уровень кровяного давления от 140 до 160" дает при объединении значения
"от 120 до 160". Если же речь идет о дискретных величинах типа: "район
проживания клиента компании", "пакет услуг, которым он пользуется" и т.д., то
разработанных методов и алгоритмов нахождения ассоциаций в этом направлении
пока не существует.
Таким образом, разработка методов построения ассоциативных правил для
небинарных величин представляется весьма своевременной.
2.1. Метод построения агрегированных ассоциативных правил для небинарных
значений признаков
2.1.2. Нахождение агрегированных ассоциативных правил путем объединения ветвей
дерева покрытий
Предлагается дальнейшее развитие метода генерации ассоциативных правил с
использованием дерева покрытий. Это позволяет получать агрегированные
ассоциативные зависимости для признаков, не являющихся бинарными величинами
[28]. Предлагаемый модифицированный метод разработан для признаков объектов в
БД, принимающими значения из множества возможных, и позволяет строить правила
вида: "Если признак X принимает значения из множества {a1,...ai}, то признак Y
принимает значения из множества {b1,...,bk}". Следует отметить, что данный
подход позволяет проводить как агрегацию признаков, являющихся непрерывными
величинами и разбитыми на интервалы (возраст, размер доходов, уровень
артериального давления), так и признаков, являющихся дискретными величинами
(местожительство клиента банка, образование, пакет услуг, предоставляемых
компанией и т.д.).
Для описания подобных величин использовался аппарат алгебры конечных
предикатов.
Если признак объекта может принимать значения из множества , тогда такой
признак может быть описан с помощью конечного предиката следующим образом:
Предикат как бы "узнает" значение признака среди всех возможных значений [87,
88].
Имеют место следующие тождества:
, (2.1)
(2.2)
Действительно, признак X принимает какое-либо значение из возможного набора, а,
следовательно, всегда один из дизъюнктивных членов, а вместе с ним и вся
дизъюнкция (2.1) обращается в 1, и признак X не может принимать одновременно
два различных значения (2.2).
Подобное описание позволяет не использовать отрицание признаков: если признак
не принимает значение , то он принимает любое значение из оставшегося набора
признаков, т.е. . В случае бинарных признаков для их описания используется
унарный предикат, различающий два значения – 0 и 1: и .
Таким образом, не требуется строить отдельные алгоритмы для нахождения
ассоциативных правил с отрицанием. Нахождение исключающей ассоциации (т.е.
ассоциативного правила, включающего отрицание какого-либо признака), данной в
[48] сводится к нахождению обычного покрытия, в которое могут входить предикаты
вида .
Для получения дерева покрытий, необходимого для работы предлагаемого метода
(подготовительный этап генерации агрегированных ассоциаций), используем
алгоритм, предложенный в [48], модифицировав его следующим образом (рис. 2.1).
Рис.2.1. Модифицированный алгоритм построения дерева покрытий
Таким образом, модификация алгоритма состоит в определении для каждого
признака, присутствующего в записи, его номера яруса дерева покрытий и
построения дерева с учетом этой информации. Каждому признаку выделяется
соответствующий ярус дерева покрытий.
Любая строка, получаемая конкатенацией вершин при прохождении по любой ветви
дерева от нулевой вершины до данной вершины, потенциально является покрытием.
Его поддержка равна поддержке последней вершины в данной строке.
Метод генерации агрегированных ассоциативных правил на основании объединения
ветвей дерева покрытий состоит в следующем. Для нахождения агрегированных
ассоциативных правил, содержащих значения признака
- Киев+380960830922