Автоматическая кластеризация в анализе данных на основе саморганизующихся карт Кохонена
Характеристика классических методов кластеризации. Особенности самоорганизующихся карт Кохонена как одного из методов аппроксимации данных. Настройка веса на основе обучающего множества без учителя. Классический алгоритм "Победитель забирает все".
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 02.11.2018 |
| Размер файла | 21,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Липецкий государственный технический университет,
Автоматическая кластеризация в анализе данных на основе саморганизующихся карт Кохонена
И.С. Сеньковская, П.В. Сараев
Основное содержание исследования
Задача кластеризации заключается в разбиении множества объектов, представленных своими векторами , , на группы, называемые кластерами. Объекты группируются таким образом, чтобы в пределах одного кластера они были более похожими друг на друга, чем на объекты других кластеров. В каждом кластере выделяют типичные представители - ядра, , где - количество кластеров [1]. Задача кластеризацией является важнейшей задачей, встречающейся при анализе данных.
Классические методы кластеризации (метод -средних, метод ближайшего соседа) предполагают, что ядра кластеров являются известными и решают задачу притяжения к ним других векторов. Одним из методов аппроксимации данных являются самоорганизующиеся карты (СОК) Кохонена. Перед использованием СОК Кохонена необходимо обучить, т.е. настроить веса на основе обучающего множества без учителя. Классическим алгоритмом обучения является алгоритм "Победитель забирает все" [2, 3].
Алгоритм "Победитель забирает все":
1. Выбор шага обучения > 0 (0,1 - 0,7).
2. Инициализация весов сети случайными числами.
3. Настройка весов. Для каждого входного вектора:
3.1. Расчет выходов нейронов слоя Кохонена. Выбирается нейрон-победитель r с наибольшим значением на выходе.
3.2. Корректировка весов победившего нейрона.
3.3. Нормировка вектора весов нейрона-победителя:
.
Ставится задача автоматической кластеризации векторов (ядра кластеров заранее не определены), т.е. задача автоматического определения оптимального количества кластеров. В данной работе предлагаются два алгоритма разбиения данных на кластеры.
Алгоритм автоматической кластеризации №1:
1. Рассчитываются расстояния (точнее, квадраты расстояний) от каждого вектора до всех остальных (для упрощения вычислений его квадрат) с помощью евклидовой метрики:
где - -й элемент вектора . Полученные значения заносятся в таблицу.
2. Определяется максимальное расстояние по всей рассчитанной таблице:
.
3. Определяется допустимое расстояние между векторами в одном кластере как фиксированный процент от найденного в пункте 2.
4. Производится объединение векторов в кластеры: если значение расстояния в одном столбце не превосходит расстояния полученного в пункте 3, то рассматриваемый вектор относится к тому же кластеру. Рассматриваемый вектор помечается соответствующим номером кластера.
5. Переходим к следующему вектор-столбцу:
5.1. Если вектор-столбец уже относится к кластеру - выполняем пункт 5.
5.2. Если вектор-столбец не является помеченным - выполняем пункты 4-5.
6. Для векторов, имеющих одинаковые метки, рассчитываются ядра кластеров как центры тяжести.
7. Расчет уточненных значений ядер кластеров с помощью алгоритма "Победитель забирает все".
Алгоритм автоматической кластеризации №2:
1. Расчет расстояния от каждого вектора до всех остальных (для упрощения вычислений его квадрат) с помощью евклидовой метрики:
где - -й элемент вектора . Полученные значения заносятся в таблицу.
2. Определяется максимальное расстояние от каждой вершины до какой-то другой (по каждому столбцу таблицы):
.
3. Производится нормировка расстояний:
4. Осуществляется сортировка расстояний для вектора по возрастанию (по каждому столбцу таблицы).
5. Векторы объединяются в кластеры: если следующее значение расстояния в одном столбце не превосходит предыдущее в некоторое фиксированное количество раз, то рассматриваемые вектора относится к одному кластеру. Рассматриваемые вектора помечаются соответствующим номером кластера.
6. Переходим к следующему вектор-столбцу:
6.1. Если вектор-столбец уже относится к кластеру - выполняем пункт 6.
6.2. Если вектор-столбец не является помеченным - выполняем пункты 5-6.
7. Для векторов, имеющих одинаковые метки, рассчитываются ядра кластеров как центры тяжести.
8. Расчет уточненных значений ядер кластеров с помощью алгоритма "Победитель забирает все".
Было разработано программное обеспечение, рассчитывающее уточненные значения ядер кластеров. На вход программы подаются первоначальные данные. Константа обучения принимается равной 0,6 и уменьшается до 0,1 с шагом 0,1. Данные параметры могут быть изменены пользователем.
Таблица 1. Результаты первого вычислительного эксперимента
|
Алгоритм |
Количество векторов |
Время работы (с) |
Количество кластеров |
|
|
Алгоритм №1 |
20 |
0,015 |
5 |
|
|
50 |
0,032 |
5 |
||
|
100 |
0,047 |
4 |
||
|
500 |
1,047 |
4 |
||
|
Алгоритм №2 |
20 |
0,016 |
5 |
|
|
50 |
0,047 |
4 |
||
|
100 |
0,422 |
3 |
||
|
500 |
351,656 |
3 |
Для тестирования были сгенерированы 4 множества объемом 20, 50, 100 и 500 векторов. Количество кластеров зависит от фиксированной числовой характеристики, при выполнении данных тестов для первого алгоритма это величина, определяемая в пункте 3; для второго алгоритма это величина, указанная в пункте 5. Числовые характеристики подобраны так, чтобы максимальное расстояние от центра до других векторов в кластере были приблизительно равным. Результаты вычислительного эксперимента приведены в таблице 1.
Существенного отличия в количестве получаемых кластеров нет, однако, необходимо учесть тот факт, что данные в тестовых выборках распределены равномерно, не наблюдается ярко выраженных кластеров. Время обработки данных вторым алгоритмом значительно дольше при больших объемах тестового множества, так как при этом увеличивается вычислительная сложность алгоритма.
Были также рассмотрены небольшие тестовые множества с ярко выраженными кластерами. Результаты вычислительного эксперимента приведены в таблице 2.
Таблица 2. Результаты второго вычислительного эксперимента
|
Алгоритм |
Количество векторов |
Визуальное количество кластеров |
Время работы (с) |
Полученное количество кластеров |
|
|
Алгоритм №1 |
16 |
3 |
0,016 |
3 |
|
|
15 |
4 |
0,01 |
3 |
||
|
Алгоритм №2 |
16 |
3 |
0,01 |
4 |
|
|
15 |
4 |
0,01 |
4 |
Полученные результаты близки к визуальным предположениям, что говорит о хорошем подборе числовых характеристик для алгоритмов. При анализе и аппроксимации данных необходимо иметь представление, насколько должны быть близки объекты, которые объединяются в один кластер. Алгоритмы позволяют определить ядра кластеров с большой точностью и существенно сжать информацию для дальнейшей работы.
самоорганизующаяся карта кохонен кластеризация
Список литературы
1. Сараев П.В. Нейросетевые методы искусственного интеллекта. Учеб. пособие. ? Липецк: ЛГТУ, 2007. - 64 с.
2. Кохонен Т. Самоорганизующиеся карты. Пер. с англ. / Агеева В.Н. ? М.: БИНОМ. Лаборатория знаний, 2008. - 655 с.
3. Аксенов С.В., Новосельцев В.Б. Организация и использование нейронных сетей (методы и технологии). - Томск: Изд-во НТЛ, 2006. - 128 с.
Размещено на Allbest.ru
...Подобные документы
Сущность, структура, алгоритм функционирования самообучающихся карт. Начальная инициализация и обучение карты. Сущность и задачи кластеризации. Создание нейронной сети со слоем Кохонена при помощи встроенной в среды Matlab. Отличия сети Кохонена от SOM.
лабораторная работа [36,1 K], добавлен 05.10.2010Сущность и понятие кластеризации, ее цель, задачи, алгоритмы; использование искусственных нейронных сетей для кластеризации данных. Сеть Кохонена, самоорганизующиеся нейронные сети: структура, архитектура; моделирование кластеризации данных в MATLAB NNT.
дипломная работа [3,1 M], добавлен 21.03.2011Реалізація сегментації позичальників методом карт Кохонена за допомогою пакету Deductor Studio. Послідовність дій, які необхідно провести для аналізу даних у Deductor Studio. Результат сегментації на картах Кохонена та характеристика кожного сегменту.
контрольная работа [1017,1 K], добавлен 29.09.2010Основы для проведения кластеризации. Использование Data Mining как способа "обнаружения знаний в базах данных". Выбор алгоритмов кластеризации. Получение данных из хранилища базы данных дистанционного практикума. Кластеризация студентов и задач.
курсовая работа [728,4 K], добавлен 10.07.2017Анализ проблем, возникающих при применении методов и алгоритмов кластеризации. Основные алгоритмы разбиения на кластеры. Программа RapidMiner как среда для машинного обучения и анализа данных. Оценка качества кластеризации с помощью методов Data Mining.
курсовая работа [3,9 M], добавлен 22.10.2012Характеристика методов нечеткого моделирования и изучение системы кластеризации в пакетах прикладных программ. Разработка и реализация алгоритма для оптимизации базы правил нечеткого классификатора с помощью генетического алгоритма аппроксимации функции.
дипломная работа [1,9 M], добавлен 21.06.2014Проблема применения методов прогнозирования кадровой работы на основе использования компьютерных технологий. Концепция банка данных, сущность и функции. Отличие реляционных и объектно-ориентированных баз данных. Организация и технология обработки данных.
реферат [1,0 M], добавлен 23.09.2014Содержание исходного набора данных. Основные причины возникновения выбросов. Главные алгоритмы кластеризации. Обработка и очистка файла. Описание его полей. Прямоугольная вещественнозначная матрица. Метрика Минковского. Математическое определение объекта.
курсовая работа [1,4 M], добавлен 25.10.2016Особенности кластеризации социальных сетей, методы распознавания сообществ. Особенности локального прореживания графа. Разработка рекомендаций по выбору метода кластеризации для выделенных классов задач. Оптимизация процесса дальнейшей обработки данных.
курсовая работа [1,8 M], добавлен 30.06.2017Исследование производительности труда методом компонентного и кластерного анализов. Выбор значащих главных компонент. Формирование кластеров. Построение дендрограммы и диаграммы рассеивания. Правила кластеризации в пространстве исходных признаков.
лабораторная работа [998,9 K], добавлен 25.11.2014Построение векторной модели нейронной сети. Проектирование и разработка поискового механизма, реализующего поиск в полнотекстовой базе данных средствами нейронных сетей Кохонена с применением модифицированного алгоритма расширяющегося нейронного газа.
курсовая работа [949,0 K], добавлен 18.07.2014Принципы и система распознавание образов. Программное средство и пользовательский интерфейс. Теория нейронных сетей. Тривиальный алгоритм распознавания. Нейронные сети высокого порядка. Подготовка и нормализация данных. Самоорганизующиеся сети Кохонена.
курсовая работа [2,6 M], добавлен 29.04.2009Описание мониторинга выбросов случайных процессов контролируемых параметров. Основные принципы обработки статистических данных в базисе аддитивной аппроксимации стандартными распределениями. Разработка методов аппроксимирующих вкладов значений выборки.
контрольная работа [308,2 K], добавлен 19.08.2015Изучение корреляционных методов стереозрения для получения плотных карт глубины, особенности и главные ограничения их использования. Исследование характера влияния используемых размеров окна корреляции и диапазона допустимых стереодиспаратностей.
лабораторная работа [5,7 M], добавлен 20.05.2014Генерирование на основе имеющихся карт Кавказа ландшафта на базе алгоритма Diamond-Square. Визуализация получившихся карт высот с помощью библиотек glut и glaux OpenGL. Суть алгоритма Diamond-Square, этапы его реализации. Скриншоты созданной программы.
курсовая работа [1,4 M], добавлен 27.05.2013Алгоритмы и стандарты криптографических преобразований. Криптографические преобразования на основе специального программного обеспечения. Метод криптографических преобразований на основе жесткой логики. Аналоги модуля шифрования и дешифрования данных.
курсовая работа [971,6 K], добавлен 30.01.2018Бібліотека Pcap та її реалізація WinPcap під платформу Windows. Аспекти робот з бібліотекою WinPcap. Штучні нейронні мережі. Застосування бібліотеки Winpcap для захоплення мережевого трафіку. Реалізація нейронної мережі Кохонена для аналізу заголовків.
дипломная работа [2,2 M], добавлен 09.06.2012Определение архитектуры реляционных СУБД. Рассмотрение кластеризации как основного способа минимизации числа дисковых операций ввода-вывода данных. Применение индексов для повышения производительности SQL-запросов. Процесс кэширования в базах данных.
курсовая работа [61,1 K], добавлен 15.07.2012Программная реализация метода оптимальной классификации одномерного упорядоченного множества на основе "склеивания с ближайшим". Проверка работоспособности программы на основе алгоритмов классификации, вычислительные эксперименты по оценке эффективности.
курсовая работа [414,4 K], добавлен 24.05.2015Классификация задач Data Mining. Задача кластеризации и поиска ассоциативных правил. Определению класса объекта по его свойствам и характеристикам. Нахождение частых зависимостей между объектами или событиями. Оперативно-аналитическая обработка данных.
контрольная работа [26,1 K], добавлен 13.01.2013
