ДИСКРИМИНАНТНЫЙ АНАЛИЗ -МЕТОДЫ ИНТЕРПРЕТАЦИИ - МЕТОДЫ КЛАССИФИКАЦИИ Класс 1 Класс 3 ОБЪЕКТ Х1 ХnХn ДИКРИМИНАНТНЫЕ ПЕРЕМЕННЫЕ (ДП) В сумме число объектов. - презентация

1 ДИСКРИМИНАНТНЫЙ АНАЛИЗ -МЕТОДЫ ИНТЕРПРЕТАЦИИ - МЕТОДЫ КЛАССИФИКАЦИИ Класс 1 Класс 3 ОБЪЕКТ Х1 ХnХn ДИКРИМИНАНТНЫЕ ПЕРЕМЕННЫЕ (ДП) В сумме число объектов должно всегда превышать число ДП в два раза.

2 Ограничения на ДП: 1) Ни одна переменная не может быть линейной комбинацией других. Соответственно недопустимы переменные, коэффициент корреляции которых равен 1. 2) Ковариационные матрицы для генеральных совокупностей равны между собой для различных классов. 3) Закон распределения для каждого класса является многомерным нормальным Этап интерпетации 1.Снижение размерности пространства ДП путем построения КДФ – канонические дискриминантные функции 2. Выбор наиболее информативных КДФ 3. Представление объектов в пространстве на основе КДФ

3 Построение Канонических дискриминантных функций х1 х4 х3 х2 КДФ1 КДФ2 объекты Уменьшение размерности пространства

4

5 F km =U 0 +U i X ikm +U 2 X 2km +…+U p X pkm, F km – значение КДФ для m-го объекта в группе К; X ikm – значение ДП Xi для m-го объекта в группе К; U i – коэффициенты, обеспечивающие выполнение требуемых условий; g – число классов; n k – число наблюдений в некотором классе; n. – общее число наблюдений по всем классам; X ikm – величина переменной i для m-го наблюдения в некотором классе k; X ik – средняя величина переменной i в некотором классе; X i.. – среднее значение переменной i по всем классам (общее среднее) ОБОЗНАЧЕНИЯ

6 1. Нахождение матрицы Т – разброс объектов между классами 2. Нахождение матрицы W – разброс объектов внутри классов 3. Нахождение матрицы В – матрицы межгрупповой суммы квадратов отклонений и попарных произведений. B ij =t ij -W ij

7 Для нахождения коэффициентов КДФ - необходимо решить систему уравнений Решение относительно v i и

8 Стандартизация коэффициентов Вклад каждой переменной в классификацию Максимальное количество КДФ p-g+1. СКОЛЬКО ОСТАВИТЬ ФУКНЦИЙ И КАКИЕ? Пример. P =6, классов g=3. Значит КДФ = 4 1. Статистика Уилкса 2. Собственные числа

9 Функция1Функция 2 SEPALLEN,42695, SEPALWID,52124, PETALLEN-,94726-, PETALWID-,57516, Стандартизированные коэффициенты Соб. Канон.Wilks' числа R Lambda Chi-Sqr. df p-level 032,191 0,9840, ,115380, ,28539,4711, ,52973, Наиболее значимая функция

10 Вид расположения объектов на основе КДФ КДФ1 КДФ2

11 ЭТАП КЛАССИФИКАЦИИ 1.На основе классифицирующих функций 2. На основе расстояния Махалонобиса 3. Методом Байесса 1. Классифицирующие функции H k =b k0 +b k1 X 1 +b k2 X 2 +…+b kp X p

12 КДФ1 КДФ2 У каждого класса своя классифицирующая функция H1- verginic H2- versicol SETOSAVERSICOLVIRGINIC SEPALLEN23,544215,698212,446 SEPALWID23,58797,07253,685 PETALLEN-16,43065,211512,767 PETALWID-17,39846,434221,079 Constant-86, , ,368 Н1 Н1= х х х х4 H3-setosa

13 Подстановка ДП нового объекта в классифицирующие функции для каждого класса х2 Новый объект х1 х3 х4х4 Н1= х х х х4 Н2= х1+7.07х2+5.21х3+6.43х4 Н3= х х х х4 Новый объект классифицируется к классу где h- максимальное

14 2. На основе расстояния Махалонобиса КЛАССИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ УНИВЕРСАЛЬНОГО КЛАССИФИКАТОРА БАЙЕССА

15 Концептуальная модель дискриминантного анализа Ков-я матрица Класс W1 Класс W2 Новый объект x 1,x 2,…,x p Диск-е функции Z i =α i1 x 1 +α i2 x 2 +…+ α ip x p i=1, 2, …, k 2 – критерий дискриминации

16 1. Дискриминантная функция Z i =α i1 x 1 +α i2 x 2 +…+ α ip x p,i=1, 2, …, k КЛАССИФИКАЦИЯ В СЛУЧАЕ ДВУХ КЛАССОВ Объекты – Х=(x 1,x 2,…,x p ). Предполагается, что класс W 1 имеет распределение W 2 -, где µ i =(µ i1, µ i2,…, µ ip ),i=1,2 Предполагаем, что 1 = 2 =S υj, (1) Будем относить X к W 1, если Z C, и к W 2, если Z

17 Если объект Х поступил из W 2, то Z имеет среднее Необходимо выбрать такие 1, …, р чтобы средние были удалены друг от друга Введем расстояние Махаланобиса (5) Нахождение таких коэффициентов из системы уравнений (4)

18 Эвристическая процедура классификации Pr(1|2) X в W 1 X в W 2 C Pr(2|1) (6)

19 Если вектор X принадлежит W 2 но то X относится к W 1 Pr(1|2) И Pr(2|1) - вероятность ошибочной классификации Необходимо найти такую С, чтобы Pr(1|2)+Pr(2|1) min 1.Вычисление оценок 1, …, р, удовлетворяющих системе (6) 2. Вычисление оценок 1 и 2 по (2) и (4) 3. Вычисление постоянной С по (7) 4. Для каждого объекта вычислить значение ДФ – Z 5. Если Z C, то Х принадлежит классу W 1, иначе к W 2 (7)

20 Обозначения: 1) q i – априорная вероятность, что объект принадлежит классу W i, i=1,2 2) Pr(X|W i ) - условная вероятность получения некоторого вектора наблюдений X, если известно, что объект принадлежит к классу W i, i=1,2. 3) Pr(W i |X) - условная вероятность того, что объект принадлежит к классу W i при данном векторе наблюдений X (апостериорная вероятность)

21 Теорема Байесса. Если X имеет многомерное нормальное распределение или, (8) (9)

22 Если Pr(X|W 1 )Pr(X|W 2 ) X принадлежит W 1 Или если X принадлежит W 1 min Это величина - вероятность того, что объект, принадлежащий к популяции W1, ошибочно классифицируется, как принадлежащий W2, или наоборот, объект из W2 ошибочно относится к W1. (10) (12)

23 Алгебраическое преобразование неравенства (10) Показывает, что байесовская процедура эквивалентна отнесению X к W 1, если (13) и к W 2, если (14)

24 Обозначения: 1) C(2|1) – стоимость ошибочной классификации из- за отнесения объекта из W 1 к популяции W 2. 2) Аналогично C(1|2) Обобщенная процедура классификации Байесса состоит в отнесении X к W 1, если (15)

25 и к W 2, если (16) q 1 C(2|1)Pr(2|1)+q 2 C(1|2)Pr(1|2) min (17) Вероятности ошибочной классификации (18) (19)

26 (20), 2 задается равенством (5) где В случае C(1|2)= C (2|1) и q 1 =q 2 =l/2, (21)

27 Если X принадлежит к одной из двух известных популяций с произвольными функциями плотности f 1 (x) и f 2 (x) соответственно, то обобщенная байесовская процедура сводится к отнесению X к W1, если Пример. Пусть X=(x 1,x 2 ) – вектор оценок абитуриента. Из опыта предыдущих лет известно, что µ 1 =(60,57), µ 2 =(42,39) и. Пусть q 1 =1/3, q 2 =2/3 и примем, что C(1|2)=2000 и C(2|1)=3000 долл.

28 Подставляя эти значения в систему уравнений (6), получаем 100α 1 +70α 2 =18, 70α α 2 =18, откуда α 1 =α 2 =54/510. Дискриминантная функция имеет вид Z=(54/510)(x1+x2). Согласно (2), ξ 1 =(54/510)(60+57)= 12.39, по (4) имеем ξ 2 =8.58. По (7) и (20) получаем ( )/2=10.49 и K=ln(4/3)= Обобщенная байессовская процедура относит объект X к классу W 1, если (54/510)(x1+x2) , т.е. x1+x согласно (15) Величина σ 2 (3) равна 3.81 и расстояние Махаланобиса 2 (5) равно 3.81.

29 Затем по формулам (18) - (19) получаем вероятности ошибочной классификации: Pr(2|1)=Ф(-0.83)=0.203; Pr(1|2)=Ф(-1.12)= ИТОГ: 1) Абитуриент принимается, если линейная комбинация его оценок больше или равна ) 20.3% потенциально хороших студентов отвергается комиссией и принимается 13.1% потенциально плохих

30 Классификация в случае двух многомерных нормальных популяций при неизвестных параметрах ДАНО: Имеется объект, которому соответствует вектор наблюдений X=(x 1,x 2,…,x p ). ТРЕБУЕТСЯ: отнести объект к классу W 1 с распределением. или к W 2 Метод решения. Оцениваемµ 1 через – объединенной выборочной ковариационной матрицей S=(S υj ), j=l,...,p; υ=l,...,p.

31 Т.е. заменяем µ ij на, i=l,2, j=l,...,p, и заменой S υj на υ=l,...,p. Далее ξ i, заданные (2) и (4), оцениваются величинами (22) а σ 2 заданные (3) – величиной (23)

32 Обобщенная байесовская процедура оценивания состоит в отнесении X=(x 1, x 2,…, x p ) к W 1 если Выборочное расстояние Махаланобиса (24) (25) является оценкой для 2 (5).

33 Алгоритм работы дискриминантного анализа: a)определяются коэффициенты дискриминантной функции а 1,…,а p ; б) оценивается значение дискриминантной функции Z il для каждого вектора наблюдений x il, i=1,2; l=1,…,n; в) определяются выборочные средние и г) рассчитывается выборочное расстояние Махаланобиса D 2 ; д) реализуется процедура классификации в соответствии с (24). Априорные вероятности q 1 и q 2

34 Несмещенная оценка расстояния Махаланобиса : Вероятность ошибочной классификации Pr(2|1) и Pr (1|2) Метод 1. Метод классифицирует каждый элемент выборки объема n 1 из класса W 1 и выборки объема n 2 из W 2 согласно выражению (24). Если m 1 – число наблюдений из W 1, отнесенных к W 2, и m2 - число наблюдений из W 2 классифицированных в W 1, (27)

35 Вычисление апостериорных вероятностей.

36 КЛАССИФИКАЦИЯ В СЛУЧАЕ K классов Рассмотрим случай отнесения неизвестного вектора наблюдений x pxl =(x 1,...,x p ) к одному из k классов W i, i= l,...,k, k2. Классификация в случае классов с произвольными известными распределениями Пусть f i (x) означает плотность распределения X в W i и q i – априорную вероятность того, что вектор наблюдения X принадлежит классу W i, i=l,...,k. Стоимость отнесения объекта из класса W j к W i - C(i|j), а вероятность отнесения объекта из W j к W i – Pr(i|j), i,j=l,...,k; ij.

37 Обобщенная байесовская процедура классификации относит объект Х к W i, если величина (30) Значение дискриминантной функции для i-го класса Такая процедура минимизирует ожидаемую стоимость ошибочной классификации (31)

38 Классификация в случае классов с многомерными нормальными распределениями Пусть популяция W i имеет распределение с функцией плотности f i (x), i=l,...,k. δ i =α i1 x 1 +…+α ip x p +γ i ln q i, i=1,…,k (1*) Вектор наблюдений X относится к классу W i, если значение δ i является максимальным среди всех i=l,...,k.

39 Апостериорная вероятность (2*) Пусть n i - объем i-й выборки, – ее вектор средних и S i – ковариационная матрица, i=l,...,k. Тогда в формуле (1*) можно заменить µ i на х i, и – на объединенную ковариационную матрицу S: (3*)

40 Таким образом, оценка дискриминантной функции для i-го класса имеет вид d i =a i1 x 1 +…+a ip x p +c i +ln q i, i=l,...,k (4*) При этом оценка апостериорной вероятности имеет вид (5*)