Статья

Название статьи МУРАВЬИНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ БИНАРНОГО ДЕРЕВА РЕШЕНИЙ
Автор Б.К. Лебедев, О.Б. Лебедев, Е.М. Лебедева
Рубрика Раздел II. Биоинспирированный поиск
Месяц, год 07, 2016
Индекс УДК УДК 681.325
DOI DOI 10.18522/2311-3103-2016-7-7488
Аннотация Рассматривается задача классификации, заключающаяся в нахождении моделей или функций, которые описывают и различают классы для того, чтобы иметь возможность предсказывать класс произвольного заданного объекта с известными атрибутами, но неизвестной меткой класса. Полученная модель основывается на анализе обучающей выборки, то есть множества объектов, чья метка класса известна. Для решения задач классификации используется метод, основанный на построении дерева решений. Дерево решений (ДР) – это дерево, в котором каждой внутренней вершине поставлен в соответствие некоторый атрибут, каждая ветвь, выходящая из данной вершины, соответствует одному из возможных значений атрибута, а каждому листу дерева сопоставлен конкретный класс или набор вероятностей классов. Для того чтобы классифицировать новый объект, необходимо двигаться по дереву сверху вниз, начиная с корня. При этом на каждом внутреннем узле дерева выбирается та ветвь, которая соответствует фактическому значению соответствующего атрибута. Добравшись до листа дерева, получаем тот класс, которому принадлежит объект согласно классифицирующему правилу. В работе исследуется дихотомические классификационные модели формируемые алгоритмом построения бинарного дерева решений. Каждый узел дерева при разбиении имеет только двух потомков. В работе рассматривается муравьиный алгоритм построения дерева решений, основанный на использовании эффективной оценочной функции для выбора атрибута. Общее правило для выбора атрибута можно сформулировать следующим образом: выбранный атрибут разбивает множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому. В общем случае поиск решения задачи построения ДР осуществляется коллективом муравьев Z={ zk |k=1,2,…,l}. На каждой итерации муравьиного алгоритма каждый муравей zk строит свое конкретное решение задачи построения ДР, представляемое маршрутом Mk в графе G=(X,U). В работе используется циклический (ant-cycle) метод муравьиных систем. В этом случае ферромон откладывается агентами на ребрах и вершинах после полного формирования решений. На первом этапе каждой итерации каждый k-й муравей формирует свой собственный маршрут Mk. Процесс построения маршрута Mk агентом zk пошаговый двухтактный. На каждом шаге t агент zk применяет вероятностные правила выбора следующей вершины (атрибута) и ребра (значения атрибута) для их включения в формируемый маршрут Mk(t). В памяти агента хранится информация: число выполненных шагов - t; маршрут Mk(t) , построенный за t шагов; вершина xi (атрибут Ai) выбранная и включенная в маршрут Mk(t) на шаге t; значение Afi атрибута Ai (вершины xi), выбранное на шаге t. На втором этапе все муравьи откладывают феромон. На третьем этапе осуществляется испарение феромона. Поиск решения задачи выполняется на полном ориентированном графе решений G(X,U), где X={xi | i=1,2,…,n} множество вершин соответствует множеству атрибутов А, U – множество бинарных ребер полного графа, соответствующих значениям атрибутов. Каждая пара вершин (xi, xk) связана двумя ориентированными бинарными ребрами. Одно бинарное ребро выходит из xi и входит в xk, другое наоборот выходит из xk и входит в xi. Для всех k бинарное ребро uik, выходящее из данной вершины xi, используется для моделирования двух значений атрибута Ai. Каждое бинарное ребро может находиться в одном из двух состояний, соответствующих двум значениям атрибута. Состояние ребра uik, связывающего пару вершин (xi, xk), фиксируется с помощью параметра Vik. Если Vik =1, то ребро uik находится в состоянии соответствующем первому значению A1i, атрибута Ai. Если Vik =2, то ребро uik находится в состоянии соответствующем второму значению атрибута Ai. Если Vik =0, то ребро не входит в состав маршрута. Для учета оценки состояния ребра uik (количества отложенного феромона), вводится два счетчика H1ik и H2ik. Решение задачи построения ДР представляется в виде кода – некоторого маршрута Mk, включающего вершины и «бинарные» ребра с выбранными состояниями на графе решений G(X,U). Для того чтобы получить ДР нужна процедура декодирования. ДР формируется последовательно в соответствии с построенным маршрутом M, начиная с первоначального ввода безымянной вершины. На каждом шаге t декодирования в маршруте M выбирается очередная пара – вершина xi и выходящее из нее ребро uik, для которого фиксируется значение параметра Vik. Вершине xi соответствуют атрибут Ai . Если Vik =1, то ребру uik соответствует первое значение A1i атрибута Ai. Если Vik =2, то ребру uik соответствует второе значение A2i атрибута Ai. Временная сложность этого алгоритма зависит от времени жизни колонии l (число итераций), количества вершин графа n и числа муравьев m, и определяется как O(l*n2*m)

Скачать в PDF

Ключевые слова Распознавание образов; классификация; дерево решений; муравьиная колония; граф поиска решений; маршрут.
Библиографический список 1. Han J., Kamber M. Data mining: Concepts and Techniques. – Morgan Kaufmann Publishers, 2001.
2. Ian H. Witten, Eibe Frank and Mark A. Hall Data Mining: Practical Machine Learning Tools and Techniques. – 3rd Edition. – Morgan Kaufmann, 2011.
3. Журавлев Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические методы. Программная система. Практические применения. – М.: Фазис, 2006. – 159 с.
4. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распозна-ванию. – Киев: Наукова думка, 2004. – 545 с.
5. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. – Springer, 2001. COMPACT - Comparative Package for Clustering Assessment. A free Matlab package, 2006.
6. Berkhin P. Survey of Clustering Data Mining Techniques, Accrue Software, 2002.
7. Радченко С.Г. Методология регрессионного анализа: монография. – К.: Корнийчук, 2011. – 376 c.
8. Бериков В.С., Лбов Г.С. Современные тенденции в кластерном анализе // Всероссийский конкурсный отбор обзорно-аналитических статей по приоритетному направлению «Ин-формационно-телекоммуникационные системы», 2008. – 26 с.
9. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining. – СПб.: БХВ-Петербург, 2004. – 336 c.
10. Лебедев Б.К., Лебедев В.Б. Эволюционная процедура обучения при распознавании образов // Известия ТРТУ. – 2004. – № 8 (43). – С. 83-88.
11. Konar A. Artificial intelligence and soft computing: behavioral and cognitive modeling of the human brain. – CRC Press LLC. – Boca Raton,Florida, 2000.
12. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация: теория и практика. – М.: Физматлит, 2006. – 272 с.
13. Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 27-35.
14. Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации. – М.: Физмалит, 2009. – 384 с.
15. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Разбиение на основе моделирования адап-тивного поведения биологических систем // Нейрокомпьютеры: разработка, применение. – 2010. – № 2. – С. 28-34.
16. Лебедев В.Б., Лебедев О.Б. Роевой интеллект на основе интеграции моделей адаптивного поведения муравьиной и пчелиной колоний // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 41-47.
17. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектиро-вания. – Таганрог: Изд-во ЮФУ, 2013.
18. Dorigo M. and Stützle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
19. Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Решение однородной распределительной задачи на основе моделей адаптивного поведения муравьиной колонии // Вестник РГУПС. – 2016. – № 2 (62). – С. 71-77.
20. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.

Comments are closed.