1 глава (1219039), страница 3

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

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

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

(1.1)

_{где ω – вектор весовых коэффициентов, b – некоторое число. Значения ω и b находятся как решения оптимизационной задачи квадратичного программирования, минимизируя для обучающей выборки функцию}

(1.2)

при ограничениях

(1.3)

что согласно условиям Куна-Таккера равносильно поиску седловой точки лагранжиана

(1.4)

Причём α_i > 0 – коэффициенты лагранжиана. Для не опорных векторов соответствующие α_i = 0, так что расчёт выполняется только для опорных векторов.

В том случае, когда классы линейно не разделимы, применяются следующие подходы.

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

, (1.5)

а ограничения принимают вид

(1.6)

_{Настраиваемый параметр С позволяет регулировать отношения между двумя целями – максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки.}

_{Альтернативный подход основан на замене в приведённых формулах скалярного произведения нелинейной функции ядра, то есть скалярным произведением в пространстве с большей размерностью. Размерность получаемого пространства может быть больше размерности исходного, преобразование, сопоставленное скалярному произведению, будет нелинейным, а, значит, функция, соответствующая в исходном пространстве оптимальной разделяющей гиперплоскости, также будет нелинейной. В этом пространстве может существовать оптимальная разделяющая гиперплоскость.}

_{Вне зависимости от используемого подхода одной из основных проблем остаётся трудоёмкость процедуры обучения. Известен ряд модификаций классического SVM, например, ESVM (Editing Supporting Vector Machines), основанный на следующем алгоритме.}

• Выполнить предварительное обучение с помощью SVM получить границы решения.

• Удалить выборки, которые находятся в некоторой области вблизи границы решения, и неправильные выборки.

• Выполнить обучение с помощью SVM для новых обучающих выборок, чтобы определить новые границы решения.

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

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

1.4.2 Метод кластеризации

Основным принципом метода кластеризации k-средних (k-NN) является отнесение объекта к тому классу, который является наиболее распространённым среди «соседей» данного объекта. Соседи образуются из множества объектов, классы которых уже известны, и, исходя из заданного значения k (k ≥ 1), определяется, какой из классов наиболее многочисленен среди них. Если k = 1, то объект просто относится к классу единственного ближайшего соседа [19]. Пример применения метода кластеризации приведен в [20]. В результате использования кластерного анализа существенно повышаются характеристики качества обслуживания (QoS) и качества восприятия (QoE) передаваемого потокового видео по беспроводной сети. Метод k-NN является одним из самых простых методов интеллектуального анализа данных. Недостатком метода k-NN является чувствительность к локальной структуре данных.

1.4.3 Нейронные сети

Искусственная нейронная сеть (ИНС) – математическая модель, а также её программное или аппаратное воплощение, построенная по принципу организации и функционирования биологических нейронных сетей – сетей нервных клеток живого организма. Это понятие возникло при изучении процессов, протекающих в мозге, и при попытке смоделировать эти процессы. После разработки алгоритмов обучения получаемые модели стали использовать в практических целях: в задачах прогнозирования, для распознавания образов в задачах управления и др. [22].

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

С точки зрения машинного обучения, нейронная сеть представляет собой частный случай методов распознавания образов, дискриминантного анализа, методов кластеризации и т. п. С математической точки зрения, обучение нейронных сетей – это многопараметрическая задача нелинейной оптимизации. С точки зрения кибернетики нейронная сеть используется в задачах адаптивного управления и как алгоритмы для робототехники. С точки зрения развития вычислительной техники и программирования, нейронная сеть – способ решения проблемы эффективного параллелизма. А с точки зрения искусственного интеллекта, ИНС является основой философского течения коннективизма и основным направлением в структурном подходе по изучению возможности построения (моделирования) естественного интеллекта с помощью компьютерных алгоритмов.

Нейронные сети не программируются в привычном смысле этого слова, они обучаются. Возможность обучения – одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Технически обучение заключается в нахождении коэффициентов связей между нейронами. В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что в случае успешного обучения сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке, а также неполных и/или «зашумленных», частично искаженных данных [23].

В наиболее простом виде перцептрон (рисунок 1.3) состоит из совокупности чувствительных (сенсорных) элементов (S-элементов), на которые поступают входные сигналы. S-элементы случайным образом связаны с совокупностью ассоциативных элементов (А-элементов), выход которых отличается от нуля только тогда, когда возбуждено достаточно большое число S-элементов, воздействующих на один А-элемент. А-элементы соединены с реагирующими элементами (R-элементами) связями, коэффициенты усиления (v) которых переменны и изменяются в процессе обучения.

Рисунок 1.3 – Структура перцептрона

Взвешенные комбинации выходов R-элементов составляют реакцию системы, которая указывает на принадлежность распознаваемого объекта определенному образу. Если распознаются только два образа, то в перцептроне устанавливается только один R-элемент, который обладает двумя реакциями - положительной и отрицательной. Если образов больше двух, то для каждого образа устанавливают свой R-элемент, а выход каждого такого элемента представляет линейную комбинацию выходов A-элементов [23].

Алгоритмы, основанные на нейронных сетях, позволяют решать практические задачи, связанные с распознаванием и классификацией образов. Нейронная сеть состоит из взаимосвязанных нейронов, образующих входной, промежуточные (скрытые) и выходной слои. Обучение происходит путём корректировки значений весов нейронов для минимизации ошибки классификации. Преимуществами нейронных сетей являются их способность автоматически изменять внутренние параметры в процессе обучения, а также способность к обобщению, основной недостаток – чувствительность к шуму во входных данных высокая сложность их построения. Пример применения нейронных сетей приведён в [21], где авторы предложили с ее помощью распознавать акты вандализма на железнодорожной станции. Нейронная сеть была реализована в виде многослойного персептрона с одним скрытым слоем. Обучение производилось с помощью алгоритма обратного распространения ошибок. Количество нейронов в скрытом слое выбрано равным 20. С помощью экспериментов было показано, что увеличение количества нейронов в скрытом слое не совершенствовали систему с точки зрения качества верно обнаруженных событий.

1.4.4 Статистические методы

С помощью статистических методов можно оценить многие параметры качества обслуживания (QoS).

В сети с большим количеством сенсоров и высокой частотой передачи, пакеты могут быть потеряны из-за столкновений или перегрузки узлов.

В этом случае, даже если узлы передают согласно графику, количество принятых пакетов от конкретного источника в пределах заданного интервала является случайной величиной. Тогда число неудачных передач k в пределах заданного интервала времени имеет биномиальное распределение [13]:

(1.7)

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

Для вычисления 3S- или 6S – интервалов для оценки скорости приёма пакетов, параметры нормального распределения, такие как выборочная средняя и дисперсия должны быть оценены. Необходимый объём выборки для эффективного оценивания параметров нормального распределения зависит от дисперсии выборки и заданной точности. Если это возможно, чтобы продлить время инициализации, по крайней мере, 25-30 временных интервалов длиной , среднее и стандартное отклонение числа принятых пакетов вычисляются в соответствии с выражениями:

(1.8)

где m - размер выборки, - - выборочные значения. 3S- и 6S- интервалы, соответствующие уровням доверия 99,87% и почти 100% соответственно. Они имеют следующие выражения:

(1.9)

(1.10)

Когда сложно собрать данные в течение длительного этапа инициализации, для оценки количества принятых пакетов может быть использовано показательное распределение. Учитывая вероятность потери пакетов p < 0,1, односторонний доверительный интервал с приближённым доверительным уровнем для k потерянных пакетов является:

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

Список файлов ВКР