Методы группировок и классификаций Методы группировок

Любая задача многомерного анализа так или иначе сводится к нахождению группировки (группи­руются или объекты, или признаки).

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

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

Метод главных компонент является представите­лем первой группы методов.

Пусть - число объектов, - число признаков, тогда норми­рованное значение -ro признака, полученное из исходной инфор­мации типа "объект-признак", необходимо представить в виде

где - -я главная компонента;

- вес -й компоненты в -й переменной (факторная нагрузка -гo фактора).

Начальными данными метода является корреляционная или кова­риационная матрица, которую строят по исходной информации. Из­вестно, что полная дисперсия -го признака

где - доля полной дисперсии -ro признака, относящаяся к -й главной компоненте ( ).

Тогда

,

где - номер признака ( );

- номер главной компоненты ( ),

есть полный вклад -й главной компоненты в дисперсию всех признаков и та доля общей дисперсии, которую рассматриваемая главная компонента объясняет. Хотя число подученных главных ком­понент равно числу исходных признаков, только небольшое число главных компонент имеет существенные вклады в объясняемую дис­персию. Главные компоненты, имеющие достаточно малые вклады, исключают из рассмотрения. Число наиболее весомых компонент сос­тавляет обычно не больше чем четвертую часть от числа рассмат­риваемых признаков. Тогда объясняемая дисперсия

,

где - число "весомых" главных компонент ( ).

Факторные нагрузки есть коэффициен­ты корреляции между фактором и исходным признаком .

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

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

Пусть коэффициент корреляции (или ковариации) двух случай­ных величин Х и Y есть X,Y . Дисперсия случайной величины Х X,X X².

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

,

которые называются факторами.

Рассматривается функционал

.

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

Максимизация соответствует требованию такого разбиения параметров, когда в одну группу попадают наиболее "близкие" меж­ду собой параметры. Действительно, при максимизации функционала для каждого фиксированного набора случайных величин в -ю группу будут попадать такие параметры, которые наиболее "близки" к ; в то же время среди всех возможных наборов слу­чайных величин будет отбираться такой набор, то каждая из величин в среднем наиболее "близка" ко всем пара­метрам из своей группы.

Если группы параметров заданы, то оптималь­ный набор факторов можно найти в результате незави­симой максимизации каждого слагаемого функционала :

При фиксированном множестве параметров фактор , удов­летворяющий записанному выше условию, находится по формуле

, (1)

где - компоненты собственного вектора матрицы R_l = {( )}, , соответствующего ее наибольшему собственному числу. С другой стороны, если величины заданы, то разбие­ние параметров на группы , обеспечивающее максимум , должно удовлетворять условию:

для каждого

,

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

Следующий итерационный алгоритм⁵⁴, опре­деляет одновременно группы и факторы . Идея его заключается в следующем.

Пусть на -м шаге итерации построено разбиение . Для каждой группы параметров строят факторы по формуле (1) и новое, -е разбиение по правилу:

относится к группе , если

. (2)

В том случае, когда существуют два или более факторов и та­кой параметр , что для этих факторов и этого параметра в фор­муле (2) имеет место равенство, параметр относится к одной из соответствующих групп произвольно. Для найденных тем или иным способом факторов их содержательная интерпретация осуществляется с помощью одномерных группировок совокупности всех изучаемых объектов по каждому из имеющихся факторов. Формирование группи­ровок проводится в диалоге человека с ЭВМ и контролируется исс­ледователем. При этом полезно строить гистограммы значений объ­ектов по выбранному фактору, а затем уже проводить группировку тем или иным методом с учетом интерпретируемости полученных ре­зультатов.

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

Каноническая корреляция - это корреляция между линейными функциями двух множеств случайных величин, кото­рая характеризуется максимально возможными значениями коэффици­ентов корреляции. В теории канонической корреляции случайные ве­личины X₁, X₂, ..., X_s и X_s+1, X_s+2, …, X_s+t линейно преобразу­ются в так называемые канонические случайные величины Y₁, Y₂, ..., Y_s и Y_s+1, Y_s+2, …, Y_s+t, такие, что:

1) все величины Y имеют нулевое математическое ожидание и единичную дисперсию;

2) внутри каждого из двух множеств величины Y некоррелированы;

3) любая величина Y из первого множества коррелирована лишь с одной величиной из второго множества;

4) ненулевые коэффициенты корреляции между величинами Y из разных множеств имеют максимальное значение. В многомерном статистическом анализе с помощью метода канонической корреляции осуществляется переход к новой системе координат, в которой кор­реляция между X₁, X₂, ..., X_s и X_s+1, X_s+2, …, X_s+t проявляется наиболее отчетливо. В результате анализа канонической корреляции может оказаться, что взаимосвязь между двумя множествами пол­ностью описывается корреляцией между несколькими каноническими случайными величинами.

Каноническую корреляцию целесообразно использовать при комплексном анализе социально-экономических блоков в исследова­нии развития региона.

Примером методов второй группы может быть метод корреляци­онных плеяд. Плеяда - группа признаков, в которой корреляци­онная связь (внутриплеядная связь) достаточно велика, а связь между признаками из разных групп (межплеядная связь) мала. Мера корреляционной связи может быть выбрана по-разному. Например, как сумма модулей коэффициентов корреляции между признаками од­ной группы. По корреляционной матрице строят граф, который разрыванием "малых" связей преобразуют в несколько подграфов. В каждом подграфе выбирают признаки (один или несколько), с помощью которых описывают полученные плеяды признаков.

Ввиду простоты этот метод часто применяют на ранних стадиях анализа.

Анализ и группировку исходных признаков как количественных, так и качественных можно также осуществить, применив метод глав­ных кластеров к транспонированной исходной матрице "объ­ект-признак".

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

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

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

Примером эвристического алгоритма, применяемого при форми­ровании классов объектов, служит известный алгоритм Мак Кина (или метод центров). Рассмотрим этот алгоритм.

Исходной информацией служит матрица "объект-признак" или матрица связи "объект-объект".

Рассмотрим случай, когда исходной является таблица "объ­ект-признак", в которой на ( )-м месте записано значение -го признака, соответствующее -му объекту, - . Объект изучаемой совокупности представля­ется в таблице в виде строки значений признаков на этом объекте или в виде точки в -мерном признаковом пространстве.

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

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

Блок "Центр" работает после блока "Класс". Этот блок перес­читывает центры классов. Для каждого класса новые координаты его центра в пространстве признаков получаются как координаты центра тяжести каждого класса. Теперь дадим формальное описание алго­ритма:

1°. Задаются точек в пространстве призна­ков, которые объявляются центрами классов.

2°. Объект относится к -му классу, , если при достигает минимума - расстояние между объектом и центром -го класса на -й итерации.

3°. Пересчитываются центры классов.

,

где - вектор значений признаков на -м объекте;

- мощность (число объектов) класса .

Пункты 2° и 3° выполняются для всех . Если мас­сив объектов исчерпан, а последовательность центров не стабили­зировалась, то описанный процесс повторяется с самого начала, причем в качестве исходных центров выбираются центры, подучивши­еся на последней итерации.

Метод Мак Кина с исходной матрицей "объект-объект" заключается в следующем. Центры выбираются по ис­ходной матрице связи "объект-объект" следующим образом. Выбира­ется максимальный по модулю отрицательный элемент . Объекты с номерами и объявляются центрами - это самые "далекие" в смысле меры связи объекты. Затем выбирается элемент , такой, что | | максимальна, причем .

После шагов будем иметь центров . В качестве центра берется объект с таким номером , что отрицательны, а | | максимальна по всем таким .

Процесс построения центров заканчивается, если исчерпаны все объекты с указанным свойством.

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

,

то есть объект относится к самому "близкому" в смысле меры свя­зи центру.

Блок "центр" в качестве нового центра -го класса вы­бирает объект этого класса, такой, что

.

Алгоритм заканчивает работу, когда процесс стабилизируется.

Для безмашинного («ручного») счета может быть использован метод вроцлавской таксономии, который был впервые применен при классификации воеводств Польши по демографическим данным. Этот метод по своей идее похож на метод корреляционных плеяд: строят граф (дерево максимальной длины), а затем его разрезают по реб­рам с минимальными связями. Имеется множество алгоритмов, напри­мер, "Краб" в, в которых "разрезание" по ребрам осуществля­ется по критерию, представленному некоторой функцией многих пе­ременных, сконструированной из эвристических соображений. Алго­ритмы, основанные на дереве максимальной длины, применяют на стадии предварительного анализа.

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

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

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

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

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

Пусть а = - матрица связей между объектами. Най­ти разбиение множества элементов на заранее не заданное число непересекающихся классов . которое максимизирует величину вида

суммы внутренних связей в за вычетом определенного порогово­го значения .

При этом считают, что диагональные элементы . Оказывается, что если оптимально в смысле критерия , то:

а) сумма внутренних связей

в каждом классе неотрицательна;

б) суммарная связь

между любыми двумя классами и неположительна.

Схема алгоритмов локальной оптимизации включает в себя три части и начинается с тривиального разбиения множества объектов на одноэлементных классов. Алгоритм "Объединение" на каждом шаге объединяет такие классы и , связи между кото­рыми максимальны до тех пор, пока все величины не станут отрицательными. Дальнейшие объединения не нужны, так как они уменьшают значение критерия.

Полученное разбиение улучшается с помощью алгоритма "Пере­мещение", после чего проводится проверка: удовлетворяет ли полу­ченное разбиение необходимым условиям оптимальности а) и б).

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

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