- •Кафедра моэвм Проф. Д.Т.Н .Геппенер в.В. «анализ и интерпретация данных»
- •1. Введение в анализ данных
- •1.1.Проблема обработки данных
- •1.2. Матрица данных
- •1.3. Гипотеза компактности и скрытых факторов
- •1.4. Структура матрицы данных и задачи обработки
- •1.5. Матрица объект – объект и признак – признак, расстояние и близость
- •1.6. Измерение признаков
- •1.7. Основные типы шкал
- •2. Классификация данных.
- •2.1. Постановка задачи
- •1. Линейные
- •2. Нелинейные решающие функции
- •2.2. Статистические методы классификации
- •2.2.1. Постановка задачи классификации как статистической задачи при известных вероятностных распределениях.
- •2.2.2. Построение классификации для нормального распределения.
- •2.2.3.Числовые примеры
- •2.2.4. Оценка качества классификации
- •2.2.5. Классификация на основе оценки апостериорной вероятности
- •2.2.6. Классификация двух нормальных распределений с неравными матрицами ковариации
- •2.2.7. Классификация нормально распределенных векторов при неизвестных параметрах распределения
- •2.2.8. Задача статистической классификации для количества классов больше 2
- •2.2.9. Линейная дискриминантная функция Фишера
- •3. Обучаемые классификаторы. Детерминистский подход.
- •3.1. Общие свойства линейных дискриминантных функций в детерминистской постановке.
- •3.2. Персептронный алгоритм получения линейных решающих правил
- •3.3. Правила поиска решения, основанные на минимизации градиента функции качества
- •3.3.1. Формальный вывод персептронного алгоритма
- •4. Кластерный анализ
- •4.1. Постановка задачи группировки данных
- •4.2 Пример
- •4.3. Критерии качества разбиения на классы
- •4.4. Основные типы кластерных процедур. Основные задачи кластерного анализа
- •4.4.1. Построение последовательной процедуры итеративной оптимизации
- •4.4.4. Иерархические процедуры группировки
- •4.4.4.1. Агломеративная процедура
- •4.5. Статистические модели группировки
- •4.6. Алгоритм автоматической классификации на основе использования кластер-анализа
- •5. Методы снижения размерности
- •5.1. Методы отбора признаков по заданному критерию
- •5.2. Метод главных компонент
- •6. Факторный анализ
- •6.1. Модель факторного анализа
- •6.2. Структура факторных уравнений
- •6.3 Неоднозначность факторного решения
- •6.4. Метод главных факторов
- •6.5. Метод центроидных факторов
- •7. Многомерное шкалирование
- •7.1. Дистанционная модель для различий
- •7.2. Модель Торгерсона
- •7.2.1.Поворот
- •7.2.2 Объективные повороты
- •7.2.3.Ручные повороты
- •7.2.4.Размерность
- •7.2.5.Интерпретация
- •7.3. Выводы
- •8. Литература
3.2. Персептронный алгоритм получения линейных решающих правил
Простейший методы получения линейных решающих функций на основе персептронных алгоритма обучения основывается на рекуррентном построении решающего правила путем коррекции ошибок.
Требуется найти T, Wn+1 для построения решающего правила d()=T + Wn+1 на основе использования конечных обучающих выборок .
Введем понятие расширенных векторов . Перейдем от размерности n к n+1 следующим образом:
-
=
W1
=
X1
..
..
Wn
Xn
Wn+1
1
Тогда наша система неравенств сводится к более простой задаче:
(*) d(X) = T > 0 (или <) x X1 (x X2)
Персептронный алгоритм основан на последовательном просмотре обучающей выборки:
X1, ... XN1……….XN
X1 X2
N = N1 + N2
Процесс обучения заключается в том, что мы циклически просматриваем выборку и подставляем получаемое значение в Wв (*), и на каждом шаге просмотра производим или не производим коррекцию весового вектора.
-
1. n+1 = n, если
x X1,
nT> 0
x X2,
nT< 0
В этом случае получен правильный ответ при классификации текущего вектора
2. n+1 = n + С, если nT < 0, x X1
n+1 = n - С, если nT > 0, x X2
Этот случай соответствует ошибочной классификации и соответственно производится коррекция весового вектора (должно быть С>0)
Эта процедура и является процедурой обучения персептронного типа.
Пусть мы имеем величину весового вектора после коррекции:
n+1 = n + С,
Подставим новый весовой вектор в выражение для решающей функции:
= (n + С)T = nT + СT = nT + C║║2 ,
Видно, что значение весовой функции увеличилось на положительную величину C║║2 , то есть мы продвинулись к правильному решению.
Показано, что если решение существует, то алгоритм сходится за конечное число шагов.
Различные варианты выбора коэффициента C позволяют улучшить данный алгоритм:
1. С – константа . Скорость сходимости может быть мала.
2. С = Cn = var(n)
Попробуем менять C на каждом шагу так .чтобы сразу получить на текущем векторе правильное решение. Здесь можно использовать такой выбор С nT + Cn║║2 > 0 , отсюда следует
Cn >
Рассмотренный алгоритм появился на основе интуитивных соображений при разработке моделей работы головного мозга человека при решении задач обучения. Дальше мы рассмотрим более формальный подход .
3.3. Правила поиска решения, основанные на минимизации градиента функции качества
3.3.1. Формальный вывод персептронного алгоритма
Y(,) – функция качества.
Определить функцию качества можно по-разному.
n+1 = n – С {} = n –
- градиент по функции .
Возьмем X X2.
Возьмем новое X’ = -X, в этом случае мы имеем правило решения, которое имеет вид:
T > 0
Неплохая функция качества имеет следующий вид:
Y(,) = ( |T| - T)
= [sgn(T) -]
-
sgn(X) =
1, X>0
-1, x<0
Тогда правило коррекции имеет вид:
n+1 = n – [n sgn(nTn) - ] =
= n + [- sgn(nTn)]
Если x X1, тогда |
n+1 = n , |
n> 0 | |
n+1 = n + С , |
n< 0 |
Для всей обучающей выборки запишем следующее:
{j}j=1..N
Рассмотрим задачу в следующем виде: Tj = bj , j=1..N
-
=
W1
=
X1
..
..
Wn
Xn
Wn+1
1
Для каждого класса мы введем обозначение:
I класс: bj = 1
II класс: bj = 2
То есть для каждого элемента мы ищем номер класса.
Мы получаем переопределенную систему уравнений N>(n+1).
Матрица будет иметь следующий вид:
-
=
x11 x12 ... x1n 1
X1T
..
=
..
xN1 xN2 ... xNn 1
XNT
= |
b1 |
|
W1 |
= (*) | ||||
.. |
= |
.. | ||||||
bN |
|
WN | ||||||
|
|
|
|
|
1 |
Решение переопределенной системы (*) мы можем найти с некоторой ошибкой.
Далее мы строим функционал качества:
J(,,) = = ║ε║2 = ║- ║2
Это функционал качества. Мы его должны минимизировать. Один из подходов – это градиентный метод:
Рассмотрим , что собой представляет матрица : ее размерность (n+1)x(n+1)
=
Если матрица невырождена, решение получается достаточно просто:
- псевдообращение матрицы Х (Матрица Мура-Пенроуза)
Если матрица является вырожденной , то в этом случае задачу можно решать с помощью метода градиентного спуска.
Можно предположить и другой вариант: Видора-Хоффа
- вектора из последовательности {xj}j . Градиент строится на каждом отдельном управлении . Процедуру мы можем повторять до тех пор , пока не будет наблюдаться сходимость . Признаком сходимости является то, что искомый параметр перестает меняться или меняется очень мало.