Использование алгоритмов ассоциации в интеллектуальных системах обработки телеметрической информации

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Использование алгоритмов ассоциации в интеллектуальных системах обработки телеметрической информации

Н.А. Жукова

В докладе рассматриваются вопросы применения алгоритмов ассоциации в задачах обработки телеметрической информации. Делается вывод о целесообразности использования алгоритмов ассоциации для анализа телеметрической информации. Предлагается модифицированный вариант алгоритмов Apriori и PredictiveApriori. Описывается созданная система и результаты ее испытаний на реальных задачах.

Введение

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

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

В настоящее время большинство программных продуктов, таких как SAS Enterprise Miner, PolyAnalyst, WEKA, в основу которых положены идеи Data Mining, ориентировано на использование в сфере бизнеса, однако, средства интеллектуального анализа данных находят применение во многих других предметных областях, таких как медицина, биология, физические исследования, телекоммуникационные системы.

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

Особенности задачи анализа ТМИ

телеметрический информация алгоритм ассоциация

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

Основные этапы анализа ТМИ с использованием технологии Data Mining представлен на рис. 1. Процесс приобретения знаний основан на построении продукционных правил, описывающих особенности ТМИ сигнала. На основе продукционных правил строятся классификаторы. Примерами классов выделяемых событий могут являться временные участки соответствующие ударным вибрациям, вибрациям на переходных режимах, вибрациям на установившихся стационарных, квазистационарных режимах.

Рис.1. Основные этапы анализа ТМИ

Процесс приобретения знаний состоит из нескольких этапов:

предварительная обработка сигнала и получение векторного описания сигнала с использованием спектрально-временного анализа Фурье и разложения сигнала по алгоритму вейвлет-пакет;

кластер-анализ на основе полученных векторных описаний сигнала решает задачу автоматической сегментации ТМ сигнала с целью выделения стандартных и нерегламентированных событий. Выделенные участки используются в качестве эталонов;

получение описания знаний в виде продукционных правил с помощью алгоритмов «Деревья решений» и построения ассоциативных правил;

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

Одной из особенностей задач обработки БМП ТМИ является необходимость обработки очень больших массивов телеметрических данных. Алгоритмы ассоциации хорошо зарекомендовали себя именно для обработки больших объемов данных. В отличие от классификаторов, построенных на основе деревьев решений, классификаторы, построенные на основе алгоритмов ассоциации, являются более точными. Однако, данные классификаторы, как правило, не являются полными. Достоинством продукционных правил, построенных на основе алгоритмов ассоциации, является принципиальная (для понимания человеком) вычислительная простота, а основным недостатком является резкий (экспоненциальный) рост объема вычислений с увеличением числа параметров и фактически полное неприятие в расчет редко встречаемых параметров.

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

Использование алгоритмов ассоциации для обработки ТМИ

На сегодняшний день наиболее широко используемым и хорошо зарекомендовавшим себя алгоритмом является алгоритм Apriori [Agrawal, 1994], который используется во многих коммерческих и свободно распространяемых системах. С точки зрения анализа данных основным достоинством алгоритма Apriori является его гибкость. Эксперт имеет возможность задавать два основных параметра: минимальную поддержку и минимальную достоверность правила, что позволяет получать существенно различные группы правил.

Опыт решения практических задач обработки ТМИ показывает, что использование только алгоритма Apriori является недостаточным. На начальных этапах обработки данных в ряде случаев сложно задать значения параметров минимальной поддержки и минимальной достоверности. В этом случае удобно применять алгоритм PredictiveApriori [Scheffer, 2001], который осуществляет поиск наиболее точных правил. На вход алгоритма PredictiveApriori подается только число правил, которые следует найти.

Поскольку данные алгоритмы не предполагают наличия целевой переменной, автором для решения задачи анализа БМП ТМИ предлагается модификация данных алгоритмов [Балтрашевич, 2005]. В частности модифицирован этап генерации кандидатов и этап построения правил. На этапе генерации кандидатов рассматриваются только кандидаты, в состав которых входит целевая переменная. При построении правил строятся только правила, в левой части которых расположена целевая переменная. Алгоритмы можно описать следующим образом.

Описание модифицированного алгоритма Apriori

F1 = {часто встречающиеся 1-элементные наборы}

для (k=2; Fk-1 <> ; k++) {

Ck = Apriorigen(Fk-1) // генерация наборов кандидатов,

// в состав которых входит целевая

// переменная

для всех объектов T {

CT = subset(Ck, T) // удаление избыточных правил

для всех кандидатов c CT

c.count ++ }

Fk = { c Ck | c.count >= minsupport} // отбор кандидатов

для каждого fFk вызов RuleGen(f) //построение правил,

// в правой части

// которых

// расположена

// целевая переменная

Результат U полученных правил}

Описание модифицированного алгоритма PredictiveApriori

Пусть ф =1. (начальное значение минимальной поддержки);

For i = 1...k do Построить набор i - элементных ассоциативных правил [x y]. Определить их достоверность. Пусть - распределение достоверности правил;

Для всех c, пусть

Пусть X0= {0}. Пусть X1= {{a1},...,{ak}} - 1-элементные наборы;

For i =1...k - 1 While ( i =1 or Xi-1?0 ):

If i > 1 Then определить i-элементный набор кандидатов, в состав которых не входит целевая переменная;

Подсчитать поддержку сгенерированных наборов. Удалить из Xi наборы, поддержка которых меньше ф;

Для всех вызвать процедуру RuleGen(x), которая осуществляет поиск наилучших правил с левой частью X; в правой части располагается целевая переменная;

If best был изменен Then увеличить ф так, чтобы оно принимало минимальное значение, при котором выполняется:

If ф > размер базы данных Then выход;

If ф увеличен на последнем шаге Then удалить из Xi наборы, у которых поддержка меньше, чем ф;

Вывести best[1]... best[n], список из n наилучших правил ассоциации.

Использование данных алгоритмов требует предварительного разбиения значений признаков на интервалы, т.е. преобразования количественных признаков в качественные [Agrawal, 1996]. Существующие системы для преобразования количественных данных в качественные, как правило, используют фильтр дискретизации [Witte, 2000]. Однако использование только фильтра дискретизации является недостаточным, поскольку в этом случае не учитываются основные проблемы, возникающие при разбиении значений количественных признаков на интервалы, такие как:

“низкая поддержка” - если число интервалов, на которые производится разбиение значений признака велико (интервалы малы), то поддержка каждого отдельного интервала может оказаться ниже минимального порога и часть правил, содержащих признак, будет потеряна;

“низкая достоверность” - часть правил могут получить достаточную поддержку только если количественный признак имеет определенное значение или если интервал разбиения мал. С увеличением интервала разбиения увеличивается число теряемых правил.

Возникшую проблему можно решить, если рассматривать все возможные интервалы разбиения количественного признака. В этом случае будут найдены наименьшие возможные интервалы, которые имеют достаточную поддержку. Однако, при этом возникают следующие проблемы:

“время выполнения” - пусть кoличественный признак принимает n значений, тогда необходимо рассмотреть ~O(n2) интервалов;

“ненужные правила” - если значение количественного признака имеет достаточную поддержку, то достаточную поддержку будут иметь все интервалы, которые включают это значение, и, следовательно, увеличится число неинтересных правил.

Описанные выше проблемы встают особенно остро при анализе ТМИ, поскольку речь идет о работе с большим объемом с количественных данных.

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

Имеющийся у автора опыт решения реальных задач анализа ТМИ, показывает, что целесообразно использовать следующий набор фильтров:

ручной фильтр;

фильтр на основе расчета энтропии [Witte, 2000];

равномерное разбиение значений количественных характеристик;

разбиение на равные интервалы значений количественных характеристик.

Система анализа ТМИ на базе алгоритмов

Для описания процесса выделения основных событий, содержащихся в записях ТМИ, была разработана система приобретения знаний. В разработанной системе реализуется процесс приобретения знаний, основанный на построении продукционных правил, описывающих особенности ТМ сигнала.

Обобщенная структура разрабатываемой системы приведена на рис.2.

Данные, поступающие на вход системы, располагаются в таблицах базы данных и представляют собой ТМ сигналы.

Рис.2. Обобщенная архитектура системы

Подсистема предварительной обработки предназначена для получения векторного описания ТМ сигнала с использованием спектрально-временного анализа Фурье [Марпл.-мл и др., 1990] и разложения сигнала по алгоритму вейвлет-пакет [Воробьев и др., 1999].

Подсистема кластер-анализа решает задачу автоматической сегментации ТМ сигнала с целью выделения стандартных и нерегламентированных событий. В подсистеме кластер-анализа реализованы следующие алгоритмы:

алгоритм К-внутригрупповых средних [Ту и др., 1978];

алгоритм максимизации ожидания (ЕМ) [McLaghlan, 1997].

В подсистеме построения деревьев решений реализованы следующие алгоритмы:

алгоритм построения деревьев решений С4.5 [Quinlan, 1993];

алгоритм построения деревьев решений СART [Murthy, 1997].

В подсистеме ассоциации реализованы следующие алгоритмы:

алгоритм построения ассоциативных правил «Apriori»;

алгоритм построения ассоциативных правил «PredictiveApriori».

В результате работы алгоритмов построения деревьев решений и алгоритмов ассоциации получается описание событий в ТМ сигнале в виде правил продукции типа:

Если

(компонента AS1 лежит в интервале 1 ) и (компонента AS2 лежит в интервале 2)

и ………………… ………………………….

То класс сегмента = значение класса

(под компонентами ASi понимаются компоненты векторного описания сегментов сигнала).

Записанные в таком виде правила создают базу знаний, описывающую различные события в телеметрическом сигнале.

Описание проведенных экспериментов

С помощью разработанной системы был проведен ряд экспериментов с реальными сигналами, поступающими от различных датчиков. Сигналы подавались на вход системы после предварительной обработки (применялось преобразование Фурье; число сглаженных спектральных Фурье-коэффициентов 16). Классы событий определялись по результатам кластер-анализа: класс 1 - переходный процесс; класс 2 - ударный процесс; класс 3 - установившиеся вибрации; класс 4 - остальные участки сигнала. Исследование было проведено на десяти различных сигналах. Ошибки построенных классификаторов находятся в диапазоне 2 - 10%.

Анализ результатов применения алгоритмов ассоциации для обработки ТМИ

Анализ проведенных экспериментов показал, что основной причиной возникновения ошибок классификатора на основе ассоциативных правил является неполнота построенного классификатора, что является прямым следствием маленького объема выборки.

Возможны следующие решения возникшей проблемы:

увеличение объема обучающей выборки;

увеличение числа правил за счет добавления правил с низким значением параметра поддержки (сильные правила), однако, это может привести к тому, что полученный набор правил будет сложно анализировать и увеличится время работы классификатора.

Заключение

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

выборка имеет большой объем (порядка нескольких сотен векторов);

в состав наименьшего из классов, полученных в результате кластер анализа, входит не менее 10% векторов от общего числа векторов обучающей выборки.

Полученные результаты исследований показывают работоспособность разработанной системы и подтверждают эффективность использования алгоритмов Data Mining. Использование данных алгоритмов позволяет повысить уровень достоверности результатов обработки данных телеметрии и приводит к повышению эффективности работы специалистов по анализу ТМИ.

Список литературы

[Балтрашевич, 2005] Балтрашевич В.Э., Жукова Н.А., Тихонов. Д.В. Интеллектуальная обработка телеметрической информации на основе алгоритмов ассоциации // Научная сессия МИФИ-2005. Сборник научных трудов. - М.: МИФИ, 2005.

[Воробьев и др., 1999] Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет - преобразования. - СПб.: ВУС, 1999.

[Марпл.-мл и др., 1990] Марпл.-мл. С.Л. Цифровой спектральный анализ и его приложения: Пер. с англ. - М.: Мир, 1990.

[Ту и др., 1978] Ту Дж., Гонсалес Р. Принципы распознавания образов. - М.: Мир, 1978.

[Agrawal, 1994] Agrawal R., Srikant R. Fast algorithms for mining association rules in large databases // Proc. International Conference on Very Large Databases, Chile. 1994.

[Agrawal, 1996] Agrawal R., Srikant R. Mining quantitative association rules in large relational tables // Proc. of the ACM SIGMOD Conference on Management of Data, Canada. 1996.

[McLaghlan, 1997] McLaghlan G. and Krishnan T. The EM algorithm and extensions. - Wiley, 1997.

[Murthy, 1997] Murthy S. Automatic construction of decision trees from data: A Multi-disciplinary survey. - Kluwer Academic Publishers, 1997.

Размещено на Allbest.ru