Geum.ru

Isbn 978-5-7262-1375 нейроинформатика 2011

Вид материалаДокументы

Содержание


Ключевые слова
Определение параметрического сплайна
Метод построения параметрического сплайна
Подобный материал:

ISBN 978-5-7262-1375-0. НЕЙРОИНФОРМАТИКА – 2011. Часть 1

А.В. ШКЛОВЕЦ, Н.Г. АКСАК

Харьковский национальный университет радиоэлектроники, Украина

axak@kture.kharkov.ua


МЕТОД АППРОКСИМАЦИИ СПЛАЙНАМИ

МИНИМАЛЬНОЙ ДЛИНЫ ЛИНЕЙНЫХ КАРТ КОХОНЕНА

ДЛЯ ВИЗУАЛИЗАЦИИ МНОГОМЕРНЫХ ДАННЫХ


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


Ключевые слова: визуализация многомерных данных, линейные карты Кохонена, параметрические сплайны минимальной длины


Введение


Для решения задач многомерной визуализации данных, имеющих нелинейную кластерную структуру, используются самоорганизующиеся карты Кохонена и их модификации [1–4]. На этапе непрерывного отображения данных на линейную или плоскую карту возникает ситуация отображения множества данных в одну точку, что делает их неразличимыми на карте и приводит к значительным ошибкам визуализации [1]. Данная проблема связана с кусочно-линейной или кусочно-плоской структурой карты. Одним из возможных решений [1] является аппроксимация карты в окрестности нейронов многомерными параболическими функциями. В работе [5] предлагается метод аппроксимации карты Кохонена параметрическим сплайном третьего порядка, который не позволяет полностью различать данные на карте.


Постановка задачи


Пусть для визуализации множества данных (, ) построена линейная карта Кохонена [6] в -мерном евклидовом пространстве с матрицей весовых коэффициентов , где – количество выходных нейронов,  – вектор весовых коэффициентов -ого нейрона, и множество выходных нейронов задает сетку в -мерном пространстве.

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

Определение параметрического сплайна


Вектор функция называется параметрическим сплайном степени дефекта () в -мерном пространстве [7], если

,
(1)

,
(2)

, , ,
(3)

где – сплайн степени дефекта  с уздами на сетке , являющейся равномерным разбиением отрезка на интервал; t – параметр сплайна.

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

Для простоты изложения введем следующие обозначения: , .


Метод построения параметрического сплайна

минимальной длины


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




Рис. 1. Построение параметрического сплайна


С учетом соотношений (1)-(3) и условия прохождения параметрического сплайна через точки (рис. 1) получено уравнений вида

.
(4)

Из условия гладкости первого и второго порядка получено уравнений вида

, ;
(5)

,

.
(6)

Уравнения (4), (5) и (6) образуют систему линейных алгебраических уравнений (СЛАУ), состоящую из уравнений. В работе [5] предлагается добавить к полученной СЛАУ уравнений вида



(7)

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

Для построения сплайна минимальной длины выразим коэффициенты через и . Подставляя значения коэффициентов в системе уравнений (4) в получим

, .
(8)

Запишем СЛАУ (4)–(6) в виде

.
(9)

Систему уравнений (9) представим в матричном виде
(10)


Обнулим подчеркнутые элементы в (10). Для этого вычтем из третьего уравнения первое, затем вычтем из -го уравнения -ое, , потом из -го уравнения вычтем -ое. В результате получим систему уравнений с трехдиагональной матрицей
(11)


Для решения системы (11) воспользуемся методом прогонки [9] и определим рекурсивно коэффициенты



(12)



(13)



(14)



(15)



(16)



(17)

Тогда решение системы (11) выражается через коэффициенты и :

.
(18)


Значения коэффициентов и могут быть найдены путем решения задачи минимизации длины [10] сплайна


.
(19)


Интеграл в задаче (19) в общем виде не существует. Воспользуемся интегральным неравенством Гёльдера [11]:

.
(20)

Тогда задача



(21)


является приближением задачи (19).

Раскроем интеграл в задаче (21), учитывая соотношения (1) и (3)
(22)

Учитывая (18), задача (22) выразится в виде
(23)

где
(24)

Здесь , и соответственно элементы векторов , и . Обозначим и . Задача (23) эквивалентна СЛАУ



(25)

Решив СЛАУ (25), получим
(26)

Используя системы уравнений (18) и (26), найдем все параметры сплайна . Сплайн построен.

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

Таблица 1


Количество скалярных операций алгоритма построения сплайна


Выражение
Операции

сложения T+
Операции

умножения T
Общее

количество T

(8)
n(l – 1)

0
n(l – 1)

(12)
3l – 7
3l – 6
6l –13

(13)
3
3l – 6
3l – 3

(14)
n(3l – 7)

n(3l – 4)

n(6l – 11)

(15)
0




(16)
3l – 6
3l – 5
6l – 11

(17)
n(3l – 6)

n(3l – 5)

n(6l – 11)

(24)
(10n + 18)(l – 1)

(14n + 26)(l – 1)

(24n + 44)(l – 1)

(26)
4n
6n + 5
10n + 5

(18)
6n(l – 1)

6n(l – 1)

12n(l – 1)



23nl + 24l – 26n – 28
26nl + 38l – 23n – 43
49nl + 62l – 49n – 71

В таблице приведены значения количества операций сложения , умножения и общего числа скалярных операций для нахождения промежуточных значений по вышеприведенным формулам. Общее количество скалярных операций для построения сплайна составляет . В [5] для построения сплайна требуется скалярных операций.


Выводы


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

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

  1. Зиновьев А.Ю. Визуализация многомерных данных. – Красноярск: Изд-во КГТУ, 2000. 168 с.
  2. Goppert J. Regularized SOM-Training: A Solution to the Topology-Approximation Dilemma? // Proc. of International Conference on NetWorks. Washington, DC, 1996. Vol. 1. P. 38–44.
  3. Kivimoto K. Topology Preservation in SOM // Proc. of International Conference on Neural NetWork. Washingon, DC, 1996. Vol. 1. P. 294–300.
  4. Chang M., Yu H., Heh J. Evolutionary Self-Organizing map // Proc. of International Joint Conference on Neural NetWorks. Washingon, DC, 1998.
  5. Аксак Н.Г., Шкловец А.В. Метод аппроксимации карт Кохонена кубическим параметрическим сплайном // системи управління навігації та зв‘язку. – 2010. 2(14). 70–74 с.
  6. Хайкин C. Нейронные сети: полный курс, 2-е издание: Пер. с англ. – М.: Издательский дом «Вильямс», 2006. 1104 с.
  7. Завьялов Ю.С., Квасова Б.И., Мирошниченко В.Л. Методы сплайн-функций. – М.: Наука, 1980. 352 с.
  8. Корнейчук Н.П., Бабенко В.Ф., Лигун А.А. Экстремальные свойства полиномов и сплайнов; АН Украины, ин-т математики. – Киев: Наук. думка, 1992. 304 с.
  9. Прасолов В.В. Задачи и теоремы линейной алгебры. М.: Наука, 1996. 367 с.
  10. Рашевский П.К. Курс дифференциальной геометрии (3-е изд). – М.-Л: ГИТТЛ, 1950. 428 с.
  11. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. – М.: Наука, 1976. 543 с.




УДК 004.032.26(06) Нейронные сети