_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (1185319), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

Данный алгоритм удобен для поиска «выбросов» вданных.Алгоритм k внутригрупповых средних является одним из наиболее известныхметодов кластеризации. Алгоритм находит такие кластеры, для объектов которых центр«своего кластера» будет ближе центра любого «чужого кластера». Алгоритм состоит изследующих шагов.Шаг 1. Выбираются k исходных центров кластеров y1 (1), y 2 (1),..., y k (1) . Этот выборпроизводиться произвольно, например, первые kрезультатов выборки из заданногомножества объектов.X  {x1 , x 2 ,..., x m }Шаг l. На l-м шаге итерации заданное множество объектовраспределяется по k группировкам по следующему правилу:x  T j (l ), если x  y j (l )  x  y i (l )для всех i  1,2,..., k , i  j , где T j (l ) - множество образов, входящих в кластер с центромy j (l ) .

В случае равенства решение принимается произвольным образом.Шагl+1.Наосновегруппировок y j (l  1) ,результатовшагаlопределяютсяновыецентрыj  1,2,..., k , исходя из условия, что сумма квадратоврасстояний между всеми объектами, принадлежащими множеству T j (l ) , и новымцентром данной группировки должна быть минимальной.Центрj  1,2,..., k ,y j (l  1) , обеспечивающий минимизациюJj 2x  y j (l  1) ,xT j ( l )является выборочным средним, определенным по множествуT j (l ) .Следовательно, новые центры кластеров определяются какy j (l  1) 1Njx,j  1,2,..., k ,xT j ( l )где N j - число выборочных объектов, входящих в множество T j (l ) . Очевидно, чтоназвание алгоритма «k внутригрупповых средних» определяется способом, принятым дляпоследовательной коррекции назначения центров кластеров.Равенствоy j (l  1)  y j (l )приj  1,2,..., kявляется условием сходимостиалгоритма, и при его достижении выполнение алгоритма заканчивается.

Полученныемножества T j (l ) ,j  1,2,..., k , и образуют искомые кластеры. В противном случаепоследний шаг повторяется.102Качество работы алгоритмов, основанных на вычислении k внутригрупповыхсредних, зависит от числа выбираемых центров кластеров, от последовательности осмотраобъектов и, естественно, от геометрических особенностей данных.Алгоритмы «итеративная оптимизация» и «метод локальной оптимизации»являются близкими методами нахождения локально-оптимальных разбиений данных назаданное число кластеров в результате минимизации критерия «сумма внутриклассовыхдисперсий, или сумма квадратов ошибок» (см. раздел 2.1.).В методе локальной оптимизации в качестве функций расстояния используютсяэвклидова метрика, «максимальное отклонение признака» и «сумма отклоненийпризнаков».Строитсяпоследовательностькластеризаций,каждаякластеризацияполучается из предыдущей путем переноса некоторого объекта из одного класса в другойтак, чтобы критерий качества монотонно уменьшался.

Кроме того, в данном методеимеется возможность нахождения оптимального числа кластеров.Рассмотрим данный алгоритм с критерием качества «сумма квадратов отклонений»при заданном фиксированном числе кластеров k .a) Сначала проводится предварительное разбиение выборки объектов на группы.Выбираются k наиболее удаленных точек и объекты распределяются в группы, какмножества объектов, для которых будет ближайшей одна из выделенных точек. Функцияблизости вычисляется по указанной пользователем метрике.b) Затем проводится итеративная оптимизация функционала штрафа — суммыkвнутриклассовых разбросов J   J p , J p p 11Tp  (x , yx i T pip) 2 , где yp — центр p-й группыTp , к которой отнесен объект x i .

J p равен среднему квадрату расстояния от объектов,отнесенных в p-ю группировку, до его центра (внутриклассовому разбросу). На каждойитерации выбирается группировка Tp, объект xi и группировка Tq такие, что при переносеобъекта xi из Tp в Tq функционал J уменьшится на максимальную величину.

Процессзавершается, когда никакой последующий перенос не уменьшает функционал (полученлокальный минимум) или достигнуто указанное пользователем максимальное числоитераций. Полученные группировки объектов Tp , p=1,2,…,k,и считаются искомымикластерами.Алгоритм нахождения оптимального числа кластеров в заданном диапазоне от a доb состоит в следующем. Вначале, меняя число кластеров k в цикле от a–1 до b+1производимкластеризациюисохраняемполученноезначениекритерияJkисоответствующее распределение объектов по k кластерам. Затем строим оценки103«качества» данных кластеризаций с учетом числа кластеров.

Эти оценки основаны наэвристическом критерии поиска точки, в которой наиболее сильно падает скоростьуменьшения функционала J.Обозначим i = Ji+1 – Ji. Теперь введем следующие понятия:«взвешенная левая производная»k 1lk  i ai  a 1,2 k i 2 k  a«взвешенная правая производная»b 1rk  i kii  k 12b,2bkв которых берутся сумма значений дискретной производной i слева (справа) отрассматриваемой точки k с экспоненциально убывающими весами при удалении от точкиk так, чтобы сумма этих весов с обеих сторон была равна 1. Назовем функционаломкачества разбиения на k кластеров величину относительного изменения взвешенныхпроизводныхlkи будем выбирать то разбиение, для которого эта величина максимальна.rk3.14. Визуализация многомерных данныхПри решении задач распознавания, классификации и анализа данных важноезначение имеет наличие средств визуализации многомерных данных, позволяющихнаглядно получать представление о конфигурации классов, кластеров и расположенииотдельных объектов.

Данные средства необходимы прежде всего в случае задач сбольшим числом признаков, когда отдельные проекции в 2-3-х мерных подпространствахпризнаков содержат мало информации относительно n -мерных описаний, или в случаяхбинарных и к-значных признаков. Данная задача рассматривалась в следующей широкоизвестной постановке /19/.Пусть в n - мерном евклидовом пространстве задан набор из m элементовxi  R n , i  1 m. Требуется найти отображение этого набора точек на плоскость R 2 так,чтобы метрические соотношения между образами точек на плоскости максимальносоответствовали бы метрическим соотношениям между ними в исходном n -мерномпризнаковом пространстве: «близкие» («далекие») n - мерные точки, остались бы«близкими» («далекими») на плоскости. Данную искомую плоскость будем называтьплоскостью обобщенных признаков (параметров).104Пусть y i – отображение элемента x i на R 2 ,  ij – расстояние между элементамиx i , x j в R n , а d ij – расстояние между y i , y j в R 2 .

Будем искать такое отображение, длякоторого сумма различий расстояний между точками будет минимальнаJ ( y )    ij  dij   min .2i, jТак как функция J содержит только расстояния между точками, она инвариантна кжесткому передвижению всей конфигурации.Минимизация функциипроводится с помощью стандартной процедурыJградиентного спуска y i 1  y i  sJ (y i ), где y - конфигурация точек на плоскости, i номер итерации, J ( y i ) - значение градиента функции J , s - шаг спуска.

В качественачальной конфигурации y 0 берется проекция точек x i на некоторую плоскость. Шагспуска s меняется согласно методу «удвоения»: шаг предыдущей итерации илипоследовательно умножается либо делится на 2 до тех пор, пока наблюдается уменьшениефункции J ( y i 1 ) . Градиент вычисляется по формуле:J i (y )    ij  dij jПри большихmyi  y jdij.затраты машинного времени могут быть практическинеприемлемы, при этом может не существовать адекватного отображения исходнойконфигурации на плоскость, поэтому количество исходных элементов случайным образомуменьшается до некоторого числа n1 C, где C - подобранная экспериментальноmконстанта.

На рис. 28, 29 приведены проекция некоторой обучающей выборки с k –значными признаками и ее визуализация на плоскости обобщенных признаков.Рис. 28. Проекция данных выборкиbreast_learn на плоскость признаков№1, 6.Рис. 29. Проекция данных выборкиbreast_learn на плоскость обобщенныхпризнаков.1053.15. Использование методов распознавания при прогнозировании временныхрядов.В различных областях практической деятельности нередко возникает задачапредсказания значения переменной Zв момент времени t  1 по величине этойпеременной в предшествующие моменты времени t , t  1, t  2, . Данная задача являетсячастным случаем более общей задачи предсказания значения некоторой переменной Z~в момент времени t  1 по значениям переменных (k признаков) из множества Z в~предшествующие моменты времени t , t  1, t  2, .

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

В качестве примера можно указатьзадачу прогноза динамики курсовой стоимости акций на фондовом рынке. Выборнаправления изменения фактически является задачей отнесения ситуации, сложившейся кмоменту времени t , к двум классам: K 1 - последующий рост величины Z в моментвремени t  1 , K 2 - последующее снижение величины Z в момент времени t  1 . Вкачестве прогностических переменных (признаков) в данном случае выступают величины~переменных из множества Z в моменты t , , t  l , где l - длина временного интервала,используемого для прогноза. Иными словами ситуация может быть описана с помощьювектора-описания S  [ Z 1 (t  l ),, Z 1 (t ), , Z k (t  l ),, Z k (t )] .Имея в своем распоряжении результаты наблюдений за изменениями переменныхна некотором временном отрезке [1,2,  , T ] , где T  l , мы можем построить выборкупрецедентов S1 , S 2 ,..., S m , y ( S1 ), y ( S 2 ),..., y ( S m ) , m  T  l  1 - полное число вхожденийвременных отрезков длины l в отрезоквекторомВеличина[1,2,  , T  1] .

Характеристики

Список файлов книги