Классификация с использованием муравьиного алгоритма

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


Впервые применение алгоритма муравьиной колонии для классификации было представлено R. Parpinelli в 2002 году. Метод извлечения классификационных правил на основе муравьиного алгоритма получил название AntMiner.
Цель метода — получить простые правила вида если условие то следствие.
Предполагается, что все атрибуты категориальны. Т.е. термы представлены в виде Атрибут = Значение, например Пол = Мужской. AntMiner последовательно формирует упорядоченный список правил. Вычисление начинается с пустого множества правил и после формирования первого, все тестовые единицы данных, покрытые этим правилом, удаляются из тестового набора.
Алгоритм использует при работе направленный граф, где каждому атрибуту сопоставляется столько вершин, сколько возможных значений он принимает в тестовом наборе. Соответственно, предполагается, что перед началом работы алгоритма из тестового набора выделены множества атрибутов и их возможных значений, а также множество возможных классов.


Псевдокод алгоритма выглядит следующим образом:
testSet = Весь тестовый набор
ПОКА (|testSet| > макс_число_непокрытых_случаев)
	i = 0;
	ВЫПОЛНЯТЬ
	    i = i + 1;
	    i-й муравей последовательно строит классификационное правило;
	    Обновление феромонов на пути, представленным правилом i-го муравья;
	ПОКА (i < Число_муравьёв)
	Выбрать лучшее из всех правил;
	testSet = случаи, не покрытые лучшим правилом;
КОНЕЦ ЦИКЛА

Рассмотрим последовательно шаги алгоритма.

Инициализация значений феромона

Все ребра графа инициализируются начальным значением феромона по следующей формуле:

, где a — общее число атрибутов, bi — количество возможных значений i-го атрибута.

Построение правила

Каждое правило в алгоритме AntMiner содержит антецедент (набор термов Атрибут = Значение) и представляемый им класс. В оригинальном алгоритме исходные данные содержат только категориальные атрибуты. Предположим, что термij ≈ Ai = Vij, где Ai это i-й атрибут, а Vij это j-ое значение Ai.

Вероятность, что этот терм будет добавлен в текущее частичное правило, составляемое муравьём определяется следующей формулой:

, где ηij это значение эвристики (будет определена далее), τij значение феромона на этом ребре графа, а I множество атрибутов, еще не использованных текущим муравьём.

Эвристика

В традиционном алгоритме муравьиной колонии для решения транспортной задачи веса ребер используются совместно со значением феромона для принятия решения о выборе следующей вершины. В алгоритме AntMiner эвристикой является количество информации — термин, использующийся в теории информации. Качеством здесь измеряется с помощью энтропии, для предпочтения одних правил над другими:


где k — число классов, Tij — подмножество, содержащее все единицы данных, где атрибут Ai имеет значение Vij, |Tij| число элементов в Tij, freq(Twij) — число единиц данных, имеющих класс w, а — общее число атрибутов, bi — число возможных значений i-го атрибута.
Чем выше значение Info Tij, тем меньше шансов что муравей выберет данный терм.

Обновление значений феромонов

После того как каждый муравей завершит конструирование правила, выполняется обновление феромонов по следующей формуле:
τij(t +1) =τ ij(t)+τij(t).Q ∀термij∈текущее правило
где Q — качество правила, которое вычисляется по следующей формуле:

Здесь TruePos — количество единиц данных, которые покрываются правилом и класс которых совпадает с классом, представляемым правилом, FaslePos — количество единиц данных, которые покрываются правилом, но класс которых отличается от класса, представляемым правилом, TrueNeg — количество единиц данных, которые не покрываются правилом и класс которых не совпадает с классом, представляемым правилом, FalseNeg — количество единиц данных, которые не покрываются правилом, но класс которых совпадает с классом, представляемым правилом.
Также требуется выполнять пересчёт феромонов, имитирующий его испарение. Это можно сделать простой нормализацией значений с учётом обновленного значения феромонов.

Улучшенное обновление феромонов

Для более гибкой настройки выполнения алгоритма используется следующая формула обновления вероятностей ребер принадлежащих текущему правилу:


где р – коэффициент испарения (обычно устанавливается значение ~0,1), Q качество правила, описанное выше. Ребра, не покрытые текущим правилом просто нормализуются. Этот способ обеспечивает снижение значения феромона при низком Q и повышение при высоком (в отличие от оригинального способа).

Элитные муравьи

Также можно улучшить сходимость алгоритма, вводя некоторое число так называемых “элитных” муравьёв, которые выбирают терм, для которого P = max Pij.
В оригинальном алгоритме выбор терм выбирается по следующему алгоритму:
	ДЛЯ ВСЕХ (i,j)∈ Ji
		ЕСЛИ q ≤ ∑ Pij  ТО Выбрать термij

Где q случайная величина [0..1] с равномерным распределением. Т.е. используется плотность вероятностей термов.

Для введения элитных муравьёв алгоритм выбора терма изменяется следующим образом:
	ЕСЛИ q1 ≤ ϕ ТО
		ДЛЯ ВСЕХ (i,j)∈ Ji
			ЕСЛИ q2 ≤ ∑ Pij  ТО Выбрать термij
	ИНАЧЕ
		Выбрать терм с  P = max  Pij


Здесь q1 и q2 случайные величины [0..1] с равномерным распределением.

Некоторые наблюдения

Аналогом AntMiner является известный алгоритм Naive Bayes. Согласно моим экспериментам по их сравнению AntMiner либо незначительно превосходит Naive Bayes, либо и вовсе уступает ему на различных наборах данных. Для сравнения использовалась реализация AntMiner представленная здесь и реализация Naive Bayes из библиотеки WEKA. Кроме того, AntMiner значительно уступает и по времени вычисления. Возможно, есть ситуации или некоторые предусловия, при которых AntMiner оказывается действительно лучшим выбором.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 8

    +4
    Простите. Пытался посмотреть рейтинг статьи на телефоне и случайно заминусовал статью.
      +1
      Я за Вас поправил. :-) [/offtopic]

      По теме: статья и алгоритм очень вовремя! Как раз сейчас в рамках работы стоит задача по классификации множества пар ключ->множество_значений, заодно испытаю.
        0
        Теоретически, он будет выдавать более статистически верное решение, чем SVM, но при этом требовать больше вычислений, но все зависит от реализации алгоритма, так что дерзайте, и ссылочкой на гитхаб поделитесь — мне эта тема интересна, и я сейчас ее активно развиваю
          0
          Можно чуть поподробнее почему
          Теоретически, он будет выдавать более статистически верное решение, чем SVM
          ?
            +1
            SVM — линейный алгоритм, а значит, сильно зависит от качества обучающей выборки — для получения качественных решений нужно найти таких членов классифицируемого множества, что они покрывали как можно большую площадь классифицируемого множества.

            Если мы начнем с помощью с SVM пытаться классифицировать сильно пересекающиеся по значениям векторов множества (тексты, например) — то разделяющая плоскость неопределенности будет довольно медленно уменьшаться.

            В муравьином случае мы работаем с многомерной структурой, и формируем наши множества на на плоскости, а в пространстве, мерность которого равна количеству элементов этого множества — а следовательно, классифицирующие множества проявляются сильней, так как каждая точка этого множества содержит значительно больше информации.
              0
              Простите, всё равно не понял.

              Под линейностью алгоритма SVM вы понимаете то, что разделение множеств происходит гиперплоскостями?
              Но с kernel trick алгоритм становится совсем нелинейным.
              Вот, смотрите здесь.

              Что такое сильно пересекающиеся по значениям векторов множества?

              И совсем не понял про пространство с мерностью, равной количеству элементов множества.
              Почему так?

              P.S. из-за чего спрашиваю — я считал, что SVM один из самых оптимальных алгоритмов классификации, который строит сложные модели. Может я чего-то не знаю?
      +6
      а почему кстати нив баес? по моему этот алгоритм почти полностью соответствует построению энтропийного дерева решений? на каждом уровне дерева ищется пара <признак-значение> которая при разбиение пространства гиперплоскостью (ортогональной одной их осей координат), минимизировало бы среднюю меру энтропию двух полученных подмножеств; итог — на выходе набор правил
        0
        так что не последует разъяснения по поводу
        Аналогом AntMiner является известный алгоритм Naive Bayes

        ?

        Only users with full accounts can post comments. Log in, please.