В статье предложен метод выявления взаимосвязи между объектами на основе анализа множества ассоциативных правил. Ассоциативные правила формируются на основе обработки анкет. Для формирования ассоциативных правил используется алгоритм Apriori. Для множества ассоциативных правил строится граф взаимосвязей. Каждое ассоциативное правило определяет взвешенное ребро графа. Для графа выполняется поиск сообществ. Сообщества показывают наиболее сильно связанные факторы исходного множества.
Copyright ○ c by the paper’s authors. Copying permitted for private and academic purposes.
выявлены ассоциативные правила, связывающие характер человека и его склонность к наркомании.
Поиск ассоциативных правил осуществляется на базе данных наркологических клиник. Применение поиска
ассоциативных правил к данным переписи населения в рамках проекта SPIN представлена в статье [
Данная статья посвящена определению закономерностей в деятельности общественных организаций российских немцев на основе базы данных, полученной с помощью анкетирования. База данных анкет используется для построения ассоциативных правил и выявления закономерностей между различными аспектами деятельности общественных организаций. 1
Постановка задачи и методы решения Для использования метода построения ассоциативных правил необходимо сформировать множество возможных записей и список транзакций. В данной работе анализировалась деятельность общественных организаций российских немцев в различных регионах. Исходная информация бралась из анкет, заполнявшихся руководителями организаций. В качестве транзакции выбиралась одна анкета. Каждая анкета содержала вопросы различного формата. Первый тип вопросов предполагал два варианта ответа «Да» или «Нет». Второй тип вопросов допускал выбор одного из четырех или пяти вариантов, причем допускался дополнительный ответ «прочее», который не кодировался, так как содержал неопределенность. Также в анкете присутствовали вопросы с недетерминированным ответом, но они не учитывались при формировании транзакций, так как все ответы были различными и не могли привести к выявлению ассоциативных правил со сколько-нибудь заметной поддержкой. Каждый вариант ответа кодировался своей записью. Вопрос обозначался идентификатором из одной или двух латинских букв. Например, вопрос, обозначаемый «A», имел два варианта ответа, кодируемых «A1» и «A2». В вопросах, содержащих выбор из двух альтернатив, нельзя ограничиваться кодированием только одной из них, не смотря на возможность однозначного восстановления второй. Такое ограничение может приводить к потере ассоциативных правил.
Пусть – множество всех ответов, которые могут присутствовать в транзакции. Каждая транзакция – это набор элементов из ( ⊆ ). – множество всех транзакций. Говорят, что транзакция содержит набор элементов , если ⊆ и ⊆ . Ассоциативным правилом называется импликация ⇒ , где ⊆ , ⊆ и ∩ = ∅.
Каждое ассоциативное правило характеризуется некоторым набором параметров. Первый параметр, называемый поддержкой, показывает частоту встречаемости данного правила в имеющемся наборе транзакций. Поддержка правила ⇒ вычисляется как процент транзакций, содержащий множество ∪ : ( ⇒ ) = ( ∪ ) || · 100%, где ( ∪ ) – количество транзакций, содержащих множество ∪ .
Достоверность правила показывает, с какой вероятностью из следует . Достоверность ассоциативного правила ⇒ вычисляется как процент транзакций, содержащих как , так и , в множестве транзакций, содержащих : ( ⇒ ) = ( ⇒ ) () . Задача поиска ассоциативных правил состоит в нахождении наборов элементов, поддержка которых не ниже чем minsupport. Из найденных наборов выделяются правила с достоверностью не ниже minconfidence. 2
Ассоциативные правила
В общей сложности было обработано 107 анкет, каждая из которых рассматривалась как независимая
транзакция. После кодирования были получены транзакции с различным числом записей от 24 до 50. На
основе данных транзакций был осуществлен поиск ассоциативных правил с поддержкой не менее 60% и
достоверностью не менее 80%. Для поиска ассоциативных правил был использован алгоритм APriori [
Анализ показывает, что поиск ассоциативных правил позволяет выявить как достаточно очевидные взаимосвязи между различными аспектами деятельности общественных организаций, так и достаточно неожиданные влияния Таблица 1: Ассоциативные правила по деятельности общественных организаций российских немцев N Предпосылка Следствие 1 Более 50% посетителей Интернет используется 61,68 80,72 центра являются в работе центра российскими немцами несколько раз в день 2 Более 50% посетителей В организации исполь- 60,75 80,72 центра являются зуются языковые курсы российскими немцами для взрослых 3 Более 50% посетителей В организации знают 62,62 80,72 центра являются о том, что Германия российскими немцами осуществляет специаль
ные программы 4 Более 50% посетителей Знания немецкого языка 62,62 81,93 центра являются за последние 10 лет российскими немцами улучшились 5 Интернет используется Знания немецкого языка 62,62 80,00 в работе центра несколько за последние 10 лет раз в день улучшились 6 В организации исполь- Более 50% посетителей 63,55 82,72 зуются языковые курсы центра являются для взрослых российскими немцами 7 В организации исполь- Интернет используется 62,62 82,72 зуются языковые курсы в работе центра для взрослых несколько раз в день 8 В организации исполь- Знания немецкого языка 63,55 85,19 зуются языковые курсы за последние 10 лет для взрослых улучшились 9 Знания немецкого языка Более 50% посетителей 62,62 80,95 за последние 10 лет центра являются улучшились российскими немцами 10 Знания немецкого языка Интернет используется 62,62 80,95 за последние 10 лет в работе центра улучшились несколько раз в день 11 Знания немецкого языка В организации исполь- 64,49 82,14 за последние 10 лет зуются языковые курсы улучшились для взрослых 12 Партнерами в работе Интернет используется 62,62 83,54 являются организации в работе центра в России несколько раз в день 13 Партнерами в работе Знания немецкого языка 63,55 82,28 являются организации за последние 10 лет в России улучшились Таблица 2: Ассоциативные правила по деятельности общественных организаций российских немцев (продолжение) Предпосылка Сотрудничество с МСНК осуществляется постоянно с высокой степенью эффективности В организации знают о том, что Германия осуществляет специальные программы Для изучения немецкого языка используются детские и молодежные языковые клубы Партнерами в работе являются организации в России и Сотрудничество с МСНК осуществляется постоянно с высокой степенью эффективности Сотрудничество с МСНК осуществляется постояннос высокой степенью эффективности и Предлагаются программы целевой направленности для всех возрастов Предлагаются программы целевой направленности для всех возрастов и Интернет используется в работе центра несколько раз в день Сотрудничество с МСНК осуществляется постоянно с высокой степенью эффективности и Знания немецкого языка за последние 10 лет улучшились Следствие Интернет используется в работе центра несколько раз в день Более 50% посетителей центра являются российскими немцами Знания немецкого языка за последние 10 лет улучшились Интернет используется в работе центра несколько раз в день Интернет используется в работе центра несколько раз в день Сотрудничество с МСНК осуществляется постоянно с высокой степенью эффективности Интернет используется в работе центра несколько раз в день 63,55 88,16 64,49
80,72 50,47
90,00 51,40
90,16 51,40
96,49 51,40
90,16 52,34 90,32 Таблица 3: Обозначения для утверждений, встречающихся в ассоциативных правилах 1 Более 50% посетителей центра являются российскими немцами 2 Интернет используется в работе центра несколько раз в день 3 В организации используются языковые курсы для взрослых 4 Знания немецкого языка за последние 10 лет улучшились 5 Партнерами в работе являются организации в России 6 Сотрудничество с МСНК осуществляется постоянно с высокой
степенью эффективности 7 В организации знают о том, что Германия осуществляет
специальные программы 8 Для изучения немецкого языка используются детские
и молодежные языковые клубы факторов друг на друга. При этом правила с одним утверждением в предпосылке обладают большей поддержкой, но меньшей достоверностью. Ассоциативные правила, содержащие конъюнкцию двух утверждений в предпосылке, характеризуются меньшей поддержкой, но очень высокой достоверностью. Следует отметить, что в формировании ассоциативных правил участвует всего 9 утверждений из 173 возможных. Между остальными утверждениями ассоциативные правила с достаточно высокими поддержкой и достоверностью отсутствуют. 3
Теоретико-графовый анализ Построим граф связей на основе выявленных ассоциативных правил. В таблице 3 приведены обозначения для утверждений, встречающихся в ассоциативных правилах.
На рисунке 1 приведен граф, построенный на основе ассоциативных правил с одной предпосылкой. В качестве веса ребер использованы значения достоверности.
Рис. 1: Граф связи утверждений ассоциативными правилами
Матрица весов построенного графа приведена в Таблице 4. Вес отсутствующих дуг равен нулю.
Применим к данному графу алгоритм поиска сообществ (community) [
,=1 ∑︁ = 1.
,=1 Таблица 4: Матрица весов графа ассоциативных правил
1 2 3 4 5 6 7 8
1 0 80,72 80,72 81,93 0 0 80,72 0
2 0 0 0 80,00 0 0 0 0
3 82,72 82,72 0 85,19 0 0 0 0
4 80,95 80,95 82,14 0 0 0 0 0
5 0 83,54 0 82,28 0 0 0 0
6 0 88,16 0 0 0 0 0 0
7 80,72 0 0 0 0 0 0 0
8 0 0 0 90,00 0 0 0 0
Для выявления сообществ используется функция модульности (modularity), показывающая оптимальность
разбиения графа на подграфы:
где – «ожидаемая связность». В канонической модели [
() = ∑︁ − ∑︁ , =1 =1 = .
() = ∑︁ − ∑︁ ,
=1 =1 = ∑︁ , = =1,̸= ∑︁ . =1,̸= где
Для поиска сообществ на графах используется алгоритм образования стяжек. Выделим в графе подграф ′ и заменим все его вершины одной вершиной, при этом вершины подграфа ∖′ остаются неизменными. Образованная вершина связана дугами с теми вершинами графа ∖′, с которыми были связаны вершины, вошедшие в стяжку. Вес вершины, вошедшей в стяжку равен сумме весов вершин и дуг, вошедших в стяжку.
Под сообществом будем понимать подграф исходного графа, который при образовании из него стяжки максимизирует функцию модульность графа (). Нашей задачей является выявление сообществ на графе ассоциативных правил. В силу того, что исходный граф имеет малое количество вершин, задача может быть решена полным перебором.
Функция модульности исходного графа равна = − 0, 1497. Объединение вершин 1, 3, 4 в одно сообщество приводит к значению функции модульности 1,3,4 = − 0, 0361, то есть такое объединение является выгодным и показывает тесную связь этих вершин. Объединение в одно сообщество вершин 1, 3, 4 и 2 приводит к значению модульности 1,2,3,4 = − 0, 0233. Остальные варианты объединения не повышают функцию модульности, то есть не являются выгодными.
Из этого анализа можно сделать вывод, о тесной связи таких аспектов деятельности общественных организаций российских немцев: «Более 50% посетителей центра являются российскими немцами», «Интернет используется в работе центра несколько раз в день», «В организации используются языковые курсы для взрослых», «Знания немецкого языка за последние 10 лет улучшились». Эти четыре направления деятельности наиболее тесно взаимосвязаны между собой и их надо рассматривать в совокупности. 4
Выводы Предложенный в данной статье подход, основанный на поиске ассоциативных правил и дальнейшем представлении связей между вопросами анкеты в виде ориентированного графа, позволяет выявить закономерности, проявляющиеся в деятельности общественных организаций. Анализ графа взаимосвязей с помощью поиска сообществ вершин дает возможность определять наиболее тесно взаимосвязанные аспекты деятельности общественных организаций. Список литературы [1] R. Agrawal, T. Imielinski, A. Swami. Mining Association Rules between Sets of Items in Large Databases. In Proc.
of the 1993 ACM SIGMOD International Conference on Management of Data , Washington DC, USA, 207–216, 1993.