Нейробум: поэзия и проза нейронных сетей

Вид материала

Документы

Содержание Определение числа классов Простой подбор Методы отжига

Подобный материал:

• Ю. Н. Шунин Лекции по теории и приложениям искусственных нейронных сетей,Рига,2007, 190.96kb.
• Я. А. Трофимов международный университет природы, общества и человека «Дубна», Дубна, 71.95kb.
• Курсовая работа по дисциплине " Основы систем искусственного интеллекта" Тема: Опыт, 903.59kb.
• Нейрокомпьютерная техника: Теория и практика, 2147.23kb.
• Заочный Государственный Университет Внастоящее время все большее применение в разработке, 64.47kb.
• Особенности применения нейронных сетей в курсе «Интеллектуальные информационные системы», 82.99kb.
• Применение аппарата нейронных сетей системы matlab для аппроксимации степенных математических, 50.69kb.
• Автоматизированная система рубрикации лекционного материала с использованием нейронных, 114.4kb.
• Ульяновский Государственный Технический Университет Кафедра вычислительной техники, 216.41kb.
• Isbn 5-7262-0634 нейроинформатика 2006, 96.9kb.

^

Определение числа классов

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

Для иллюстрации будем пользоваться пространственной моделью в двумерном пространстве. На рис, 10 приведено множество точек, которые будут разбиваться на классы.
^

Простой подбор

Идея метода состоит в том, что бы начав с малого числа классов постепенно увеличивать его до тех пор, пока не будет получена «хорошая» классификация. Понятие «хорошая» классификация может быть формализовано по разному. При простом подборе классов как правило оперируют таким понятием, как часто воспроизводящийся класс. Проводится достаточно большая серия классификаций с различным начальным выбором классов. Определяются классы, которые возникают в различных классификациях. Считаются частоты появления таких классов. Критерием получения «истинного» числа классов может служить снижение числа часто повторяющихся классов. То есть при числе классов k число часто повторяющихся классов заметно меньше чем при числе классов k-1 и k+1. Начинать следует с двух классов.

Рис. 10. Множества точек для классификации

Рис. 11. Разбиение множества на два (а) и три (б) класса

Рассмотрим два примера. На рис. 10 приведены множества точек, которые будут разбиваться на классы. При каждом числе классов проводится 100 разбиений на классы. В качестве начальных значений ядер выбираются случайные точки.

Сначала рассмотрим множество точек, приведенное на рис. 10а. При классификациях на два класса во всех 100 случаях получаем классификацию, приведенную на рис. 11. Таким образом, получено устойчивое (абсолютно устойчивое) разбиение множества точек на два класса.

В принципе можно на этом остановиться. Однако возможно, что мы имеем дело с иерархической классификацией, то есть каждый (или один) из полученных на данном этапе классов может в дальнейшем разбиться на несколько классов. Для проверки этой гипотезы проведем классификацию на три  класса. Во всех 100 случаях получаем одно и то же разбиение, приведенное на рис. 11б. Гипотеза об иерархической классификации получила подтверждение. Предпринимаем попытку дальнейшей детализации - строим разбиение на четыре класса. При этом возникают три различных разбиения, приведенных на рис. 12. При этом разбиение, приведенное на рис. 12в возникает всего два раза из 100. Разбиение, приведенное на рис. 12а - 51 раз, на рис. 12б - 47 раз. Если отбросить редкие классы, то получим набор из семи классов. Один из них воспроизводится 98 раз (красное множество на рис. 12а). Остальные шесть классов образуют две тройки. Каждая тройка состоит из двух <маленьких> классов и <большого> класса, являющегося их объединением. Из этого анализа напрашивается вывод о том, что <реальное> число классов равно пяти. Проверяем это предположение.

Рис. 12. Три варианта классификации на четыре класса

Результаты классификации на пять классов приведены на рис. 13. Выделенные на предыдущем этапе пять «маленьких» классов были воспроизведены 84, 67, 64, 68 и 69 раз. Два «больших» класса, выделенных на предыдущем этапе, были воспроизведены 24 и 30 раз. Остальные классы были получены не более чем 4 раза, а большинство по одному разу. Проверим классификацию на 6 классов. Малые классы были получены 75, 70, 53, 43, 44 раза. Один из больших классов – 16 раз. Из остальных классов один был воспроизведен 24 раза, второй – 19 раз. Все другие классы появлялись не более 10 раз. Всего получено 149 классов.

Рис. 13. Различные варианты классификации на пять классов

Таким образом, получена трехуровневая иерархическая классификация: Два класса первого уровня приведены на рис. 11а. Три класса второго уровня – на рис. 11б. Пять классов третьего уровня – на рис. 13а.

Рис. 14. Классификации на два класса

Рис. 15. Типы классификаций на три класса

Рис. 16. Типичные классификации на четыре класса

Проведем туже процедуру для множества точек, приведенного на рис. 10б. При классификации на два класса получим четыре типичных варианта классификаций, приведенных на рис. 14. Всего получено 14 классов. Два класса были получены по 69 раз, два по 18 раз. Остальные не более 6 раз.

Проведем классификацию на три класса. Получим всего два типа классификаций, приведенных на рис. 15. Всего получено 12 классов. Одна тройка классов была воспроизведена 14 раз, вторая – 26 раз, третья – 27 и четвертая – 33 раза. После классификации на четыре класса получены четыре типичных классификации, приведенные на рис. 16. Всего получено 54 класса. Пять из них  получены 36, 37, 36, 36 и 57 раз. Еще 4 класса получены 14 раз, два класса – 10 раз, остальные не более 6 раз. При классификации на пять классов получено семь типичных классификаций, приведенных на рис. 17. Всего было получено 49 классов. При этом пять классов были получены 91, 82, 87, 92 и 82 раза. Еще один класс – 8 раз. Остальные классы не более 3 раз. Увеличился разрыв между «редкими» и «частыми» классами. Сократилось число часто повторяющихся классов. Для контроля проведем классификацию на 6 классов. Всего получено 117 классов. Из них пять были получены 86, 81, 57, 76 и 69 раз. Все остальные классы были получены не более 9 раз.

Таким образом, на основе классификаций на четыре, пять и шесть классов можно утверждать, что «реально» существует пять классов.
^

Методы отжига

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

Альтернативой методу перебора служит метод отжига. Идея метода отжига состоит в том, что на основе критерия качества класса принимается решение об удалении этого класса, разбиении класса на два или о слиянии этого класса с другим. Если класс «хороший», то он остается без изменений. Существует много различных критериев качества класса. Рассмотрим некоторые из них.

1. Количественный критерий. Класс, в котором менее N точек считается пустым и полежит удалению. Порог числа точек выбирается из смысла задачи и вида меры близости.
   

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

3. Критерий сферической разделимости. Два класса считаются сферически разделимыми, если сумма радиусов двух классов меньше расстояния между ядрами этих классов. Если классы сферически неразделимы, то эти классы сливаются в один.
   

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

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

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

Метод применения этого критерия прост. Разбиваем первый класс на два и запускаем процедуру настройки сети (метод динамических ядер или обучение сети Кохонена). Если плотности обоих классов, полученных разбиением одного класса, не меньше плотности исходного класса, то считаем разбиение правильным. В противном случае восстанавливаем классы, предшествовавшие разбиению, и переходим к следующему классу. Если после очередного просмотра всех классов не удалось получить ни одного правильного разбиения, то считаем полученное число классов соответствующим «реальному». Эту процедуру следует запускать с малого числа классов, например, с двух.

Проведем процедуру определения числа классов для множества точек, приведенного на рис. 10а. Результаты приведены на рис. 18. Порядок классов 1-й класс – черный цвет, 2-й класс – синий, 3-й – зеленый, 4-й – красный, 5-й – фиолетовый, 6-й – желтый.

Рассмотрим последовательность действий, отображенную на рис. 18.

Первый рисунок – результат классификации на два класса.

Второй рисунок – первый класс разбит на два. Результат классификации на три класса. Плотности увеличились. Разбиение признано хорошим.

Рис. 18. Результат применения критерия плотности классов для определения числа классов к множеству точек, приведенному на рис. 10а.

Третий рисунок – первый класс разбит на два. Результат классификации на четыре класса. Плотности увеличились. Разбиение признано хорошим.

Четвертый рисунок – первый класс разбит на два. Результат классификации на пять классов. Плотности не увеличились. Разбиение отвергнуто. Возврат к третьему рисунку.

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

Шестой рисунок – третий класс разбит на два. Результат классификации на пять классов. Плотности увеличились. Разбиение признано хорошим.

Седьмой рисунок – первый класс разбит на два. Результат классификации на шесть классов. Плотности не увеличились. Разбиение отвергнуто. Возврат к шестому рисунку.

Восьмой рисунок – второй класс разбит на два. Результат классификации на шесть классов. Плотности не увеличились. Разбиение отвергнуто. Возврат к шестому рисунку.

Девятый рисунок – третий класс разбит на два. Результат классификации на шесть классов. Плотности не увеличились. Разбиение отвергнуто. Возврат к шестому рисунку.

Десятый рисунок – четвертый класс разбит на два. Результат классификации на шесть классов. Плотности не увеличились. Разбиение отвергнуто. Возврат к шестому рисунку.

Одинадцатый рисунок – пятый класс разбит на два. Результат классификации на шесть классов. Плотности не увеличились. Разбиение отвергнуто. Возврат к шестому рисунку.

Двенадцатый рисунок (совпадает с шестым) – окончательный результат.

Рис. 19. Результат применения критерия плотности классов для определения числа классов к множеству точек, приведенному на рис. 10б.

На рис. 19 приведен результат применения плотностного критерия определения числа классов для множества точек, приведенного на рис. 10б.