Классификация на основе линейных дискриминантных форм

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

  Вместо самих измерений рассмотрим их проекции на вектор C. Этот вектор определяется либо на основе метода главных компонент, либо на основе одной из идей линейного дискриминантного анализа. Вектор C является нормалью к гиперплоскости, разделяющей рассматриваемые облака точек. Закон распределения проекции z = C^TX зависит от класса W _i, к которому принадлежит Х. Решающее правило имеет вид:

.

     В случае двух гауссовых классов с параметрами (a ₁, Σ₁) и (a ₂, Σ₂) для измерения Х из i -го класса его проекция

поэтому ошибки классификации вычисляются следующим образом:

              (7.9)

Оптимальное значение свободного члена v находят из условия

P (e) = p ₁ P ₁ + p ₂ P ₂ = min.

В принципе, можно сразу минимизировать P (e) по двум переменным, C и v.

  Пример 7. 4. Построение разделяющей прямой в двумерном пространстве.

  В условиях примера 13.1

p ₁ = p ₂ = 0.5;   X = (x, y) ^T, .

Выберем направление проектирования, при котором достигает максимума расстояние между проекциями центров классов: C =(Σ₁+Σ₂) ^-1(a ₁- a ₂). Находим:

Согласно формулам (13.9),

,

учитывая, что p ₁ = p ₂ = 0.5, находим вероятность ошибочной классификации:

Дифференцируя по v и приравнивая производную нулю, получаем для нахождения v уравнение

 откуда v = -0.13,

P ₁=1 – Φ(2.86) = 0.002; P ₂ = Φ(-2.86) = 0.002.

   Пример 7.5. Сценарий в ИМС MatLab.

Документ 7.1. Построение границы зон и оценивание величин ошибок распознавания методом Монте-Карло

clear; clc;   p1=0.5; p2=0.5; ax=[-2 0]’; ay=[2 0]; Sx =[1 0; 0 2]; Sy =[1 0.5; 0.5 1]; %Моделирование n=200; % объем выборок X=sqrtm(Sx)*randn(2,n); X(1, J =ax(1)+X(1, J; X(2, J =ax(2)+X(2, J; Y=sqrtm(Sy)*randn(2,n); Y (1, J = ay (1)+ Y (1, J; Y (2, J = ay (2)+ Y (2, J; %Границы зоны поиска X_L=min(min(X(1, J),min(Y(1, J));  X_U=max(max(X(1, J),max(Y(1, J)); Y_L=min(min(X(2, J),min(Y(2, J)); Y_U=max(max(X(2, J),max(Y(2, J)); % Случайный поиск N=2000;    % число эмуляций RN(1, J =0.5*(X_L+X_U)+(X_U-X_L)*2*(rand(1,N)-0.5); RN(2, J =0.5*(Y_L+Y_U)+(Y_U-Y_L)*2*(rand(1,N)-0.5); DX=inft(RN,ax,Sx,p1); DY=inft(RN,ay,Sy,p2); Ix=find(DX-DY>0);  Iy=find(DY-DX>0); Ky=convhull(RN(1,Iy),RN(2,Iy)); %=========== Экранный вывод ============= subplot(5,2,[1 3 5 7]); plot(X(1, J,X(2, J,’*’,’LineWidth’,2); grid; hold on; plot(Y(1, J,Y(2, J,’*r’,’LineWidth’,3); hold on; plot(RN(1,Iy(Ky)),RN(2,Iy(Ky)),’g’,’LineWidth’,3); axis(1.3*[X_L X_U Y_L Y_U]); subplot(5,2,[2 4 6 8]); plot(RN(1,Ix),RN(2,Ix),’.’,’LineWidth’,1); grid; hold on; plot(RN(1,Iy),RN(2,Iy),’.r’,’LineWidth’,1); hold on; plot(RN(1,Iy(Ky)),RN(2,Iy(Ky)),’g’,’LineWidth’,3); axis(1.8*[X_L X_U Y_L Y_U]); In_x=inpolygon(X(1, J,X(2, J,RN(1,Iy(Ky)),RN(2,Iy(Ky))); In_y=inpolygon(Y(1, J,Y(2, J,RN(1,Iy(Ky)),RN(2,Iy(Ky))); subplot(5,2,[9 10]); axis off; text(0,0.6,[‘ Доля ошибочных распознаваний в X ‘,num2str(sum(In_x)/n)],… ‘FontName’,’Courier New Cyr’,’FontSize’,14,’FontWeight’,’Bold’); text(0,0.1,['Доля ошибочных распознаваний в Y ',num2str(1-sum(In_y)/n)],… ‘FontName’,’Courier New Cyr’,’FontSize’,14,’FontWeight’,’Bold’);

Процедура-функция вычисления дискриминантного информанта

function D = inft (Z, a, S, p); %Вычисление дискриминантного информанта k=length(a); for i=1:k; Z(i, J =Z(i, J -a(i); end; D0=inv(S)*Z; D=log(p)-0.5*log(det(S))-0.5*diag(Z’*D0);

Рис. 7.4. Результат работы программы из Документа 7.1

Пример 7.6. Сценарий в ИМС MatLab.

Документ 7.2. Линейная классификация и оценивание величин ошибок распознавания

clear; clc; p1=0.5; ax=[-2 0]’; Sx=[1 0; 0 2]; p 2=0.5; ay =[2 -1]'; Sy =[1 0.5; 0.5 1]; %Моделирование n=200; % объем выборок X=sqrtm(Sx)*randn(2,n); Y=sqrtm(Sy)*randn(2,n); X(1, J =ax(1)+X(1, J; X(2, J =ax(2)+X(2, J; Y(1, J =ay(1)+Y(1, J; Y(2, J =ay(2)+Y(2, J; %Оценивание параметров Sxx = cov (X ');    Syy = cov (Y '); axx =(mean (X '))'; ayy =(mean (Y '))'; %векторы-столбцы %Проектирование C=inv(Sxx+Syy)*(axx-ayy); x=C’*X; a_x=C’*axx; s_x=sqrt(C’*Sxx*C); y=C’*Y; a_y=C’*ayy; s_y=sqrt(C’*Syy*C); % Оптимизация свободного члена v=-2:0.01:2; P1=normcdf(v,a_x,s_x); P2=1-normcdf(v,a_y,s_y); P=p1*P1+p2*P2; [p0, I]=min(P); v_opt=v(I); %==== Графический вывод =====   subplot(5, 2, [1 3 5 7]); plot(v,P,’LineWidth’,2); grid; xlabel(‘ Свободный член v’,’FontName’,’Courier New Cyr’, ‘FontSize’,12,’FontWeight’,’Bold’); ylabel(‘ Вероятность ошибки ’,’FontName’,’Courier New Cyr’, ‘FontSize’,12,’FontWeight’,’Bold’); t=[-2 2];   subplot(5, 2, [2 4 6 8]); plot(X(1,X(2,:)’*’,’LineWidth’,1); grid; hold on; plot(Y(1,:),Y(2,’*r’,’LineWidth’,1); hold on; plot(t,(v_opt-C(1)*t)/C(2),’g’,’LineWidth’,3); axis([min([X(1,:), Y(1,:)]), max([X(1,:) Y(1,:)]), min([X(2,:) Y(2,:)]), max([X(2,:) Y(2,:)])]);   subplot(5,2,[9 10]); axis off; text(0,0.2,[‘ Свободный член v opt= ‘,num2str(v_opt),’ P= ‘,num2str(P(I))],… ‘FontName’,’Courier New Cyr’,’FontSize’,14,’FontWeight’,’Bold’);

Рис.7.5. Результат работы программы из Документа 7.2

Задания на лабораторную работу

1. Смоделировать две 3-мерные выборки (n =100) из нормального закона с различными средними и ковариационными матрицами.

2. Произвести классификацию полученных данных 3 различными способами.

3. Проанализировать зависимость результатов классификации от расстояния Махаланобиса между исходными классами.

4. Перейти к плоскости главных компонент и изобразить на ней зоны притяжения каждого из классов.

Контрольные вопросы

  Знать основные определения теории классификации в линейном и нелинейном вариантах, технологии построения дискриминантных информантов в одномерном и многомерном случаях.

КЛАСТЕРНЫЙ АНАЛИЗ

  Кластерный анализ (автоматическая классификация, распознавание образов без учителя, таксономия, кластер-анализ) – это совокупность методов, подходов и процедур, предназначенных для разбиения исследуемой совокупности на подмножества относительно сходных между собой объектов (кластеры, таксоны, классы). В основе лежит неформальное предположение о том, что объекты, относимые к одному кластеру, должны иметь большее сходство между собой, чем с объектами других кластеров.