Интеллектуальный анализ данных

• Название: Интеллектуальный анализ данных
• Дата: 11.10.2022
• Размер: 7.76 Mb.
• Имя файла: iad_iadl.pdf
• Тип: Учебное пособие; #726651
• страница: 17 из 23

NB! В научной литературе, особенно в англоязычной классификатор Байе- са часто называют наивным (Naive Bayes). Это объясняется тем, что основным допущением при выводе теоремы Байеса является независимость событий. Од- нако, несмотря на наивность эти классификаторы дают достаточно хорошие ре- зультаты во многих жизненных ситуациях.
Вопросы для самопроверки:
1. Поясните различия интенсионального и экстенсионального подходов к описанию объектов прообраза.
2. В чем состоит метод k ближайших соседей?
3. Объясните содержание метода дробящихся эталонов.
4. В чем состоит алгоритм 1R-правила?
5. Что называется сверхчувствительностью (overfitting) алгоритма?
6. В чем состоит метод потенциальных функций?
7. Что называют потенциальной функцией i-го заряда?
8. Что является основой байесовского классификатора?
Литература:
1. Загоруйко Н.Г. Прикладной анализ данных и знаний. – Новосибирск : Изд-во
НГУ, 1990.
2. Плэтт В. Информационная работа стратегической разведки: основные принци- пы. – М.: Изд-во иностр. лит-ры, 1958.
3. Паклин Н.Б., Орешков В.И., Бизнес-аналитика: от данных к знаниям. –
СПб.: Питер, 2013.
4. Барсегян А.А. и др. Анализ данных и процессов. – СПб: БХВ-Петербург, 2009.
5. Горелик А.Л., Скрипкин В.А. Методы распознавания :Учеб. пособие для вузов. –
М.: Высш. шк., 2004.
6. Фу К. Структурные методы в распознавании образов. – М.: Мир, 1978.
7. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. – М.: Наука, 1970.

126 8. Лапко В.А. Непараметрические коллективы решающих правил. – М.: Наука,
2002.
9. Журавлев Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение. – М.: Фан, 1989.
10. Дюран Б., Оделл П. Кластерный анализ. – М.: Статистика, 1977.
11. Мандель И.Д. Кластерный анализ. – М.: Финансы и статистика, 1988.
12. Орлов А.И. Прикладная статистика. – М.: Экзамен, 2004.

127
ЛЕКЦИЯ 15
ДИСКРИМИНАНТНЫЙ АНАЛИЗ
1. Линейный дискриминантный анализ
Пусть теперь в k-мерном признаковом пространстве имеются два облака точек {X
i
}и {Y
j
}, i = 1,…, n, j = 1,…, m. Они характеризуются своими центрами a
1
и
a
2
и своими ковариационными матрицами 
1
, 
2
, вместо которых рассматривают соответствующие выборочные матрицы рассеяния S
1
= (n-k)
1
ˆ
и S
2
= (m-
k)
2
ˆ
.Обычно бывает выгодно с самого начала перейти к безразмерным величи- нам, поделив каждую компоненту на соответствующее ей СКО. Поставим задачу о выборе направления проектирования следующим образом: будем требовать, что- бы рассеяние внутри облаков - проекций было минимальным и при этом эти обла- ка разошлись как можно дальше друг от друга.
Рассмотрим формальную постановку этой задачи. Пусть имеются две квад- ратичные формы С
T
AC и С
T
BС с симметричными положительно-определенными матрицами A и B. Требуется найти единичный вектор С, являющийся решением следующей оптимизационной задачи:
1
max;
min;



C
C
BC
C
AC
C
T
T
T
Предположим, что для второй формы уже найдено удовлетворительное значение: С
T
BС=b, b>0. Будем решать задачу
,
min;
b
BC
C
AC
C
T
T


а условие нормировки
1

C
C
T
учтем позднее. Составим функцию Лагранжа
)
b
BC
C
(
AC
C
)
,
C
(
L
T
T





и приравняем нулю ее производные по С и по λ:



































b
BC
C
BC
C
AC
C
b
BC
C
C
B
A
b
BC
C
L
BC
AC
C
L
T
T
T
T
T
0
)
(
0 0
2 2
Отсюда сразу следует, что при любом b искомый вектор С* должен быть собственным вектором пучка квадратичных форм {A, B}, соответствующим одному из его собственных чисел λ*, при этом вспомним также об условии
1
*
*

C
C
T
. Вы- числим соответствующее значение функции Лагранжа или, что то же самое, зна- чение минимизируемой функции:
*
*
*
*
)
*
,
*
(
b
BC
C
AC
C
C
L
T
T






Таким образом, решение задачи состоит в том, что С – единичный собст- венный вектор пучка {A, B}, соответствующий его минимальному собственному числу λ. Это диктует два подхода к решению исходной задачи об оптимальном проектировании.
1. В качестве матрицы А выбираем сумму ковариационных матриц рас- сматриваемых совокупностей: A = Σ
1
+Σ
2
. Это означает, что минимизируется сумма внутренних дисперсий проекций C
T
Σ
1
C+ C
T
Σ
2
C.
В качестве матрицы В выбираем произведение расстояний между центрами исходных облаков: B = (a
1
-a
2
)(a
1
-a
2
)
T
, тогда C
T
BC=[(C
T
a
1
C- C
T
a
2
C) (C
T
a
1
C- C
T
a
2
C)
T
]=
(C
T
a
1
C- C
T
a
2
C)
2
– квадрат расстояния между центрами облаков-проекций. Недос- таток этого подхода в том, что матрица В имеет ранг 1, поэтому у пучка {A,B} име- ется единственное собственное подходящее собственное число λ. Данный подход обеспечивает проектирование только на прямую, что дает единственную дискри-
минантную компоненту.

128 2. В качестве матрицы А снова выбираем сумму ковариационных матриц
Σ
1
+Σ
2
, а в качестве В – ковариационную матрицу объединенного облака. При этом минимизируется сумма внутривыборочных дисперсий проекций и одновременно максимизируется их межвыборочная дисперсия. Это позволяет получить любое число
k
m  дискриминантных компонент, соответствующих m минимальным соб- ственным числам пучка {A,B}.
Элементы вектора С можно интерпретировать как веса, отражающие важ- ность каждой компоненты векторов X, Y при разделении исходных совокупностей.
Если используется несколько дискриминантных компонент, это соответствует различным независимым точкам зрения на X, Y. Иногда дискриминантным ком- понентам удается приписать некий физический смысл – тогда можно говорить о
дискриминантных факторах.
Пример. Для двух данных k-мерных выборок X = [ X
1
, X
2
,…, X
n
], Y = [ Y
1
,
Y
2
,…, Y
n
] (
2

k
) найти коэффициенты двух главных дискриминантных факторов по матрицам рассеяния и определить долю информации, объясняемую этими факторами.
Решение.
Процедура вычисления двух дискриминантных факторов по матрицам рас- сеяния function [c,d,r]=discr0(X,Y);
%X,Y - сравниваемые участки измерений - матрицы (n1xm), (n2xm)
%Проводится линейный дискриминантный анализ по рассеянию
[n1,m]=size(X); [n2,m]=size(Y);
%Вычисление матриц внутригруппового и межгруппового рассеяния
SX=cov(X)*(n1-m); SY=cov(Y)*(n2-m);
S1=SX+SY;
%Вычисление объединенной матрицы рассеяния
Z=[X;Y];
S2=cov(Z)*(n1+n2-m);
%Вариант: SX=cov(X); SY=cov(Y); S1=SX+SY; Z=[X;Y]; S2=cov(Z)*(n1+n2-m);
[P,Q]=eig(S2,S1); c=-P(:,m); d=P(:,m-1); %старшие собственные векторы пучка квадратичных форм
Процедура вычисления коэффициентов двух дискриминантных факторов по матрицам внутреннего рассеяния и расстоянию между центрами проекций function [c,d]=discr1(X,Y);
%X,Y - сравниваемые участки измерений - матрицы (n1xm), (n2xm)
%Проводится линейный дискриминантный анализ с регуляризацией
[n1,m]=size(X); [n2,m]=size(Y);
%Вычисление матриц внутригруппового и межгруппового рассеяния
SX=cov(X)*(n1-m);
SY=cov(Y)*(n2-m);
M=n1*mean(X)-n2*mean(Y);
S1=SX+SY;
S2=(M'*M+0.00001*eye(size(S1))); %регуляризация
[P,Q]=eig(S2,S1); c=-P(:,m); d=P(:,m-1); %старшие собственные векторы пучка квадратичных форм

129
Пример. Смоделировать две независимые 3-мерные выборки с заданными параметрами и представить их

В виде 3-мерных облаков точек ;

На плоскости 2 главных факторов;

На плоскости 2 главных дискриминантных факторов.
Решение. Моделирование и отображение двух выборок function modelir;
%Моделирование n=100; r12=0.5; r23=0.3; r13=0.4;
S0=[1 r12 r13; r12 1 r23; r13 r23 1];
[P,Q]=eig(S0); Q=diag([1 2 0.1]); ax=[0 -2 0]; SX=P'*Q*P; X=modl(ax,SX,n); ay=[0 2 0]; SY=P*Q*P'; Y=modl(ay,SY,n);
%=============Вывод 3-мерных облаков точек================= subplot(2,2,1); plot3(X(:,1),X(:,2), X(:,3),'*','LineWidth',2); box; grid; hold on; plot3(Y(:,1),Y(:,2),Y(:,3),'sr','LineWidth',2); title('Два 3-мерных облака',...
'FontName','Courier New Cyr','FontSize',14,'FontWeight','Bold');
%========Представление на плоскости главных факторов========
[c,d,q]=factor1([X;Y]); x1=X*c; y1=X*d; x2=Y*c; y2=Y*d; subplot(2,2,2); plot(x1,y1,'*','LineWidth',2); grid; hold on; plot(x2,y2,'sr','LineWidth',2); title('Главные факторы',...
'FontName','Courier New Cyr','FontSize',14,'FontWeight','Bold');
%========Дискриминация по матрицам рассеяния (док.8.2)=======
[c,d]=discr0(X,Y); %2 матрицы x1=X*c; y1=X*d; x2=Y*c; y2=Y*d; subplot(2,2,3); plot(x1,y1,'*','LineWidth',2); grid; hold on; plot(x2,y2,'sr','LineWidth',2); title('Дискриминация по матрицам рассеяния',...
'FontName','Courier New Cyr','FontSize',14,'FontWeight','Bold');
%====== Дискриминация по расстоянию между центрами (док.8.3)=======
[c,d]=discr1(X,Y); %2 матрицы и расстояние между центрами проекций x1=X*c; y1=X*d; x2=Y*c; y2=Y*d; subplot(2,2,4); plot(x1,y1,'*','LineWidth',2); grid; hold on; plot(x2,y2,'sr','LineWidth',2); title('Дискриминация по расстоянию между центрами',...
'FontName','Courier New Cyr','FontSize',14,'FontWeight','Bold');
Моделирование нормальной 3-мерной выборки объема n с заданными па- раметрами

130 function X=modl(a,S,n);
[P,Q]=eig(S); E0=randn(n,3); E=E0*Q; X=E*sqrtm(S);
X(:,1)=a(1)+X(:,1); X(:,2)=a(2)+X(:,2); X(:,3)=a(3)+X(:,3);
Рис.2. Результат работы программы

131
ЛЕКЦИЯ 16
КЛАСТЕРИЗАЦИЯ ДАННЫХ
1. Постановка задачи кластеризации
Формальная постановка задачи кластеризации описывается следующим образом.
Пусть задано множество объектов {Х}
n
, обладающих k свойствами, и мно- жество имен (меток) кластеров Y. Задана также функция определения схожести объектов ρ(x
i
, x
j
); i, j=1,2, … , n.
Требуется разбить множество Х на непересекающиеся подмножества – кластеры – так, чтобы каждый кластер состоял из объектов схожих между собой, а объекты различных кластеров существенно отличались по своим свойствам. При этом каждому объекту из X приписывается имя (номер кластера) из Y.
Например, при рассмотрении множества животных могут быть сформиро- ваны кластеры «Большие животные», «Сухопутные животные» и их альтернати- вы. Впрочем, для альтернатив названных кластеров достаточно затруднительно подобрать осмысленные названия.
NB! Напомним, что порядок формирования кластеров определяется переч- нем доступных характеристик исследуемого множества объектов.
Кластеризация является важной частью понятия более высокого уровня – кластерного анализа. Второй его этап – интерпретация полученных результатов – необходим для того, чтобы описать полученные результаты в терминах предмет- ной области.
NB! Прародителем кластер-анализа можно считать древнегреческого фи- лософа Демокрита. В «Письме учебному соседу» он писал: «Если суть многих вещей тебе непонятна, расположи сходные из них между собой и тебе многое станет яснее».
Кластер-анализ нашел применение в следующих ситуациях:
– понимание данных на основе выявленной кластерной структуры. Сущ- ность данной задачи заключается в группировке объектов по их характеристикам.
В данном случае неизвестное свойство – это имя кластера, к которому оно отно- ситься;
CЛОН,
МЫШЬ
КИТ
CЛОН,
КИТ
МЫШЬ
Рис.1. Примеры кластеризации по разным признакам

132
– «сжатие» данных путем замены множества объектов кластера его ти- пичным представителем;
– обнаружение закономерностей в наборах данных. В отличие от первой задачи, в этом случае существенно распределение объектов, относящихся к из- вестным классам, по кластерам.
Так, к примеру, решается задача кредитного скоринга – выявление условий
(свойств объектов), при которых клиент не склонен к своевременному возвраще- нию кредита;
– уточнение границ классов для распознавания с обучением;
– обнаружение аномалий (Novelty Detection) путем выявления нетипич- ных объектов, т.е. таких, которые наиболее непохожи на другие объекты кластера.
2. Классификация методов кластеризации
Исчерпывающей и однозначной классификации методов кластеризации еще не разработано. Одной из причин этого является постоянное развитие данного направления анализа, появление новых объектов кластеризации и адекватных им методов обработки данных.
Ниже приводится вариант классификации методов кластеризации объ- ектов в пространстве разнотипных признаков.
По виду искомой кластерной структуры выделяют методы, ориенти- рованные на разбиения (рис.2)и иерархии (рис.3).
Разбиения представляют собой «сгущения» точек, выделенные в про- странстве характеристик, т.е. группы наиболее схожих между собой объек- тов. При этом некоторые точки могут не входить в какой-либо кластер.
Методы, позволяющие строить иерархические структуры (дендрограм- мы), как правило, итеративны: на каждом шаге формируется один из уровней иерархии. На самом верхнем уровне все объекты исследуемой выборки объе- диняются в один кластер. Следует отметить, что данная операция не несет какой-либо смысловой нагрузки, но позволяет логически завершить иерар- хию.
NB! Итеративно разбивая разбиение, полученное на предыдущем шаге, по- лучим иерархическую структуру.
Рис.2. Пример разбиения
Рис.2. Пример иерархии

133
3. Иерархические алгоритмы кластеризации
По способу формирования кластеров в иерархических алгоритмах вы- деляют центроидный и дисперсионный методы и методы связи (одиночной, полной или средней).
Рис.4. Центроидный метод
Рис.5. Метод ближайшего соседа
Рис. 6. Метод дальнего соседа
Рис. 7. Метод средней связи
Рис. 8. Дисперсионный метод

134
Общим правилом является объединение двух кластеров, для которых обеспечивается минимальное значение некоторого показателя:
- для центроидного метода минимальным должно быть расстояние между
«центрами тяжести» кластеров;
- для дисперсионного метода минимизируется внутрикластерная дисперсия;
- для метода одиночной связи минимальным должно быть расстояние меж- ду ближайшими членами различных кластеров,
- для метода полной связи – расстояние между наиболее удаленными друг от друга объектами, относящимся к различным кластерам;
NB! Метод одиночной связи называют также методом «ближайшего сосе- да», а полной связи – «дальнего соседа».
- для метода средней связи выбирается минимальное среднее расстояние между объектами различных кластеров.
Один из возможных алгоритмов иерархической кластеризации основан на последовательном объединении объектов в кластеры, а кластеров – во все более крупные кластеры.
Эта процедура описывается следующим итератив- ным алгоритмом.
Каждый объект определяется отдельным кластером;
Пока количество кластеров > 1
Найти пару ближайших объектов (кластеров);
Объединить их в новый кластер;
Конец
Необходимо отметить особенность реализации центроидного метода: в нем при объединении объектов в кластеры происходит физическое замещение объе- диненных объектов некоторым абстрактным, соответствующем их центру тяжести в пространстве характеристик. Соответственно, на каждой итерации сокращается таблица взаимных расстояний. В других методах (связи, дисперсионных) физиче- ского удаления объектов не производится, поэтому таблица расстояний строится только один раз, однако, необходимы дополнительные структуры данных для хра- нения информации о кластерной структуре (какие объекты в какие кластеры вхо- дят).
Следует также сказать, что кроме рассмотренного выше алгоритма объеди- нения объектов или кластеров (агломеративного), существуют и дивизимные ал-
горитмы кластеризации, в которых исследуемое множество объектов объедине- но в единый кластер, а далее проводится его декомпозиция. При этом результаты агломеративной и дивизимной кластеризации при одинаковом правиле объедине- ния объектов и одной и той же выборке данных могут не совпадать.
Важным для анализа дендрограмм является расстояние между кластерами.
Напомним, что чем меньше расстояние, тем больше сходство, поэтому наиболее
«плотные» кластеры образуются при малых расстояниях.
При этом возможно существование объектов, представляющих собой ано- малии, поскольку значительно удалены как друг от друга, так и от других объек- тов.
Несомненными достоинствами алгоритмов иерархической кластериза-
ции полагают:

135
- возможность выбора необходимого количества кластеров на основе ана- лиза дендрограммы;
- независимость результата от начальных условий (при заданном методе объединения кластеров анализ одной и той же выборки данных дает одни и те же результаты).
Недостатком же является ограниченное количество объектов анализа: дендрограмма с количеством объектов более сотни воспринимается с трудом.
Именно вследствие этого недостатка в эпоху Больших данных (Big Data) развива- ются неиерархические алгоритмы.