Особенности задач многомерной классификации

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

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

Задача многомерной классификации – не только одна из самых распространенных в практике экономико-статистических исследований, но и одна из самых древних. Методы классификации получили развитие еще в глубокой древности, когда люди, обращая внимание на звездное небо, пытались сгруппировать звезды в своеобразные кластеры (созвездия) и дать им название в соответствии с образами, которые они им напоминали (Большая Медведица, Малая Медведица, Рыбы, Близнецы, Волк, Ворон и т.д.).

Существенное развитие методов классификации произошло в XVIII в., когда в 1757 г. французским ботаником М. Адансоном была выполнена иерархическая классификация растений и видов животных. Дальнейшее развитие методы классификации получили в работах Д. И. Менделеева при создании Периодической системы элементов во второй половине XIX в. Периодическая система, или периодическая классификация, элементов имела огромное значение для развития неорганической химии.

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

Рассмотрим основные методы и приемы, используемые для разделения объектов на группы, кластеры.

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

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

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

Задачи классификации по степени определенности границ классов можно разбить на два типа [32]:

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

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

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

Целесообразность, возможность и эффективность применения тех или иных методов классификации зависят от конкретной математической постановки задачи. Здесь необходимо учитывать, какая априорная информация используется для построения модели (априорные сведения о классах или выборочные данные).

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

Таким образом, необходимо различать следующие задачи классификации.

  • 1. Разбиение многомерного диапазона изменения значений анализируемых признаков на области, в результате чего исследуемая совокупность объектов разбивается на некоторое число однородных групп.
  • 2. Определение естественного расслоения исходных наблюдений на четко выраженные сгустки, или кластеры, находящиеся друг от друга на некотором расстоянии.

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

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

Многие исследователи, такие как Дж. Хартиган, К. Фукунага, М. Вонг, трактуют кластерный анализ широко, включая в него задачу декомпозиции распределений. Как способ представления исходных данных понятие смеси распределений использует польский исследователь Я. В. Овсиньски при рассмотрении общей постановки задачи кластерного анализа. Подобного взгляда придерживаются М. И. Шлезингер и А. В. Миленький. Е. Е. Жук и К). С. Харин также указывают на существование в кластерном анализе вероятностного и геометрического подходов, отдавая предпочтение первому [321.

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

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

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

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

Если число кластеров заранее задано, то для классификации часто используют параллельные кластерные процедуры – итерационные алгоритмы. Основной целью их использования является сокращение перебора вариантов. Наиболее распространенным среди неиерархических быстрых методов кластерного анализа является итерационный алгоритм k-средних. Идея метода заключается в разбиении множества объектов на заранее известное число кластеров таким образом, чтобы минимизировать функционал качества – сумму внутриклассовых дисперсий. Алгоритм k-средних крайне чувствителен к выбору начальных приближений центров. Неудачный выбор может приводить к плохим результатам кластеризации.

Среди наиболее популярных алгоритмов, предполагающих, что каждый кластер – нечеткое множество объектов, можно выделить алгоритм нечетких С-средних [32], близкий к алгоритму k-средних, но предполагающий определение меры принадлежности каждого объекта к каждому из кластеров. Он менее чувствителен к выбору начального приближения центров кластеров.

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

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

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

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

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

 
< Пред   СОДЕРЖАНИЕ     След >