Определение КЛД и правило ближайшего соседства

Кусочно-линейные дискриминантные функции (КЛД)

Классификация по минимуму расстояния

Хотя этот классификатор был предложен достаточно давно, до сих пор он остается эффективным инструментом решения задачи классификации.

Решающее правило, используемое в этом методе, имеет вид:

xW_j, если D(x, z_j)=D(x, z_k), k=1,…M

где D(°) — метрика, называемая евклидовым расстоянием образа х от z_k, и z_k— есть эталонное среднее (или центр класса) для класса W_k.

Тогда

D(x, z_k) = |x - z_k|

Исходя из D(x, z_k) > D(x, z_j) j,k

Имеем

D²(x, z_k) > D²(x, z_j)

Другими словами, мы можем использовать D² вместо D в решающем правиле:

D²(x, z_k) = |x - z_k|²

Или в матричной форме

D²(x, z_k) = (x - z_k)^т (x - z_k) = х^тх–2х^т z_k+ z_k^т z_k

Учитывая, что выражение х^тх является постоянной для всех к, его можно отбросить. Тогда поиск минимума D(x, z_k) эквивалентен поиску

[–2х^т z_k+ z_k^т z_k]

или альтернативно мы должны найти

[х^т z_{k -} ½z_k^т z_k], к=1,2,…М

Последнее выражение определяет классификатор по минимуму расстояния. ДФ, используемая в классификаторе, может быть выражена как

d_k(Х) = х^т z_{k -} ½z_k^т z_{k =}х^т z_{k -} ½ |z_k|² = х^т W

где

и — расширенный вектор

Отметим, что решающая поверхность между любыми двумя классами W_i и W_j образуется плоскостью, перпендикулярной линии z_i - z_j, проходящей через ее середину.

Рис.

Доказательство этого очень просто.

Уравнение решающей поверхности классами W₁ и W₂имеет вид

d(Х) = х^т (z_{1 –} z₂) - ½(z₁^т z_{1 –}z ₂^т z₂=0

Возьмем точку — середину отрезка, соединяющего z₁, z₂

Подставим z_ср в выражение d(x)

Очевидно, сама гиперплоскость, разделяющая W₁ и W₂определяется вектором нормали:

Отметим, что классификатор по минимуму расстояния использует для представления каждого класса одну точку.

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

рис.2.6

Однако в случае, если классы не будут нормально распределенными с одинаковыми дисперсиями по всем координатам, как показано на рис.2.6.b, то будет иметь место неправильная классификация.

Даже если D₁< D₂, точка + должна быть отнесена к W₂вместо W₁. Аналогично, на рис.2.6с точка + должна быть отнесена к W₃по минимуму расстояния, однако она ближе кW₂.

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

D(x, W_k)=[ D(x, z_k^m)], (2.21)

Где к представляет к-ую категорию, m — номер m-го прототипа, N_к — число прототипов для категории к.

Это уравнение дает наименьшее расстояние между Х и каждым прототипом из W_k.

Тогда решающее правило становится таким

x W_j, если D(x, W_j)=[ D(x, W_k)],

где D(x, W_k) дается выражением (2.21)

ДФ изменяется соответственно так

d_k(Х) = [х^т z_k^m_- ½|z_k^m|²], к=1,2,…М

2.2.3. Линейная разделимость

Говорят, что классы линейно разделимы, если они классифицируются какой-либо линейной функцией, как,например, показано на рис.2.7а

рис.2.7 Линейная разделимость между классами

(а) классы W_i иW_j линейно разделимы

(b) (c) классы W_i иW_j не разделимы линейно

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

Пример выпуклой функции (рис.2.8а)

рис.2.8 Свойство выпуклости функции

(а) выпуклая решающая функция

(b) невыпуклая решающая функция

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

Кусочно-линейная функция — это функция, которая линейна в отдельных областях пространства признаков. КЛДФ дают кусочно-линейные границы между классами (категориями) как показано на рис.2.9а.

рис.2.9. Кусочно-линейная разделимость для различных классов.

Где разделяющая поверхность, показанная на рис. 2.9 невыпуклая.

ДФ определяется как

она состоит в том, что мы находим максимум d_k^m(x) среди прототипов класса к, где N_k – число прототипов в классе к и

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

Случай 1.

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

рис.2.10.Три различных случая в распознавании образов

(а) каждый класс отделяется от другого единственной разделяющей плоскостью

(b) каждый класс разделяется попарно от другого отдельной разделяющей плоскостью

(с)тоже, что и (b), но без областей неопределенностей

Случай 2

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

Например: w₁ может быть отделена от w₂ поверхностью d₁₂(x)=0 и от w₃ d₁₃(x)=0 (рис.2.10.). Всего существует M(M-2)/2 решающих поверхностей, представляемых как d_ij(x)=0 и когда d_ij(x)>0 i=j.

Случай 3.

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

2.3.2. Многослойные машины

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

На рис.2.11. показана такая машина.

Первый слой_это часть до Σ и справа от него второй слой.

определяют r-различных ДФ, представляют собой n-мерные вектора.

Первый слой состоит из нечеткого числа ДФ, чьи выходы клишируются пороговым логическим элементом как +1 или-1, в зависимости от значения f(x). Второй слой — это одна линейная поверхность с единичным весовым вектором, используемым для решения к какому классу окончательно относится вектор. Когда используется адаптивная обратная связь для обучения порогового логического элемента с , пороговый логический элемент называется адаптивным пороговым элементом (ADALINE). Когда в машине используется много пороговых элементов, это называется MADALINE — коммитет-машина (commitet).

Рассмотрим простую двухклассовую проблему для геометрической интерпретации такой машины.

Пусть мы имеем три логических элемента в первом слое:R=3 будут определять три гиперплоскости в пространстве признаков, как показано на рис.2.12.

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