Интеллектуальный анализ данных учебное пособие. ИАД Лекции Замятин 20. Интеллектуальный анализ данных
 Скачать 2.95 Mb.
|
|
6.2.2. Без трансформации пространства признаков Основной идеей метода попарной разделимости ДМ для сни- жения размерности многомерных данных метода является использование перебора исходного P-мерного набора признаков x = {x i , i = 1, …, P} с целью максимизации заданного критерия ин- формативности и выделения подпространства y = {y i , i' = 1, …, P'} наиболее информативных полезных признаков. При этом в качестве критерия информативности признаков используется критерий инте- гральной разделимости известного набора классов { i , i = 1, …, M}, определяемых соответствующими обучающими выборками {V i , i = 1, …, M}. Интегральная разделимость вычисляется как средне- взвешенное значение попарных классовых разделимостей, опреде- ляемых расстоянием ДМ (JM) [33], характеризующим среднее Интеллектуальный анализ данных 60 расстояние между функциями условных плотностей распределения p(x| i ) и p(x| j ) соответствующей пары классов i и j . Расстояние JM ij между классами i и j определяется следующим выражением: 𝐽𝑀 𝑖𝑗 = ∫ {√𝑝(𝐱| 𝑖 ) − √𝑝(𝐱| 𝑗 )} 2 𝑑𝐱 x (6.3) Если в выражении (6.3) использовать предположение о нормаль- ном распределении условных плотностей вероятности распределения признаков x, то расчет критерия ДМ может быть представлен в виде: JM ij = 2(1 – e –B ), (6.4) где – расстояние Бхаттачария [33], зависящее от параметров двух многомерных нормальных распределений N i (x|µ i , i ) и N j (x|µ j , j ), определяемых вектором средних µ и ковариационной матрицей как 𝐵 = 1 8(µ 𝑖 –µ 𝑗 ) T { 𝑖+𝑗 2 } −1 (µ 𝑖 –µ 𝑗 ) + 1 2ln{ |(𝑖+𝑗)/2| |𝑖| 1 2|𝑗| 1 2 } (6.5) Для нахождения интегральной метрики разделимости JM ave всех классов признакового пространства используют вычисления с ис- пользованием элементов симметричной матрицы ||JM|| попарных разделимостей, расположенных выше главной диагонали 𝐽𝑀 ave = ∑ ∑ 𝑝(ω 𝑖 )𝑝(ω 𝑗 )𝐽𝑀 𝑖𝑗 𝑀 𝑗=𝑖+1 𝑀 𝑖=1 , (6.6) где p( i ) и p( j ) – весовые коэффициенты (априорные вероятности) классов i и j соответственно. Функция JM ij – расстояния (6.3) асимптотически сходится к значению 2,0. Если элемент матрицы JM ij = 2,0, то это означает, что классы i и j абсолютно разделимы и вероятность их перепутывания равна нулю. Для снятия ограничения на согласованность распределения с гауссовым в распознаваемых классах вместо оценок (6.4) и (6.5) для расчета попарных классовых разделимостей JM ij используется оценка (6.3). В качестве метода численного интегрирования для нахождения значений оценки (6.3) применяется метод Монте-Карло вычисления кратных определенных интегралов. В силу высокой вычислительной сложности нахождения значе- ний оценки (6.3) задача полного перебора комбинаций исходных B 6. Основные методы анализа и интерпретации данных 61 признаков (количество сочетаний из P по P' – С 𝑃 ′ 𝑃 ) заменяется усе- ченным перебором, основанном на отыскании информативных под- наборов (1–2 признака) в исходном P-мерном наборе признаков x из условия максимума критерия JM ave (6.6). Каждый найденный поднабор признаков добавляется в информативный набор y, и кри- терий JM ave проверяется для всех попавших в набор y компонент. Усеченный перебор исходных признаков из x завершается по дости- жении приемлемого значения критерия JM ave (обычно 1,9–2,0) или по завершении перебора всех исходных признаков x. Несмотря на бóльшую по сравнению с МГК вычислительную сложность, данный метод не накладывает ограничения на вид рас- пределения исходных признаков классифицируемых объектов и не вносит дополнительные искажения в признаковую структуру про- странства. 6.3. Классификация 6.3.1. Постановка задачи классификации Задачу классификации математически в общем случае можно представить следующим образом [67]. Для каждого класса i из ис- ходного алфавита { i , i = 1, ..., M} (M – количество предопределен- ных типов) введем понятие вероятности появления класса i в про- странстве признаков (x). Данная вероятность p( i ) называется априорной вероятностью класса i . Также предположим, что для каждого класса i известна многомерная (P-мерная) функция p(x| i ), описывающая условную плотность распределения (УПР) вектора признаков x в классе i , для которой справедливо ( | ω ) 1 i i p d x x , (6.7) Априорная вероятность p( i ) и УПР p(x | i ) являются наиболее полными вероятностными характеристиками класса i Таким образом, задача классификации может быть сформулиро- вана в виде задачи статистических решений (испытание M стати- Интеллектуальный анализ данных 62 стических гипотез) с помощью определения дискриминантной функции (x), принимающей значение i в случае, когда принима- ется гипотеза H i :x i . Полагается, что принятие классификатором решения i , когда в действительности входной образ принадлежит к классу j , приводит к потере, определяемой функцией потерь L( i | j ). Тогда условный риск R( i | x)принятия решения i в случае x j находится как 1 ( | ) ( | ω ) (ω | ) M i i j j j R L p x x , (6.8) где p( j | x) носит название апостериорной вероятности события x j и вычисляется исходя из априорной вероятности p( i ) и условной плотности распределения p(x | i ) согласно теореме Бай- еса [67] следующим образом: 1 (ω ) ( | ω ) (ω | ) (ω ) ( | ω ) j j j M k k k k p p p p p x x x (6.9) Задача классификации сводится к выбору наименьшего услов- ного риска (6.8), т.е. (x) = i : (x i ), если R( i | x) < R( j | x), i ≠ j. (6.10) Правило классификации (6.10) носит название байесовского решающего правила классификации. При использовании в (6.8) нуль-единичной функции потерь 0, ( | ) , 1,..., 1, i j i j L i j M i j (6.11) риск, соответствующий такой функции, является средней вероятно- стью ошибки (ложной классификации) и, исходя из (6.8) и (6.11), определяется как ( | ) (ω | ) 1 (ω | ), i j i j i R p p x x x i, j = 1, ..., M. (6.12) Исходя из (6.10) и (6.12), дискриминантная функция i (x) при использовании нуль-единичной функции потерь (6.11) выглядит следующим образом: i (x) = p( i ) p( x | i ), i, j = 1, ..., M, (6.13) 6. Основные методы анализа и интерпретации данных 63 и согласно (6.9) и (6.13) байесовское решающее правило (6.10) можно записать: m(x): x i , если p( i ) p( x | i ) > p( j ) p( x | j ), i j. (6.14) В параметрическом подходе к классификации при оценке УПР p(x | i ) принимается гипотеза о некотором известном виде плотно- сти распределения признаков (например, гауссовом), что позволяет использовать для нахождения p(x | i ) ее параметрическую оценку. Следует отметить, что УПР называют правдоподобием, а такой под- ход к классификации – методом максимального правдоподобия (англ. maximum likelihood, ML). В случае гауссова распределения ис- пользуется оценка вида [33]: 1/ 2 / 2 1 ˆ ˆ ˆ ( | ω ) (2 ) exp 1/ 2( ) ( ) , P t i i i i i p x x x i = 1, ..., M, (6.15) где i – выборочный вектор средних типа i ; i – выборочная кова- риационная матрица типа i ; P – количество признаков; | i | – детер- минант выборочной ковариационной матрицы типа i ; i –1 – обрат- ная выборочная ковариационная матрица типа i [67, 112]. При этом вычисление априорной вероятности p( i ) в выражении (6.9) производится с помощью простых способов, в которых p( i ) прини- мается равной для всех классов: p( i ) = p( j ), i, j = 1, ..., M, (6.16) либо пропорциональной размеру имеющихся обучающих данных: 1 ( ) , i i M k k N p N i = 1, ..., M, (6.17) где N k – размер обучающей выборки, соответствующий типу k Классификацию, в основе которой лежит байесовское решающее правило (6.9), причем вне зависимости от вида используемой оценки УПР (параметрическая или непараметрическая), называют байесовской (англ. Bayes или Naive Bayes 1 ). 1 «Наивным» байесовский классификатор называют из-за предположения о неза- висимости признаков вектора x между собой. Интеллектуальный анализ данных 64 Таким образом, основой большинства современных классифика- торов является теорема Байеса, а их математический аппарат может быть реализован с использованием различных подходов. Среди них выделяют непараметрические статистические классификаторы, включающие простые, такие как классификатор по правилу парал- лелепипеда, и значительно более сложные, использующие в своей основе непараметрическое оценивание УПР признаков [58, 71, 97, 117]. При классификации оценка УПР в выражении (6.9) на основе непараметрического подхода характеризуется меньшей чувстви- тельностью к статистическим характеристикам данных, эффективна с точки зрения точности классификации при произвольном (неиз- вестном) распределении признаков, в том числе и отличном от нор- мального (гауссова). Однако непараметрические классификаторы требуют перебора всех значений обучающей выборки при оценке УПР для каждого x, поэтому их отличают высокие вычислительные затраты. Рассмотрим более подробно этот подход в разд. 6.3.2. Также к непараметрическим относят нейросетевые классифика- торы, основанные на использовании аппарата искусственных нейронных сетей (ИНС)[100]. Однако в этом случае, как правило, не осуществляется оценка УПР. Для краткости изложения такие классификаторы называют нейросетевыми классификаторами, а искусственные нейронные сети – просто нейросетями. Рассмотрим их более подробно в разд. 6.3.3. В последнее время набирают популярность более математически сложные классификаторы с использованием машины опорных век- торов (англ. support vector machine – SVM) [7, 33]. Они характери- зуются достаточно высокой устойчивостью к статистическим ха- рактеристикам исходных векторов признаков [37, 59]. При этом классификаторы SVM по сравнению с нейросетевыми классифика- торами для задач классификации в пространстве большой размер- ности выглядят предпочтительнее – при практической реализации они вместо многоэкстремальной задачи (с вероятностью попадания в локальный экстремум) решают задачу квадратичного программи- рования, имеющую единственное решение. Кроме того, разделяю- щие поверхности решения классификаторов SVM обладают более 6. Основные методы анализа и интерпретации данных 65 высокими дифференцирующими (разделяющими) возможностями за счет максимизации ширины разделяющей полосы [37, 59]. Это относит такие классификаторы к перспективным с точки зрения вы- числительной эффективности и точности. Детали построения таких классификаторов изложены в разд. 6.3.4. 6.3.2. Контролируемая непараметрическая классификация Как отмечено выше, для проведения классификации признаков, распределение которых априори неизвестно или не согласовано с нормальным законом распределения, используют различные под- ходы к непараметрической оценке плотности распределения. Среди них наиболее широкое распространение получил подход к оценке УПР по методу k-го ближайшего соседа (для краткости будем при- водить англоязычную аббревиатуру названия метода – k-NN), кото- рая определяется, исходя из выражения [117]: 1 1 ( | ) V( , , ) P i P k p N k N x x , i = 1, ..., M, (6.18) где k P – параметр близости соседа, N – величина выборки, V(k P , N, x) – объем множества всех элементов обучающей выборки, расстояние которых до точки x в P-мерном пространстве меньше или равно R k P В случае использования евклидова расстояния / 2 1/2 V( , , ) A [( 2) / 2] P P k P R k N P x , (6.19) где Г – гамма-функция, A– единичная матрица. В выражении (6.18) величина k P является параметром, при этом существует ряд методик нахождения ее оптимального значения k опт [117]. К сожалению, поиск значения k опт ведет к увеличению вы- числительной сложности алгоритмов оценки УПР, что затрудняет их использование при решении практических задач. Поэтому на практике значение k P часто принимают фиксированным (например, 1, 3, 21, 87, N , где N – размер выборки [20, 23, 25, 117]). При этом очевидно, что большее значение k P требует большего количества Интеллектуальный анализ данных 66 операций по расчету расстояния R k P в (6.19), что ведет к дополни- тельным вычислительным затратам при классификации. Поэтому, учитывая важность проведения непараметрической классификации с высокой вычислительной эффективностью, это значение прини- мают фиксированным (например, k P = 3). Выше отмечено, что более широкому использованию непарамет- рических подходов к оценке плотности распределения препят- ствует их низкая вычислительная эффективность, связанная с необ- ходимостью перебора всех значений обучающей выборки для оценки УПР в точке x P-мерного пространства. Поэтому задача по- вышения вычислительной эффективности оценки УПР в непара- метрических методах оценки плотности для решения практических задач классификации является отдельной, интенсивно разрабатыва- емой, областью исследований [77, 99]. 6.3.3. Контролируемая непараметрическая нейросетевая классификация На сегодняшний день нейросетевой аппарат достаточно широко применяется при решении самых различных задач классификации, прогнозирования, оценки плотности распределения, поэтому при- ведем здесь лишь некоторые необходимые пояснения, связанные с областью ИНС [7, 100]. Так, широко используется такое понятие, как формальный нейрон, представляющий собой упрощенную ма- тематическую абстракцию биологического нейрона (рис. 13). Каждый такой нейрон обладает группой синапсов – однонаправ- ленных входных связей, соединенных с выходами других нейронов, а также имеет аксон – выходную связь данного нейрона, с которой сигнал может поступать на синапсы других нейронов. Каждый си- напс характеризуется величиной синаптической связи или ее весом w i . Кроме того, важной характеристикой любого формального нейрона является функция активации, или пороговая функция f (S). Наиболее распространенными пороговыми функциями являются сигмоидные функции типа гиперболического тангенса и логистиче- ской функции [98]. 6. Основные методы анализа и интерпретации данных 67 Рис. 13. Схема формального нейрона Наиболее популярными и широко распространенными, в том числе и для решения задач контролируемой классификации, явля- ются нейросети прямого распространения – многослойные персеп- троны [98]. Они позволяют работать с данными произвольного рас- пределения и учитывать такие закономерности в данных, которые затруднительно учесть другими методами [7]. Потенциально нейросетевые классификаторы обладают рядом существенных преимуществ по сравнению с традиционными стати- стическими классификаторами. Так, в качестве входных данных для них можно использовать трудноформализуемые взаимозависимые факторы произвольного распределения. Нейросетевые классифика- торы учитывают такие закономерности в данных, которые порой не могут быть учтены никаким другим классификатором [7, 100]. При этом точность классификации нейросетевых классификаторов вы- сока и приближается к байесовской [98]. Несмотря на очевидные достоинства нейросетевого подхода при классификации, существует ряд проблем, требующих решения [7, 100]. Одной из основных проблем является необходимость экспертного обучения нейросети. При этом требует решения задача определения оптимальных параметров, задающих структуру нейросети, а также параметров ее обучения. Решение этой задачи для данных различ- ной природы может иметь длительный итерационный характер, что для конечного пользователя может оказаться неприемлемым. Аксон Выход 𝑌 = 𝑓(𝑆) S 𝑥 1 𝑥 2 𝑥 3 𝑤 1 𝑤 3 𝑤 2 Входы Синапсы Интеллектуальный анализ данных 68 Существуют некоторые сложности практического применения нейросетей при решении практических задач классификации. В част- ности, применение многослойного персептрона (далее – просто нейросети) связано с решением одной из таких задач, заключающейся в определении его оптимальной топологии – количества слоев и эле- ментов (нейронов) в них. Именно правильно выбранная топология во многом определяет перспективность использования нейросетей в том или ином случае. Минимально необходимое количество элементов нейросети позволит быстро ее обучить и получить точные результаты ее применения. Однако задача определения топологии нейросети яв- ляется сложной и окончательно до сих пор не решена. В [41] предла- гается неравенство для оценки числа синаптических связей N w в виде: 2 1 1 1 log y p p w y x y y x p N N N N N N N N N N , (6.20) где N y – размерность выходного вектора, N p – число примеров обу- чающей выборки, N x – размерность входного вектора. Для практи- чески значимого варианта нейросети с одним скрытым слоем число нейронов N в нем можно определить как w x y N N N N , (6.21) При использовании выражений (6.20) и (6.21) число нейронов скрытого слоя, как правило, получается бóльшим, чем выбранное при решении практических задач эмпирически, поэтому предлагается использовать это число только в качестве рекомендации, а оконча- тельное решение по параметрам нейросети принимать эмпирически. Отметим два наиболее широко используемых на практике спо- соба определения числа нейронов в выходном слое: 1. Число нейронов равно одному (рис. 14, а). Выход интерпрети- руется как вероятность принадлежности к конкретному типу (классу). 2. Число нейронов более одного. Например, оно может быть равно количеству классов (рис. 14, б) или представлять собой некоторый вектор, значения которого интерпретируется в более сложной процеду- ре использования нейросети при оценке плотности распределения [40]. 69 6. Основные методы анализа и интерпретации данных а б Р ис 14 Не йр ос етев ы е то по ло гии : а – оди н в ы хо д, б – не ск ол ьк о вы хо до в 𝑥 1 𝑓 1 𝑥 2 𝑓 2 𝑥 𝑁 𝑥 𝑓 𝑁 … ∑ 𝑖= 1 𝑁 𝑥 𝑖 (1 ) 𝑤 𝑖1 (1 ) 𝑓 1 (1 ) ∑ 𝑖= 1 𝑁 𝑥 𝑖 (1 ) 𝑤 𝑖2 (1 ) 𝑓 2 (1 ) ∑ 𝑖= 1 𝑁 𝑥 𝑖 (1 ) 𝑤 𝑖𝐿 (1 ) … 𝑓 𝐿 (1 ) ∑ 𝑖= 1 𝐿 𝑥 𝑖 (2 ) 𝑤 𝑖2 (2 ) 𝑓 2 (1 ) 𝑑 1 Вхо дно й скр ы ты й вы хо дно й 𝑥 1 𝑓 1 𝑥 2 𝑓 2 𝑥 𝑁 𝑥 𝑓 𝑁 … ∑ 𝑖= 1 𝑁 𝑥 𝑖 (1 ) 𝑤 𝑖1 (1 ) 𝑓 1 (1 ) ∑ 𝑖= 1 𝑁 𝑥 𝑖 (1 ) 𝑤 𝑖2 (1 ) 𝑓 2 (1 ) ∑ 𝑖= 1 𝑁 𝑥 𝑖 (1 ) 𝑤 𝑖𝐿 (1 ) … 𝑓 𝐿 (1 ) ∑ 𝑖= 1 𝐿 𝑥 𝑖 (2 ) 𝑤 𝑖2 (2 ) 𝑓 2 (2 ) 𝑑 2 Вхо дно й с кр ы тый вы хо дно й ∑ 𝑖= 1 𝐿 𝑥 𝑖 (2 ) 𝑤 𝑖1 (2 ) 𝑓 1 (2 ) 𝑑 1 ∑ 𝑖= 1 𝐿 𝑥 𝑖 (2 ) 𝑤 𝑖𝑁 𝑦 (2 ) 𝑓 𝑁 𝑦 (2 ) 𝑑 𝑁 𝑦 Интеллектуальный анализ данных 70 Важным и необходимым этапом практического использования любой нейросети является процесс ее обучения. Обучение нейросети в общем случае представляет собой поиск глобального минимума многомерной целевой функции путем «исследования» нейросетью многомерного пространства выборочных обучающих данных и подстройкой w i и параметров функций активации f [7, 100]. Обучающие данные представляют собой множество входных век- торов X = {X i , i = 1, ..., N p } и множество известных выходных векторов A = {A i , i = 1, ..., N p }, где X i = {x 1 , x 2 , ..., x Nx } и A i = {a 1 , a 2 , ..., a Ny }. В процессе обучения минимизируется значение среднеквадратиче- ской ошибки (СКО), вычисляемой согласно выражению [100]: 2 1 1 2 M i i i E A Y , (6.22) где Y i = {y 1 , y 2 , ..., y Ny } – фактические значения, получаемые с выхо- дов нейросети. При программной реализации моделей нейросетей и их исполь- зовании наиболее часто в качестве алгоритма обучения применяют градиентный алгоритм обратного распространения ошибки или его модификации [41]. Этот алгоритм обладает устойчивой сходи- мостью и приемлемыми требованиями к ресурсам вычислительной техники. |