Содержание


Практический интеллектуальный анализ расплывчатых и неопределенных данных

Представляем метод интеллектуального анализа на основе нечетких ассоциативных правил

Comments

Базы данных были разработаны для хранения данных, но еще более важной является возможность обращения к данным после их сохранения. Системы управления базами данных, построенные, например, на реляционных моделях (использующие язык структурированных запросов SQL), документ-ориентированных моделях (такие как MongoDB и Apache CouchDB) и графовых моделях (такие как хранилища триплетов RDF), обладают способностью точно сохранять данные, а также запрашивать данные, хранящиеся в них.

Запрос данных в строгой форме дает возможность получить только вполне определенную и конкретную информацию. Более высоким уровнем, чем простой запрос, является статистический анализ, основанный на определенных подсчетах (процентных отношениях и пропорциях). С помощью статистики вы можете предсказывать возможные варианты будущего, но для этого используются, как правило, закрытые данные, которые хранятся в вашей базе данных.

Существует целый ряд методов интеллектуального анализа данных, многие из которых специально предназначены для статистического анализа и попыток извлечь возможную новую информацию из существующих данных. Сегодня растущее число методологий интеллектуального анализа данных способно также обрабатывать неопределенности и расплывчатости в существующих данных, и эти методологии предполагают и учитывают неоднозначные и расплывчатые ответы в выходных результатах аналитических запросов.

Какого рода бывают неопределенности и расплывчатости и где они присутствуют?

Неопределенности и расплывчатости постоянно присутствуют в повседневной жизни человека. Например, вы наверняка часто слышите фразу: «Сегодня ожидается дождь». Это и есть неопределенность, потому что дождя сегодня вообще может не быть — ведь прогнозирование погоды пока еще не стало абсолютно надежным и безошибочным. Ваш друг или подруга могут сказать, что он (или она) придет к вам «около 6 часов вечера». Слово «около» говорит о предполагаемой неопределенности, поскольку время указано неточно.

На самом деле, если вы внимательно вслушаетесь в большинство разговоров, которые вы слышите или ведете ежедневно, вы заметите неопределенности и расплывчатости почти в каждом предложении. Вполне вероятно, что и эта статья, которую вы сейчас читаете, полна неоднозначностей, неясностей и предположений! Важно отметить, что данные могут быть «нечеткими» ("fuzzy") либо непреднамеренно, либо умышленно. Например, если опрос общественного мнения проводился на случайной выборке населения, можно непреднамеренно пропустить важные мнения тех, кто не вошел в эту выборку, но, когда вы слышите прогноз погоды по телевидению или радио, ведущий использует нечеткую терминологию вроде «легкий ветерок» или «сильный дождь» вполне намеренно. Что значит «легкий ветерок» или «сильный дождь»? Насколько легким будет ветер и сильным дождь? Или, если вернуться к примеру об опросе, в какой степени возможные пропущенные мнения неохваченных потенциальных респондентов могли бы повлиять на ваши выводы?

Традиционная теория вероятностей предоставляет статистические методы, которые помогают «разгадать», может ли произойти то или иное событие, и позволяют успешно классифицировать новую информацию на основе старой информации. Такая форма вероятности, более известная как субъективная вероятность (subjective probability), делает попытку дать ответ на вопрос: «Какова вероятность Х?» Альтернативный подход предлагает теория нечетких множеств, которая пытается ответить на вопрос: «В какой мере я считаю Х элементом этого множества?» и, поэтому, может рассматриваться скорее в качестве «меры возможного», а не вероятностной меры. В ряде исследований была проведена работа по преобразованию нечетких множеств в вероятностные множества и наоборот.

Основы теории нечетких множеств

Классическая теория множеств предоставляет операции для комбинирования и манипулирования наборами данных, в том числе операции объединения (возвращает комбинацию данных из двух или более наборов), пересечения (находит общие данные в двух или нескольких наборах), разности множеств (удаляет данные, найденные в одном наборе, из другого набора) и отрицания (указывает, что вы хотите найти всё, о чем мы знаем, но чего нет в этом наборе). Существуют разнообразные общие законы (подобно физическим законам, а не юридическим правилам или нормам) для упрощения комбинаций операций теории множеств. Эти законы работают всегда, и математически «высечены в камне» благодаря самой природе чисел, множеств и упорядоченности. На классической теории множеств основана природа всех обычно применяемых баз данных, где запись (или объект данных) может быть представлена в качестве элемента одного или нескольких наборов данных (или множеств). Запросы к базе данных устанавливают взаимосвязи между этими наборами и фильтруют эти взаимосвязи для получения результата. С точки зрения классической теории множеств элемент данных либо «присутствует» в наборе, либо «отсутствует» в нем — без каких-либо двусмысленностей, вариантов интерпретации и полутонов.

Теория нечетких множеств, напротив, допускает для элемента данных возможность «иногда» присутствовать (или «иногда» отсутствовать) в наборе до определенной степени. Вы, например, можете считать, что у Ника каштановые волосы, с достоверностью, выраженной цифровым значением 0,9, а у Джоанн — с достоверностью 0,5. В классической теории множеств вам придется делать сложный выбор: следует ли отнести и Ника, и Джоанн к «каштановому» набору, что особенно проблематично в случае с Джоанн, поскольку ваше знание о том, какой на самом деле у нее цвет волос, сравнительно менее точное. В теории нечетких множеств значение 0,0 означает, что элемент данных не принадлежит множеству (набору данных), значение 1,0 означает полную принадлежность множеству. Таким образом, классическую теорию множеств в этом контексте можно рассматривать как ограниченную версию теории нечетких множеств, и в литературе по данной тематике нередко встречается определение классической теории множеств как «теории четких множеств» (в отличие от нечетких). Теория нечетких множеств предлагает ту же группу операций, что и классическая теория множеств, в том числе операции объединения, пересечения, разности множеств и отрицания, однако между этими теориями существуют незначительные отличия в общих законах — просто потому, что некоторые из законов классической теории множеств работают только тогда, когда вы ограничиваете принадлежность множеству двумя значениями. Читатели, знакомые с реляционными базами данных, могут рассматривать операции объединения и пересечения как частные случаи операции слияния или соединения.

В теории нечетких множеств можно найти разные виды объединения, пересечения, разности множеств и отрицания, но приведенные ниже являются наиболее распространенными. Они также предпочтительны при работе с четкими множествами:

  • Нечеткое объединение (fuzzy union — логическое сложение двух нечетких множеств):
    A union B = { max(mu(a), mu(b)) for a in A and b in B and if a == b }

    Это означает, что результатом нечеткого объединения является максимальное значение принадлежности множеству каждого уникального элемента в обоих наборах. Таким образом, если элемент «Джоанн» появился в обоих списках, то более высокое значение принадлежности множеству среди двух наборов становится значением принадлежности множеству для операции объединения.

  • Нечеткое пересечение (fuzzy intersection — логическое произведение двух нечетких множеств):
    A intersection B = { min(mu(a), mu(b) for a in A and b in B and if a == b }

    Это означает, что результатом нечеткого пересечения является минимальное значение принадлежности множеству каждого уникального элемента в обоих наборах. Если элемент «Ник» имеет значение принадлежности множеству 0,9 в одном наборе и 0,1 — в другом наборе, то значение 0,1 выбирается в качестве значения принадлежности множеству для операции пересечения. Если «Ник» имеет значение принадлежности множеству 0,0 (т.е. он не появился в одном наборе), то он будет исключен из операции пересечения.

  • Нечеткое отрицание (fuzzy negation — вид логической инверсии в теории нечетких множеств):
    -A = { 1 – mu(a) for a in A }

    Это означает, что вы обрабатываете весь набор и вычитаете каждое значение принадлежности множеству из значения 1,0. Например, элемент «Кит» (Keith; мужское имя) может быть в наборе «людей с седыми волосами» со значением принадлежности 0,8. Если вы хотите узнать, с каким значением принадлежности множеству он находится в наборе «людей, у которых нет седых волос», то вы выполняете операцию 1,0 — 0,8 и получаете, естественно, значение 0,2.

  • Нечеткая разность множеств (fuzzy set difference):
    A – B = { max(0, mu(a) – mu(b)) for a in A and b in B and if a == b }

    Это означает, что вы вычитаете значения принадлежности множеству каждого элемента в одном наборе данных из значений принадлежности соответствующего элемента в другом наборе данных. Эта операция имеет более точное определение — «ограниченная разность» (bounded difference), поскольку, если результат вычитания является отрицательным числом, вы присваиваете ему значение 0 (или, иными словами, ограничиваете его нулевым значением). Таким образом, если элемент «Ник» находится в наборе людей с каштановыми волосами со значением принадлежности 0,9, а также в наборе людей со светлыми волосами со значением принадлежности 0,2, то в результате операции нечеткой разности множеств («Люди с каштановыми волосами» — «Люди со светлыми волосами») Нику будет присвоено значение принадлежности 0,7 (0,9 — 0,2). Эту операцию можно также использовать для определения, того, действительно ли у Ника каштановые волосы, путем исключения других потенциальных вариантов.

Разработка решений для интеллектуального анализа нечетких данных

С помощью операций над нечеткими множествами можно создавать нечеткие алгоритмы, нечеткие базы данных и нечеткие базы знаний. Решения для интеллектуального анализа нечетких данных начали появляться на рубеже 1990-2000 годов, когда вычислительные машины стали достаточно мощными для практической реализации методов углубленного анализа больших наборов данных и машинного обучения и когда стала актуальной обработка неопределенностей и расплывчатостей. Настоящая статья охватывает, главным образом, интеллектуальный анализ нечетких ассоциативных правил— как один из видов интеллектуального анализа нечетких данных, — но я коснусь и других методов анализа нечетких данных.

Классический интеллектуальный анализ ассоциативных правил

В начале 1990-х годов группа исследователей из IBM, в которую входили Ракеш Агравал (Rakesh Agrawal), Томаш Имелински (Tomasz Imielinski) и Арун Свами (Arun Swami), разработали концепцию автоматического расчета «достоверности» связей от одного элемента данных к другому элементу в транзакционной базе данных. Рассматриваемой исследователями транзакционной базой данных была база данных супермаркета, которая содержала транзакции (торговые операции; фактически — это набор товаров, купленных покупателем за один визит), совершаемые покупателями. Алгоритм, разработанный Агравалом и его командой, который назвали APRIORI, сопоставлял элементы данных, такие, например, как «молоко», с другими элементами, такими, например, как «хлеб», и рассчитывал достоверность в соответствии с тем, как часто молоко и хлеб были замечены вместе в одних и тех же транзакциях. Эту строку упорядоченных таким образом элементов стали называть «ассоциативными правилами» (association rules), число транзакций с одним или более подобным элементом назвали «поддержкой» (support), а результат вычисления —«достоверностью» (confidence), которая рассчитывалась путем деления поддержки для всех элементов в правиле на поддержку для начальных (initial) элементов. Метод транзакционных ассоциативных правил активно развивался все эти годы и становился все более эффективным. Исследователи разработали версии алгоритма специально для компьютеров с параллельной обработкой данных. Таким образом, для расчета достоверности ассоциативного правила транзакций нужно выполнить следующее:

transaction_association_confidence(A to B) = support(A union B)/support(A)

В нашем примере это означает: если элемент А — это молоко, а элемент В — это хлеб, то достоверность утверждения, что если в транзакции присутствует молоко, то присутствует и хлеб, равна количеству (или процентной доле) транзакций с молоком или хлебом (либо и с молоком, и с хлебом), поделенному на количество (или процентную долю) транзакций только с молоком.

Несколько иная форма ассоциативного правила появилась не на основе транзакций, а на основе свойств объектов. Так, вместо того чтобы искать достоверность «если есть молоко, то есть и хлеб», вы можете вычислять достоверность «каштановых волос в сочетании с карими глазами», где элементы (в данном случае люди) будут появляться и в исходном наборе, и в целевом наборе. В этом случае, в силу специфики объектов, объединение (как сумма двух множеств) в расчете достоверности должно быть реализовано операцией пересечения (логического произведения двух множеств):

object_association_confidence(A to B) = support(A intersection B)/support(A)

Поясним это на примере: если A — это каштановые волосы, а B — карие глаза, то вы делите количество людей, у которых каштановые волосы и карие глаза, на количество всех людей с каштановыми волосами (независимо от цвета их глаз).

Как использовать нечеткие ассоциативные правила

Один из самых простых способов сделать алгоритм интеллектуального анализа ассоциативных правил более «нечетким» — выполнить «нарезку» (сделать т.н. альфа–сечения —alpha-cuts) в заданных точках в диапазоне между 0,0 и 1,0; где элементы со значением функции принадлежности выше уровня отсечения считаются «четкими» (что соответствует полной принадлежности), а элементы ниже уровня отсечения считаются элементами без принадлежности. Результатом являются уровни достоверности для правил при различных значениях уровня отсечения. Это один из «самых нечетких» методов, с результатом в виде двумерного графа, а не единственного значения достоверности. Таким образом, ваш расчет нечетких ассоциативных связей будет выглядеть следующим образом (и такой подход пригоден как для транзакционной, так и для объектно-ориентированной формы):

fully_fuzzy_association_confidence(A to B) = {classical_association_confidence(alphacut(A, alpha) 
    to alphacut(B, alpha)) for alpha in predetermined_alphas}

Несмотря на то, что это, возможно, самый «нечеткий» и одновременно легко осуществимый вариант, он может требовать значительных вычислительных ресурсов. Кроме того, он требует, чтобы значения принадлежности (или функции принадлежности) были назначены каждому элементу (или каждому классу элементов) в базе данных. В идеале эти значения принадлежности должны быть рассчитаны по некоторой формуле: например, «сильный дождь» может быть функцией нечеткой принадлежности, основанной на количестве миллиметров выпавших осадков, и он может быть связан (может ассоциироваться) с «сильным ветром», который, в свою очередь, может быть функцией нечеткой принадлежности, основанной на скорости в километрах в час. Ассоциация может быть построена с использованием конкретных фактов, взятых из определенного дня. Например, если вы анализируете метеоданные в определенной стране в определенный день за последние пять лет, вы можете придти к выводу, что существует тесная связь между «сильным дождем» и «сильным ветром», однако, когда вы слышите прогноз метеоролога, он в своих фразах может быть намеренно немного более расплывчатым (т.е. иметь более высокое альфа–сечение), говоря, что, если в этот день пойдет «сильный дождь», то, возможно, он будет сопровождаться «сильным ветром».

Методы, которые, похоже, преобладают в литературе об интеллектуальном анализе нечетких ассоциативных правил, предусматривают суммирование значений принадлежности и деление результата на количество транзакций (или объектов) в базе данных. Таким образом, для иллюстрации двух упомянутых форм:

fuzzy_sum_transaction_association_confidence(A to B) = sum({mu(t) 
    for t in (A union B)})/number_of_transactions

_________________________________________


fuzzy_sum_object_association_confidence(A to B) = sum({mu(o) 
    for o in (A intersection B)})/number_of_objects

Такая форма суммирования упрощает результирующую достоверность, предлагая единственное значение (а не двумерный граф), однако при этом эффективно восстанавливает «четкость и однозначность» данных. То есть у вас не остается интерпретируемости, возможности того или иного толкования, которые обеспечивают нечеткость и расплывчатость. Кроме того, эта форма требует предварительно заданных значений принадлежности или функций принадлежности.

В 1998 году группа исследователей из Китайского университета Гонконга (Chinese University of Hong Kong), в том числе Ада Вай-Чи (Ada Wai-chee) и Мень Хонь Вон (Man Hon Wong), разработали методику для поиска нечетких множеств в заданной базе данных. Научный доклад под названием "Finding Fuzzy Sets for the Mining of Fuzzy Association Rules for Numerical Attributes" («Поиск нечетких множеств с целью интеллектуального анализа нечетких ассоциативных правил для численных атрибутов»), представлявший их работу, был написан специально для международной конференции Intelligent Data Engineering and Automated Learning Conference (Интеллектуальная инженерия данных и автоматизированное обучение) в 1998 году. Эта работа представляет особый интерес, поскольку устраняет требование о необходимости заранее знать значения или функции нечеткой принадлежности. Недостаток методики состоит в том, что она использует довольно сложный алгоритм кластеризации, известный как CLARANS, однако эта тема выходит за рамки настоящей статьи.

Другие формы интеллектуального анализа нечетких данных

Интеллектуальный анализ ассоциативных правил — это не единственная форма интеллектуального анализа данных. Так, группа исследователей из IBM во главе с Ракешем (Rakesh) разработала метод интеллектуального анализа последовательных шаблонов (sequence pattern mining) как расширение метода интеллектуального анализа ассоциативных шаблонов (association pattern mining). В отличие от направленных ассоциаций, формируемых независимо от времени, последовательные шаблоны имеют временную зависимость: попросту говоря, они должны быть упорядочены во времени. Интеллектуальный анализ последовательных шаблонов, возможно, стал еще более полезным для транзакционных баз данных, чем ассоциативные правила, и может применяться к любым датированным записям базы данных (наборам данных с временными метками — temporal data sets). Интеллектуальный анализ последовательных шаблонов также может быть сделан «нечетким» ("fuzzified"). Еще одной формой интеллектуального анализа данных является классификация (classification), которая часто использует методы кластеризации, пытается обнаружить сходство статистически и классифицирует полученные данные. Существуют специализированные методы нечеткой классификации, которые применяются в таких разных прикладных областях, как геология и медицина.

Заключение

В статье приводится краткий обзор того, как можно учитывать неопределенности и расплывчатости при интеллектуальном анализе данных. Рассматриваются вопросы разработки и практического применения теории нечетких множеств в качестве решения задач для учета неопределенностей и расплывчатостей. В статье также исследуются ассоциативные правила, которые изначально были разработаны в IBM и затем были дополнены и усовершенствованы сообществом разработчиков и пользователей средств интеллектуального анализа данных. Автор рассмотрел различные способы обработки нечетких данных в ассоциативных правилах и пришел к выводу, что «размывание» ("fuzzification" — подготовка задачи к решению методами нечеткой логики) и результаты интеллектуального анализа нечетких ассоциативных правил в значительной степени зависят от области применения и пользователя. И, наконец, статья содержит краткое описание других форм интеллектуального анализа нечетких данных, которые успешно применяются в различных отраслях.

Алгоритмы, используемые в интеллектуальном анализе данных, становятся все более необходимыми для тех, кто хранит данные в базах данных. Это становится очевидно, если понаблюдать за компаниями (включая IBM), продающими продукты баз данных, которые заявляют, что их продукты могут масштабироваться и поддерживают параллельную обработку, а также если послушать исследователей и разработчиков, обсуждающих плюсы и минусы больших данных. Я уверен, что теория нечетких множеств наряду с теорией вероятностей будет играть решающую роль в будущем развитии методов интеллектуального анализа данных, поскольку она обладает не только потенциалом для учета неопределенностей и расплывчатостей, но и возможностью сделать компьютерные интерфейсы более естественными для человека путем реализации «вычислений с помощью слов» ("computing with words"), а не с помощью программного кода.

У IBM есть два продукта для интеллектуального анализа данных — IBM DB2® Intelligent Miner® и SPSS® Modeler. IBM также участвовала в создании основ архитектуры управления неструктурированной информацией (Unstructured Information Management Architecture, UIMA), которая является архитектурой для интеллектуального анализа данных. Другие открытые и коммерческие программные продукты также пригодны для интеллектуального анализа данных, но это системы в первую очередь статистические, и я бы советовал компаниям и сообществу ПО с открытым исходным кодом внедрять и применять нечеткие методы. В настоящее время, однако, мы как разработчики можем реализовать нечеткие методы только поверх этих систем. Я приглашаю вас прокомментировать эту статью и поделиться своими успехами и любыми проблемами, которые могут возникнуть в процессе реализации алгоритмов интеллектуального анализа нечетких данных.


Ресурсы для скачивания


Похожие темы

  • Оригинал статьи: Practical data mining of vague and uncertain data («Анализируйте свой бизнес розничной торговли с помощью IBM DB2 Intelligent Miner for Data» (документ IBM Redbooks®): руководство по использованию DB2 Intelligent Miner в сфере розничной торговли.
  • Mining Your Own Business in Retail Using DB2 Intelligent Miner for Data («Анализируйте свой бизнес розничной торговли с помощью IBM DB2 Intelligent Miner for Data» (документ IBM Redbooks®): руководство по использованию DB2 Intelligent Miner в сфере розничной торговли.
  • Statistical analysis of medical data with IBM SPSS Modeler («Статистический анализ медицинских данных с помощью IBM SPSS Modeler»), авторы Алекс Торквато Соуза Карнейро (Alex Torquato Souza Carneiro) и Марчело Франчески де Бьянки (Marcelo Franceschi de Bianchi), портал developerWorks, октябрь 2012 года: руководство по использованию методов интеллектуального анализа данных и машинного самообучения в SPSS Modeler.
  • XML data mining, Part 2: Mining XML association rules («Интеллектуальный анализ XML-данных: Часть 2. Поиск ассоциативных правил в XML-данных»), автор Лаура Ирина Русу, портал developerWorks, декабрь 2011 года: пошаговое руководство по поиску ассоциативных правил в XML-файлах.
  • Fuzzy Logic (статья «Нечеткая логика») в Стэнфордской философской энциклопедии (Stanford Encyclopedia of Philosophy): философское описание нечеткой логики и теории нечетких множеств.
  • Видео Fuzzy Logic («Нечеткая логика»): практическое руководство по созданию приложений, использующих методы нечеткой логики и нечетких множеств, в частности, для анализа данных.
  • Finding Fuzzy Sets for the Mining of Fuzzy Association Rules for Numerical Attributes («Поиск нечетких множеств с целью интеллектуального анализа нечетких ассоциативных правил для численных атрибутов»), авторы Ада Вай-Чи (Ada Wai-chee), Мен Хон Вонг (Man Hon Wong) и др.: о применении методов кластеризации для автоматического поиска функций нечеткой принадлежности с целью использования в интеллектуальном анализе ассоциативных правил.
  • Fast Algorithms for Mining Association Rules («Быстрые алгоритмы для интеллектуального анализа ассоциативных правил»), авторы Ракеш Агравал (Rakesh Agrawal) и Рамакришнан Срикант (Ramakrishnan Srikant), оба из IBM: эта статья, опубликованная в 1994 году, описывает интеллектуальный анализ ассоциативных правил и алгоритм APRIORI.
  • Efficient and Effective Clustering Methods for Spatial Data Mining («Эффективные и действенные методы кластеризации для интеллектуального анализа пространственных данных»), авторы Рэймонд ЭнДжи (Raymond Ng) и Цзявэй Хань (Jiawei Han): в этой статье, опубликованной в 1994 году, рассматриваются различные методы кластеризации, но, самое главное, в ней представлен алгоритм CLARANS.
  • Веб-сайт MongoDB: великолепный ресурс для изучения хранилищ документов MongoDB и NoSQL в целом.
  • Веб-сайт CouchDB организации Apache Foundation: также содержит полезную информацию о системах NoSQL.
  • Узнайте больше о хранилищах RDF-данных (триплетов) (RDF Triple stores) на Wiki-ресурсе W3C: статья LargeTripleStores о крупных хранилищах триплетов.
  • Узнайте больше о продуктах семейства SPSS.
  • Узнайте больше об DB2 Intelligent Miner.

Комментарии

Войдите или зарегистрируйтесь для того чтобы оставлять комментарии или подписаться на них.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Information Management
ArticleID=979093
ArticleTitle=Практический интеллектуальный анализ расплывчатых и неопределенных данных
publish-date=07292014