Урок 7. Методы исследования структуры данных 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Урок 7. Методы исследования структуры данных



Урок 7. Методы исследования структуры данных

Анализ многомерных данных без использования обучающей информации направлен на выяснение структуры взаимоотношений объектов и признаков ТЭД. В настоящее время накоплен обширный арсенал средств такого анализа. Наиболее полное изложение применяемых здесь подходов, сопровождающееся подробными ссылками на ключевые работы, содержится в /Айвазян С. А. и др., 1989/. Классификация известных методов анализа структуры многомерных данных приведена в табл. 7. 1.

Таблица 7. 1. Классификация методов анализа структуры данных

Методы визуализации данных Методы автоматического группирования
Линейные методы снижения размерности Нелинейные отображения Многомерное шкалирование Заполняющие пространство кривые Факторный анализ объектов и признаков Кластерный анализ объектов и признаков Иерархическое группирование Определение «точек сгущения

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

Методы визуализации данных

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

Пример применения метода главных компонент

Ниже рассматривается пример, относящийся к сравнительному оцениванию изделий, характеризующихся одновременно несколькими параметрами. Это — автомобили. В таблице приводятся выборочные сведения о фирме-изготовителе автомобиля, названии модели, а также оценочные параметры — вес (переменная weight), число цилиндров (переменная cylinders), ускорение (переменная accel), объем двигателя (переменная displace) и мощность в лошадиных силах (переменная horspower).

Таблица 7. 2

Изготови-тель Модель Вес Цил. к-во Ускорение Объем Мощность
Volkswagen Ford Mazda Datsun Honda Oldsmobile Dodge Mercury Pontiac Chevrolet Ford Ford Plymouth AMC Buick Mercury Dodge AMC Chevrolet Buick Ford Dodge Chevrolet Toyota Datsun Dodge Toyota Plymouth Oldsmobile Datsun Audi Volvo Saab Peugeot Volkswagen Honda Pontiac Mercury Ford AMC Dodge Chevrolet Ford Mercury Dodge Buick Ford Chevrolet Chrysler Volkswagen Mazda Dodge AMC Mercedes Cadillac Peugeot Oldsmobile Plymouth Plymouth Datsun Fiat Buick Chevrolet Oldsmobile Pontiac Volkswagen Toyota Chevrolet Datsun Chevrolet Ford AMC Dodge Audi Toyota Mazda Datsun Toyota Mazda Dodge Datsun Volkswagen Volkswagen Audi Mercedes Honda Renault Subaru Volkswagen Datsun Mazda Triumph Ford Honda Plymouth Buick Dodge Chevrolet Plymouth Toyota Plymouth Honda Subaru Datsun Toyota Mazda Plymouth Ford Ford Volkswagen Renault Honda Toyota Datsun Mazda Peugeot Saab Volvo Toyota Datsun Buick Oldsmobile Ford Chrysler Chevrolet Chevrolet Chevrolet Pontiac Dodge Pontiac Ford AMC Volkswagen Mazda Mazda Plymouth Mercury Nissan Honda Toyota Honda Honda Datsun Buick Oldsmobile Chrysler Ford Toyota Dodge Chevrolet Ford Volkswagen Dodge Ford Chevrolet Rabbit Dl Fiesta GLC Deluxe B210 GX Civic CVCC Cutlass Diplomat Monarch Phoenix Malibu Fairmont A Fairmont M Volare Concord Century Zephyr Aspen Concord D1 MonteCarlo RegalTurbo Futura Magnum XE Chevette Corona 510 Omni Celica GT Sapporo Starfire 200-SX 5000 264GL 99GLE 604SL Scirocco Accord LX Lemans V6 Zephyr 6 Fairmont 4 ConcordDL6 Aspen 6 Caprice Cl LTD Landau GrandMarqs St. Regis Estate SW Country SW Malibu SW Lebaron SW Rabbit Cus GLC Deluxe Colt Hatch Spirit DL 300D Eldorado 504 Cutlass Horizon HorizonTC3 210 Strada Cus SkylarkLim Citation Omega Phoenix Rabbit CorollaTer Chevette 310 Citation Fairmont Concord Aspen 4000 Corona LB 626 510 Hatch Corolla GLC Colt 210 Rabbit Dl Dasher Dl 5000S Dl 240D Civic1500G LeCar Delx DL Rabbit 280-ZX RX-7 GS TR7 Coupe Must Cobra Accord Reliant Skylark Aries SW Citation Reliant Starlet Champ Civic1300 210 Tercel GLC 4 Horizon 4 Escort 4W Escort 2H Jetta 18I Prelude Corolla 200SX 626 505S Dl 900S Diesel Cressida 810 Maxima Century Cutlass LS Granada GL Lebaron Cavalier CavalierSW Cavalier2D 1200 Hatch Aries SE Phoenix Fairmont Concord Dl Rabbit L GLC Cust l GLC Custom Horizon Lynx l Stanza XE Accord Corolla Civic M Civic A 310 GX CenturyLmt Cutlass Dl Lebaron Granada l Celica GT Charger2.2 Camaro MustangGL Pickup Rampage Ranger S-10 1985 1800 1985 2070 1800 3365 3735 3570 3535 3155 2965 2720 3430 3210 3380 3070 3620 3410 3425 3445 3205 4080 2155 2560 2300 2230 2515 2745 2855 2405 2830 3140 2795 3410 1990 2135 3245 2990 2890 3265 3360 3840 3725 3955 3830 4360 4054 3605 3940 1925 1975 1915 2670 3530 3900 3190 3420 2200 2150 2020 2130 2670 2595 2700 2556 2144 1968 2120 2019 2678 2870 3003 3381 2188 2711 2542 2434 2265 2110 2800 2110 2085 2335 2950 3250 1850 1835 2145 1845 2910 2420 2500 2905 2290 2490 2635 2620 2725 2385 1755 1875 1760 2065 1975 2050 1985 2215 2045 2380 2190 2320 2210 2350 2615 2635 3230 2800 3160 2900 2930 3415 3725 3060 3465 2605 2640 2395 2575 2525 2735 2865 3035 1980 2025 1970 2125 2125 2160 2205 2245 1965 1965 1995 2945 3015 2585 2835 2665 2370 2950 2790 2130 2295 2625 2720 4 4 4 4 4 8 8 8 6 6 6 4 6 6 6 6 6 6 8 6 8 8 4 4 4 4 4 4 4 4 5 6 4 6 4 4 6 6 4 6 6 8 8 8 8 8 8 8 8 4 4 4 4 5 8 4 8 4 4 4 4 4 6 6 4 4 4 4 4 4 4 4 6 4 4 4 4 4 4 4 4 4 4 5 4 4 4 4 4 6 3 4 4 4 4 4 4 6 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6 6 6 8 6 6 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 6 6 4 6 4 4 4 4 4 4 4 4 21,5 14,4 19,4 18,6 16,4 15,5 13,2 12,8 19,2 18,2 15,8 15,4 17,2 17,2 15,8 16,7 18,7 15,1 13,2 13,4 11,2 13,7 16,5 14,2 14,7 14,5 14,8 16,7 17,6 14,9 15,9 13,6 15,7 15,8 14,9 16,6 15,4 18,2 17,3 18,2 16,6 15,4 13,4 13,2 15,2 14,9 14,3 15 13 14 15,2 14,4 15 20,1 17,4 24,8 22,2 13,2 14,9 19,2 14,7 16 11,3 12,9 13,2 14,7 18,8 15,5 16,4 16,5 18,1 20,1 18,7 15,8 15,5 17,5 15 15,2 17,9 14,4 19,2 21,7 23,7 19,9 21,8 13,8 17,3 18 15,3 11,4 12,5 15,1 14,3 17 15,7 16,4 14,4 12,6 12,9 16,9 16,4 16,1 17,8 19,4 17,3 16 14,9 16,2 20,7 14,2 15,8 14,4 16,8 14,8 18,3 20,4 15,4 19,6 12,6 13,8 15,8 19 17,1 16,6 19,6 18,6 18 16,2 16 18 16,4 20,5 15,3 18,2 17,6 14,7 17,3 14,5 14,5 16,9 15 15,7 16,2 16,4 17 14,5 14,7 13,9 13 17,3 15,6 24,6 11,6 18,6 19,4 90 98 78 85 91 260 318 302 231 200 200 140 225 232 231 200 225 258 305 231 302 318 98 134 119 105 134 156 151 119 131 163 121 163 89 98 231 200 140 232 225 305 302 351 318 350 351 267 360 89 86 98 121 183 350 141 260 105 105 85 91 151 173 173 151 98 89 98 86 151 140 151 225 97 134 120 119 108 86 156 85 90 90 121 146 91 85 97 89 168 70 122 140 107 135 151 156 173 135 79 86 81 97 85 89 91 105 98 98 105 100 107 108 119 120 141 121 145 168 146 231 350 200 225 112 112 112 112 135 151 140 151 105 91 91 105 98 120 107 108 91 91 91 181 262 156 232 144 135 151 140 97 135 120 119 48 66 52 70 60 110 140 139 105 95 85 88 100 90 105 85 110 120 145 165 139 140 68 95 97 75 95 105 85 97 103 125 115 133 71 68 115 85 88 90 110 130 129 138 135 155 142 125 150 71 65 80 80 77 125 71 90 70 70 65 69 90 115 115 90 76 60 70 65 90 88 90 90 78 90 75 92 75 65 105 65 48 48 67 67 67 67 62 132 100 88 72 84 84 92 110 84 58 64 60 67 65 62 68 63 65 65 74 75 75 100 74 80 110 76 116 120 110 105 88 85 88 88 88 85 84 90 92 74 68 68 63 70 88 75 70 67 67 67 110 85 92 112 96 84 90 86 52 84 79 82

Введем эти данные в электронную таблицу STATGRAPHICS (в ней присутствуют также другие дополнительные параметры). Назовем файл данных cardata. Выберем Special | Multivariate Methods | Principal Components. Появляется окно диалога для задания анализируемых переменных (Рис. 7. 1).

Рис. 7. 1. Окно задания переменных для анализа по методу главных компонент

Нажимаем OK. Получаем исходную сводку анализа МГК (Рис. 7. 2).

Из полученной сводки заключаем, что анализу подвергаются переменные weight, cylinders, accel, displace и horspower, и что число объектов составляет 151. Далее следует информация непосредственно МГК: собственные значения главных компонент, упорядоченные по величине (Eigenvalue); процент дисперсии, приходящийся на каждую выделенную главную компоненту (Percent of Variance); накопленный процент дисперсии (Cumulative Percentage).

Приведенные цифры говорят о том, что уже первые две главные компоненты описывают 93,4 % дисперсии исходных данных. Третья главная компонента добавляет еще приблизительно 4,2 % дисперсии, так что в сумме это получается 97, 6% дисперсии.

Для более детального анализа нажмем кнопку табличных опций (вторая слева в верхнем ряду) и в соответствующем окне диалога (Рис. 7. 3) установим флажок компонентных весов (Component Weights). Получим следующую таблицу (Рис. 7. 4).

Рис. 7. 2. Исходная сводка МГК

Рис. 7. 3. Окно диалога табличных опций МГК

Рис. 7. 4. Веса признаков в главных компонентах

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

Рис. 7. 5. Графические опции метода главных компонент

Рис. 7. 6. Проекция исследуемых автомобилей в пространство первых трех ГК

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

Для первой наиболее многочисленной группировки характерны сравнительно небольшие: вес, количество цилиндров, мощность и объем двигателя (первая слева группа). Вместе с тем, большая доля автомашин этой группы обладают хорошим ускорением (высокие значения 2‑й ГК) и высоким соотношением веса и мощности к количеству цилиндров (3‑я ГК).

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

И, наконец, третья группа автомашин (сравнительно малочисленная) имеет большой вес, мощность, количество, цилиндров. В то же время, показатели ускорения и соотношение веса и мощности к количеству цилиндров здесь (если говорить в целом) гораздо меньшие.

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

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

То есть полагается, что значения каждого признака xi могут быть выражены взвешенной суммой латентных переменных (простых факторов) fj, количество которых меньше числа исходных признаков, и остаточным членом ei с дисперсией s 2(ei), действующей только на xi, который называют специфическим фактором.

Коэффициенты lij называются нагрузкой i -й переменной на j -й фактор или нагрузкой j -го фактора на i -ю переменную. В самой простой модели факторного анализа считается, что факторы fj взаимно независимы и их дисперсии равны единице, а случайные величины ei тоже независимы друг от друга и от какого-либо фактора fj. Максимально возможное количество факторов m при заданном числе признаков p определяется неравенством

которое должно выполняться, чтобы задача не вырождалась в тривиальную. Данное неравенство получается на основании подсчета степеней свободы, имеющихся в задаче /Лоули Д. и др., 1967/. Сумму квадратов нагрузок называют общностью соответствующего признака xi и чем больше это значение, тем лучше описывается признак xi выделенными факторами fj. Общность есть часть дисперсии признака, которую объясняют факторы. В свою очередь,  показывает, какая часть дисперсии исходного признака остается необъясненной при используемом наборе факторов, и данную величину называют специфичностью признака. Таким образом,

дисперсия признака = общность + специфичность

Основное выражение факторного анализа показывает, что коэффициент корреляции любых двух признаков xi и xj можно выразить суммой произведения нагрузок некоррелированных факторов

Задачу факторного анализа нельзя решить однозначно. Равенства в факторной модели не поддаются непосредственной проверке, так как p исходных признаков задается через (p + m) других переменных — простых и специфических факторов. Поэтому представление корреляционной матрицы факторами, как говорят ее факторизацию можно произвести бесконечно большим числом способов. Если удалось произвести факторизацию корреляционной матрицы с помощью некоторой матрицы факторных нагрузок F, то любое линейное ортогональное преобразование F (ортогональное вращение) приведен к такой же факторизации /Налимов В. В., 1971/. Поэтому нередко в одном и том же пакете программ анализа данных реализовано сразу несколько версий методов факторизации, и у исследователей возникает закономерный вопрос, какой из них лучше. Здесь сошлемся на слова одного из основоположников современного факторного анализа Г. Хартмана: «Ни в одной из работ не было показано, что какой-либо один метод приближается к ²истинным² значениям общностей лучше, чем другие методы… Выбор среди группы методов наилучшего производится в основном с точки зрения вычислительных удобств, а также склонностей и привязанностей исследователя, которому тот или иной метод казался более адекватным его представлениям об общности» /цит. по Александров В. В. и др., 1990/.

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

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

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

Другие методы линейного проецирования данных, развиваются в рамках направления, получившего название разведочный анализ данных /Тьюки Дж., 1981/. Современные методы проецирования, в частности методы целенаправленного проецирования, являются естественным обобщением охарактеризованных выше классических методов анализа данных. Их систематизация и характеристики представлены в /Айвазян С. А. и др., 1989/.

Пример применения факторного анализа

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

Настоящий пример адаптирован по данным, приведенным в отчете об изучении пожилых людей /Morrison D. F., 1990/. Испытуемые были разбиты с помощью теста Векслера на две полярные группы. Для первой группы характерно наличие признаков старения, для второй такие признаки отсутствуют.

В нашем случае будут рассмотрены 37 человек, у которых признаки старения выражены. Мы выделим (на основе экспериментальных данных) факторы и проинтерпретируем их.

Откроем файл данных с названием Senile.sf.

Таблица 7. 3. Таблица с экспериментальными данными

info similars arith picture info similars arith picture
1 7 5 9 8 20 10 10 15 8
2 8 8 5 6 21 14 7 11 5
3 16 18 11 9 22 16 11 12 11
4 8 3 7 9 23 10 7 14 6
5 6 3 13 9 24 10 10 9 6
6 11 8 10 10 25 10 7 10 10
7 12 7 9 8 26 7 6 5 9
8 8 11 9 3 27 15 12 10 6
9 14 12 11 4 28 17 15 15 8
10 13 13 13 6 29 16 13 16 9
11 13 9 9 9 30 13 10 17 8
12 13 10 15 7 31 13 10 17 10
13 14 11 12 8 32 19 12 16 10
14 15 11 11 10 33 19 15 17 11
15 13 10 15 9 34 13 10 7 8
16 10 5 8 6 35 15 11 12 8
17 10 3 7 7 36 16 9 11 11
18 17 13 13 7 37 14 13 14 9
19 10 6 10 7

Нелинейные отображения

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

Для получения нелинейных отображений y (x) задается некоторый критерий (мера) искажения структуры данных J { y (x)} и решается задача на определение минимума J. Большинство мер искажения основано на сравнении попарных расстояний между объектами в исходном пространстве  и пространстве отображения . Например, используется мера, предложенная в /Sammon J. W., 1969/ и являющаяся аналогом критерия «стресса», применяемого в многомерном шкалировании,

где  — расстояние между i -м и j -м объектами в исходном пространстве ;

 — евклидово расстояние между отображениями этих объектов в .

Если в приведенном критерии положить a < 0, то он станет более чувствительным к ошибкам отображения малых расстояний и менее чувствительным к искажению больших расстояний. При a > 0, наоборот, точнее отображаются большие расстояния и загрубляются малые, так критерий начинает сильнее реагировать на ошибки в передаче больших расстояний Обычно результаты, полученные для a < 0 лучше, чем для a > 0 /Айвазян С. А. и др., 1989/.

Несколько более разнообразные возможности предоставляет использование двухпараметрического критерия, предложенного в /Терехина А. Ю., 1986/,

Данный критерий может оказаться полезным, если при отображении объектов в  требуется большие расстояния еще больше увеличить, а малые — еще сильнее уменьшить. Этот эффект будет получен, если положить a 1 < 0 и a 2 > 0.

Поиск отображений объектов в пространство меньшей размерности, минимизирующих значение критерия J, осуществляется, как правило, с помощью различных градиентных процедур. Большой выбор таких процедур для решения данной задачи, а также разнообразные варианты критерия J предлагаются, например в /Попечителев Е. П. и др., 1985; Терехина А. Ю., 1986/. В качестве начального приближения для новых координат объектов часто используются их проекции на первые главные компоненты. Размерность пространства для визуального анализа данных в , допустимое количество итераций в градиентной процедуре и точность отображения задаются исследователем. В зависимости от выбранного критерия J могут получаться различные конфигурации точек в  и может существенно варьироваться время работы алгоритма отображения, которое также во многом определяется типом применяемой градиентной процедуры. Известны другие, менее распространенные разновидности методов нелинейного отображения объектов. Они рассматриваются, например, в /Айвазян С. А. и др., 1989/.

Многомерное шкалирование

Многомерное шкалирование — совокупность методов, позволяющих по заданной информации о мерах различия (близости) между объектами рассматриваемой совокупности приписывать каждому из этих объектов вектор характеризующих его количественных показателей. При этом размерность искомого координатного пространства задается заранее, а «погружение» в него анализируемых объектов производится таким образом, чтобы структура взаимных различий (близостей) между ними, измеренных с помощью приписываемых им вспомогательных координат, в среднем наименее отличалась бы от заданной в смысле того или иного функционала качества /Айвазян С. А., и др., 1989/.Процедуры многомерного шкалирования отличаются от описанных выше методов линейного и нелинейного проецирования данных в пространство меньшей размерности в основном тем, что исходной информацией для них служит только матрица различий (близостей) между исследуемыми объектами и не требуется знания значений признаков для этих объектов. Когда информация задана в виде матрицы попарных расстояний между объектами, используются методы так называемого метрического шкалирования. Если же элементы матрицы выражают порядковые отношения между объектами, то применяются методы неметрического шкалирования. Ниже охарактеризован классический подход к решению задачи метрического шкалирования.

Обычно, хотя и не обязательно, пространство предполагается евклидовым. Для этого случая справедливы следующие преобразования, которые необходимы для перехода от матрицы расстояний D = (dij) к координатам объектов в пространстве для визуального анализа x 1, …, xp’.

Метод определения координат точек x1, …, x N (с точностью до ортогонального вращения) и заодно размерности пространства, в которое они отображаются, основан не на непосредственном использовании матрицы D, а на преобразовании ее в матрицу B скалярных произведений центрированных векторов

где m — вектор средних значений.

Между элементами матрицы B и расстояниями dij установлено следующее соотношение

Процедура перехода от D к B называется двойным центрированием D. Матрица B размера (N ´ N) обладает следующими свойствами:

a) Неотрицательно определена.

b) Ранг матрицы B равен размерности искомого пространства отображения.

c) Ненулевые собственные числа матрицы B, упорядоченные в порядке убывания, совпадают с соответствующими собственными числами матрицы S = XX T, где X — центрированная матрица данных (неизвестная нам). Матрица S / N есть матрица ковариаций для X.

d) Пусть ur есть r‑ й собственный вектор матрицы S,соответствующий r‑ му собственному числу lr. Тогда вектор значений r ‑й главной компоненты будет zr = X T ur.

В то же время пусть yrr ‑й собственный вектор матрицы B, соответствующий тому же самому собственному значению lr, то есть

Тогда

Из свойства 4 следует, что, решая задачу собственных чисел и собственных векторов для матрицы B и ограничиваясь ненулевыми собственными числами l 1, …, lp’, получаем координатное представление точек в пространстве главных компонент, основываясь на приведенных формулах.

Элементы матрицы B могут быть представлены в виде

Очевидно, решение Z является линейной функцией X и определяется лишь с точностью до ортогонального преобразования, поскольку, применяя к матрице Z преобразование вращения, получим, что преобразованная матрица Z * столь же точно восстанавливает матрицу B, как и матрица Z. Поэтому такое шкалирование называют линейным.

Подробно с классическим подходом к многомерному шкалированию можно ознакомиться в работах /Torgerson W. S., 1952; Терехина А. Ю., 1986; Дэйвисон М., 1988/. Решение задачи шкалирования, полученное классическим линейным методом, часто используется как начальное приближение в процедурах нелинейного многомерного шкалирования, которые строятся аналогично рассмотренным выше процедурам нелинейного проецирования данных в пространство меньшей размерности. Особенности этих процедур описаны в приведенной литературе по многомерному шкалированию.

Факторный анализ объектов.

При факторном анализе объектов используется формальный аппарат факторного анализа, изначально предназначавшийся для агрегирования взаимосвязанных признаков. Этому аппарату была дана характеристика в предыдущем подразделе. Отличие состоит в том, что в факторном анализе объектов таблица экспериментальных данных поворачивается на 90 0 (транспонируется), то есть объекты и признаки меняются местами. Если при факторном анализе признаков ищутся группы близких (коррелированных) признаков на основе корреляционной матрицы, то для транспонированных данных аналогом корреляционной матрицы является матрица, описывающая попарные коэффициенты корреляции (сходства) объектов. Она вводится в алгоритм формального факторного анализа, и в результате получаются факторы, описывающие уже не группы коррелированных признаков, а группы сходных объектов /Александров В. В. и др., 1990/. Особенности данной процедуры подробно рассмотрены в /Айвазян С. А. и др., 1974/.

Кластерный анализ.

Этот анализ предназначен для разбиения множества объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества классификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых каким-либо общим свойством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования /Миркин Б. Г., 1980/:

a) внутри групп объекты должны быть тесно связаны между собой;

b) объекты разных групп должны быть далеки друг от друга;

c) при прочих равных условиях распределения объектов по группам должны быть равномерными.

Требования a) и b) выражают стандартную концепцию компактности классов разбиения /Аркадьев А. Г. и др., 1971/; требование c) состоит в том, чтобы критерий не навязывал объединения отдельных групп объектов.

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

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

Пусть wl — l ‑я группа (класс, кластер) объектов, Nl — число объектов, образующих группу, вектор ml — среднее арифметическое объектов, входящих в wl (другими словами «центр тяжести» l -й группы), а r (wl, wm ) — расстояние между группами wl и wm.

 

Рис. 7. 18. Различные способы определения расстояния между кластерами: 1 — по ближайшим объектам, 2 — по центрам тяжести, 3 — по самым дальним объектам

Расстояние ближайшего соседа есть расстояние между ближайшими объектами кластеров:

Расстояние центров тяжести равно расстоянию между центральными точками кластеров

Расстояние дальнего соседа — расстояние между самыми дальними объектами кластеров

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

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

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

Многообразие алгоритмов кластерного анализа обусловлено также множеством различных критериев, отражающих те или иные аспекты качества автоматического группирования. Простейший критерий качества непосредственно базируется на величине расстояния между кластерами. Однако такой критерий не учитывает «населенность» кластеров — относительную плотность распределения объектов внутри выделяемых группировок. Поэтому другие критерии основываются на вычислении средних расстояний между объектами внутри кластеров. Но наиболее часто применяют критерии в виде отношений показателей «населенности» кластеров к расстоянию между ними. Это, например, может быть отношение суммы межклассовых расстояний к сумме внутриклассовых (между объектами) расстояний или отношение общей дисперсии данных к сумме внутриклассовых дисперсии и дисперсий центров кластеров.

Функционалы качества и конкретные алгоритмы автоматической классификации (группирования) достаточно полно и подробно рассмотрены в /Айвазян С. А. и др., 1989/.

Иерархическое группирование

Процедуры иерархического типа предназначены для получения наглядного представления о стратификационной структуре всей исследуемой совокупности объектов. Эти процедуры основаны на последовательном объединении кластеров (агломеративные процедуры) и на последовательном разбиении (дивизимные процедуры). Наибольшее распространение получили агломеративные процедуры. Они выглядят следующим образом.

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



Поделиться:


Последнее изменение этой страницы: 2021-03-10; просмотров: 199; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.16.51.3 (0.11 с.)