Основные понятия теории классификации

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

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

При внедрении современных эконометрических и статистиче¬ских методов в практику технико-экономических исследований, при разработке соответствующих программных продуктов невозможно обойтись без классификации этих методов. Естественно исходить из вида обрабатываемых данных. В соответствии с современными воз¬зрениями делим эконометрику и прикладную статистику на четыре области: статистика случайных величин (одномерная статистика); многомерный статистический анализ; статистика временных рядов и случайных величин; статистика объектов нечисловой природы.
В первой области элемент выборки - число, во второй - век¬тор, в третьей - функция, в четвертой - объект нечисловой при¬роды. Термин «объект нечисловой природы» относится к элемен¬там математического пространства, не являющегося векторным (линейным). Их нельзя складывать, умножать на числа, в отличие от чисел, векторов и функций. Примерами являются бинарные от¬ношения (упорядочения, разбиения на классы, толерантности); множества, нечеткие множества; результаты измерений в номи¬нальной и порядковой шкалах (т.е. по качественным признакам), в частности булевы вектора; вектора разнотипных признаков; тек¬сты и т.д.
Математический аппарат статистики объектов нечисловой при¬роды базируется на использовании расстояний (мер близости, пока¬зателей различия) в пространствах таких объектов. Это вызвано от¬сутствием в таких пространствах операций суммирования, на которых основано большинство методов других областей статисти¬ки. Любые методы, использующие только расстояния (меры близо¬сти, показатели различия) между объектами, следует относить к ста¬тистике объектов нечисловой природы, поскольку такие методы могут работать с объектами произвольного пространства, если в нем задана метрика или ее аналоги.
Таким образом, весьма многие математические методы класси¬фикации объектов или признаков следует включать в статистику объектов нечисловой природы. Она является уже весьма развитой области прикладной математики.
Рассматриваем важное направление эконометрики и прикладной статистики - математические методы классификации. Основная их часть относится к статистике объектов нечисловой природы, а именно, методы классификации, основанные на расстояниях между объектами.
Основные направления в математической теории классифи-кации. Какие научные исследования относить к этой теории? Исхо¬дя из потребностей специалиста, применяющего математические методы классификации, целесообразно принять, что сюда входят исследования, во-первых, отнесенные самими авторами к этой тео¬рии; во вторых, связанные с ней общностью тематики, хотя бы и не упоминался термин «классификация». Это предполагает ее слож¬ную внутреннюю структуру.
В литературных источниках наряду с термином «классифика¬ция» в близких смыслах используются термины «группировка», «распознавание образов», «диагностика», «дискриминация», «сор¬тировка» и др. Терминологический разнобой связан прежде всего с традициями научных кланов, к которым относятся авторы публика¬ций, а также с внутренним делением самой теории классификации.
В научных исследованиях по современной теории классификации можно выделить два относительно самостоятельных направления. Одно из них опирается на опыт таких наук, как биология, география, геология, и таких прикладных областей, как ведение классификаторов продукции и библиотечное дело. Типичные объекты рассмотрения - классификация химических элементов (таблица Д.И. Менделеева), биологическая систематика, универсальная десятичная классифика¬ция публикаций (УДК), классификатор товаров на основе штрих-кодов.
Другое направление опирается на опыт технических исследова¬ний, экономики, маркетинговых исследований, социологии, меди¬цины. Типичные задачи - техническая и медицинская диагностика, а также, например, разбиение на группы отраслей промышленности, тесно связанных между собой, выделение групп однородной про¬дукции. Обычно используются такие термины, как «распознавание образов» или «дискриминантный анализ». Это направление обычно опирается на математические модели; для проведения расчетов ин¬тенсивно используется ЭВМ. Однако относить его к математике столь же нецелесообразно, как астрономию или квантовую механи¬ку. Рассматриваемые математические модели можно и нужно изу¬чать на формальном уровне, и такие исследования проводятся. Но направление в целом сконцентрировано на решении конкретных за¬дач прикладных областей и вносит вклад в технические или эконо¬мические науки, медицину, социологию, но, как правило, не в мате¬матику. Использование математических методов как инструмента исследования нельзя относить к чистой математике.
В 60-х годах XX в. внутри прикладной статистики достаточно четко оформилась область, посвященная методам классификации. Несколько модифицируя формулировки М. Дж. Кендалла и А. Стьюарта 1966 г., в теории классификации выделим три подобласти: дискриминация (дискриминантный анализ), класте¬ризация (кластер-анализ), группировка. Опишем эти подобласти.
В дискриминантном анализе классы предполагаются заданными плотностями вероятностей или обучающими выборками. Задача со¬стоит в том, чтобы вновь поступающий объект отнести в один из этих классов. У понятия «дискриминация» имеется много синонимов: ди¬агностика, распознавание образов с учителем, автоматическая клас¬сификация с учителем, статистическая классификация и т.д.
При кластеризации и группировке целью является выявление и выделение классов. Синонимы: построение классификации, распо¬знавание образов без учителя, автоматическая классификация без учителя, таксономия и др. Задача кластер-анализа состоит в выясне¬нии по эмпирическим данным, насколько элементы «группируются» или распадаются на изолированные «скопления», «кластеры». (от cluster (англ.) - гроздь, скопление). Иными словами, задача - вы¬явление естественного разбиения на классы, свободного от субъек¬тивизма исследователя, а цель - выделение групп однородных объ¬ектов, сходных между собой, при резком отличии этих групп друг от друга.
При группировке, наоборот, «мы хотим разбить элементы на группы независимо от того, естественны ли границы разбиения или нет». Цель по-прежнему состоит в выявлении групп однородных объектов, сходных между собой (как в кластер-анализе), однако «соседние» группы могут не иметь резких разли¬чий (в отличие от кластер-анализа). Границы между группами ус¬ловны, не являются естественными, зависят от субъективизма ис¬следователя. Аналогично при лесоустройстве проведение просек (границ участков) зависит от специалистов лесного ведомства, а не от свойств леса.
Задачи кластеризации и группировки принципиально различны, хотя для их решения могут применяться одни и те же алгоритмы.
Важная для практической деятельности проблема состоит в том, чтобы понять, разрешима ли задача кластер-анализа для конкретных данных или возможна только их группировка, поскольку они доста¬точно однородны и не разбиваются на резко разделяющиеся между собой кластеры.
Как правило, в математических задачах кластеризации и группи¬ровки основное - выбор метрики, расстояния между объектами, меры близости, сходства, различия. Хорошо известно, что для лю¬бого заданного разбиения объектов на группы и любого е > 0 можно указать метрику такую, что расстояния между объектами из одной группы будут меньше е, а между объектами из разных групп - больше 1/Е. Тогда любой разумный алгоритм кластеризации даст именно заданное разбиение.
Ситуация осложняется использованием одного и того же термина в разных смыслах. Термином «классификация» (и термином «диагно¬стика») обозначают, по крайней мере, три разные вещи: процедуру построения классификации (и выделение классов, используемых при диагностике), построенную классификацию (систему выделенных классов) и процедуру ее использования (правила отнесения вновь по¬ступающего объекта к одному из ранее выделенных классов). Други¬ми словами, имеем естественную триаду: построение - изучение -использование классификации.
Как уже отмечалось, для построения системы диагностических классов используют разнообразные методы кластерного анализа и группировки объектов. Наименее известен второй член триады -изучение отношений эквивалентности, полученных в результате по¬строения системы диагностических классов. Статистический анализ полученных, в частности экспертами, отношений эквивалентности - часть статистики бинарных отношений и тем самым - статисти¬ки объектов нечисловой природы. Помимо общих результатов этой области эконометрики и прикладной статистики, представляют ин¬терес частные результаты, полученные специально для отношений эквивалентности.
Диагностика в узком смысле слова (процедура использования классификации, т.е. отнесения вновь поступающего объекта к одно¬му из выделенных ранее классов) - предмет дискриминантного анализа. Отметим, что с точки зрения статистики объектов нечисло¬вой природы дискриминантный анализ является частным случаем общей схемы регрессионного анализа, соответствующим ситуации, когда зависимая переменная принимает конечное число значений, а именно - номера классов, а вместо квадрата разности стоит функ¬ция потерь от неправильной классификации. Однако есть ряд спе¬цифических постановок, выделяющих задачи диагностики среди всех регрессионных задач.
О построении диагностических правил. Начнем с обсуждения одного распространенного заблуждения. Иногда рекомендуют сна¬чала построить систему диагностических классов, а потом в каждом диагностическом классе отдельно проводить регрессионный анализ (в классическом смысле) или применять иные методы многомерного статистического анализа. Однако обычно забывают, что при этом нельзя опираться на вероятностную модель многомерного нормаль¬ного распределения, так как распределение результатов наблюде¬ний, попавших в определенный кластер, будет отнюдь не нормаль¬ным, а усеченным нормальным (усечение определяется границами кластера).
Процедуры построения диагностических правил делятся на ве-роятностные и детерминированные. К первым относятся так назы¬ваемые задачи расщепления смесей. В них предполагается, что рас¬пределение вновь поступающего случайного элемента является смесью вероятностных законов, соответствующих диагностическим классам. Как и при выборе степени полинома в регрессии, при анализе реальных социально-экономических данных встает вопрос об оценке числа элементов смеси, т.е. числа диагностиче¬ских классов. Были изучены результаты применения обычно реко¬мендуемого критерия Уилкса для оценки числа элементов смеси. Оказалось, что оценка с помощью критерия Уилкса не является состоятельной, асимптотическое распределение этой оценки - гео-метрическое, как и в случае задачи восстановления зависимости в регрессионном анализе. Итак, продемонстрирована несостоятель¬ность обычно используемых оценок. Для получения состоятельных оценок достаточно связать уровень значимости в критерии Уилкса с объемом выборки, как это было предложено и для задач регрессии.
Как уже отмечалось, задачи построения системы диагностиче¬ских классов целесообразно разбить на два типа: с четко разделен¬ными кластерами (задачи кластер-анализа) и с условными граница¬ми, непрерывно переходящими друг в друга классами (задачи группировки). Такое деление полезно, хотя в обоих случаях могут применяться одинаковые алгоритмы. Сколько же существует алго¬ритмов построения системы диагностических правил? Иногда называют то или иное число. На самом же деле их бесконечно много, в чем нетрудно убедиться.
Действительно, рассмотрим один определенный алгоритм - ал¬горитм средней связи. Он основан на использовании некоторой меры близости d(x, у) между объектами х и у. Как он работает? На первом шаге каждый объект рассматривается как отдельный кластер. На ка¬ждом следующем шаге объединяются две ближайших кластера. Рас¬стояние между кластерами рассчитывается как средняя связь (отсюда и название алгоритма), т.е. как среднее арифметическое расстояний между парами объектов, один из которых входит в первый кластер, а другой - во второй. В конце концов все объекты объединяются вме¬сте, и результат работы алгоритма представляет собой дерево после¬довательных объединений (в терминах теории графов), или «Дендро-грамму». Из нее можно выделить кластеры разными способами. Один подход - исходя из заданного числа кластеров. Другой - из сооб¬ражений предметной области. Третий - исходя из устойчивости (ес-ли разбиение долго не менялось при возрастании порога объединения - значит оно отражает реальность) и т.д.
К алгоритму средней связи естественно сразу добавить алгоритм ближайшего соседа (когда расстоянием между кластерами называ¬ется минимальное из расстояний между парами объектов, один из которых входит в первый кластер, а другой - во второй) и алго¬ритм дальнего соседа (когда расстоянием между кластерами назы¬вается максимальное из расстояний между парами объектов, один из которых входит в первый кластер, а другой - во второй).
Каждый из трех описанных алгоритмов (средней связи, ближай¬шего соседа, дальнего соседа), как легко проверить, порождает бес¬конечное (континуальное) семейство алгоритмов кластер-анализа. Дело в том, что величина d"(x, у), а > О, также является мерой близо¬сти между хиу и порождает новый алгоритм. Если параметр а про¬бегает отрезок, то получается бесконечно много алгоритмов клас¬сификации.
Каким из них пользоваться при обработке данных? Дело ослож¬няется тем, что практически в любом пространстве данных мер бли¬зости различных видов существует весьма много. Именно в связи с обсуждаемой проблемой следует указать на принципиальное разли¬чие между кластер-анализом и задачами группировки.
Если классы реальны, естественны, существуют на самом деле, четко отделены друг от друга, то любой алгоритм кластер-анализа их выделит. Следовательно, в качестве критерия естественности классификации следует рассматривать устойчивость относительно выбора алгоритма кластер-анализа.
Проверить устойчивость можно, применив к данным несколько подходов, например, столь непохожие алгоритмы, как «ближайшего соседа» и «дальнего соседа». Если полученные результаты содержа¬тельно близки, то они адекватны действительности. В противном случае следует предположить, что естественной классификации не существует, задача кластер-анализа не имеет решения, и можно проводить только группировку.
Как уже отмечалось, часто применяется так называемый агломе-ративный иерархический алгоритм «Дендрограмма», в котором вна¬чале все элементы рассматриваются как отдельные кластеры, а за¬тем на каждом шагу объединяются два наиболее близких кластера. Для работы «Дендрограммы» необходимо задать правило вычисле¬ния расстояния между кластерами. Оно вычисляется через расстоя¬ние d(x, у) между элементами х я у. Поскольку d"(x, у) при 0 < а < 1 также расстояние, то, как правило, существует бесконечно много различных вариантов этого алгоритма. Представим себе, что они применяются для обработки одних и тех же реальных данных. Если при всех а получается одинаковое разбиение элементов на класте¬ры, т.е. результат работы алгоритма устойчив по отношению к из¬менению а, то имеем «естественную» классификацию. В противном случае результат зависит от субъективно выбранного исследовате¬лем параметра а, т.е. задача кластер-анализа неразрешима (предпо¬лагаем, что выбор а нельзя специально обосновать). Задача группи-ровки в этой ситуации имеет много решений. Из них можно выбрать одно по дополнительным критериям. Следовательно, получаем эвристический критерий: если решение задачи кластер-анализа существует, то оно находится с помощью лю¬бого алгоритма. Целесообразно использовать наиболее простой. Проблема поиска естественной классификации. Существуют различные точки зрения на эту проблему, например естественная классификация - закон природы; основана на глубоких закономер¬ностях, тогда как искусственная классификация - на неглубоких; для конкретного индивида та, которая наиболее быстро вытекает из его тезауруса; удовлетворяет многим целям; в то время как цель ис¬кусственной классификации задает человек; классификация с точки зрения потребителя продукции; классификация, позволяющая де¬лать прогнозы; имеет критерием устойчивость. Приведенные высказывания дают представление о больших рас-хождениях в понимании «естественной классификации». Этот тер¬мин следует признать нечетким, как и многие другие социально-экономические, научно-технические и пр. Кажущееся рациональ¬ным требование выработать сначала строгие определения, а потом развивать науку - невыполнимо. Следовать ему - значит отвле¬кать силы от реальных задач. При системном подходе к теории классификации становится ясно, что строгие определения можно надеяться получить на последних этапах построения теории. Мы же находимся в начале, поэтому, не давая определения понятиям «есте¬ственная классификация» и «естественная диагностика», обсудим, как проверить на «естественность» классификацию (набор диагно¬стических классов), полученную расчетным путем. Можно выделить два критерия «естественности», по поводу ко¬торых имеется относительное согласие: А. Естественная классификация должна быть реальной, соответст-вующей действительному миру, лишенной внесенного исследо¬вателем субъективизма; Б. Естественная классификация должна быть важной или с науч¬ной точки зрения (давать возможность прогноза, предсказания новых свойств, сжатия информации и т.д.), или с практиче¬ской. Пусть классификация проводится на основе информации об объ¬ектах, представленной в виде матрицы «объект-признак» или мат¬рицы попарных расстояний (мер близости). Пусть алгоритм класси¬фикации дал разбиение на кластеры. Как можно получить доводы в пользу естественности этой классификации? Например, уверенность в том, что она - закон природы, может появиться только в резуль¬тате длительного ее изучения и практического применения. Это со¬ображение относится и к другим из перечисленных выше критериев, в частности к Б (важности). Сосредоточимся на критерии А (реаль¬ности). Понятие «реальности» кластера требует специального обсужде¬ния. Рассмотрим существо различий между понятиями «класси¬фикация» и «группировка». Пусть, к примеру, необходимо деревья, растущие в определенной местности, разбить на группы находя¬щихся рядом друг с другом. Ясна интуитивная разница между не¬сколькими отдельными рощами, далеко отстоящими друг от друга и разделенными полями, и сплошным лесом, разбитым просеками на квадраты с целью лесоустройства. Однако формально определить эту разницу столь же сложно, как определить понятие «куча зерен», чем занимались еще в Древней Греции (одно зерно не составляет кучи, два зерна не составляют кучи,..., если к тому, что не составля¬ет кучи, добавить еще одно зерно, то куча не получится; значит - по принципу математической индукции - никакое количество зе¬рен не составляет кучи; но ясно, что миллиард зерен - большая ку¬ча зерен - подсчитайте объем). Переформулируем сказанное в терминах «кластер-анализа» и «методов группировки». Выделенные с помощью первого подхода кластеры реальны, а потому могут рассматриваться как кандидаты в «естественные». Группировка дает «искусственные» классы, кото¬рые не могут быть «естественными». Выборку из унимодального распределения можно, видимо, рассматривать как «естественный», «реальный» кластер. Применим к ней какой-либо алгоритм классификации («средней связи», «бли¬жайшего соседа» и т.п.). Он даст какое-то разбиение на классы, ко¬торые, разумеется, не являются «реальными», поскольку отражают прежде всего свойства алгоритма, а не исходных данных. Как отли¬чить такую ситуацию от противоположной, когда имеются реальные кластеры и алгоритм классификации более или менее точно их вы¬деляет? Как известно, «критерий истины - практика», но слишком много времени необходимо для применения подобного критерия. Поэтому представляет интерес критерий, оценивающий «реаль¬ность» выделяемых с помощью алгоритма классификации кластеров одновременно с его применением. Такой показатель существует - это критерий устойчивости. Ус-тойчивость - понятие широкое. В частно¬сти, поскольку значения признаков всегда измеряются с погрешно¬стями, то «реальное» разбиение должно быть устойчиво (т.е. не ме¬няться или меняться слабо) при малых отклонениях исходных данных. Алгоритмов классификации существует бесконечно много, и «реальное» разбиение должно быть устойчиво по отношению к переходу к другому алгоритму. Другими словами, если «реальное» разбиение на диагностические классы возможно, то оно находится с помощью любого алгоритма автоматической классификация. Сле-довательно, критерием естественности классификации может слу¬жить совпадение результатов работы двух достаточно различаю¬щихся алгоритмов, например «ближайшего соседа» и «дальнего соседа». Мы рассмотрели два типа «глобальных» критериев «естественно¬сти классификации», касающихся разбиения в целом. «Локальны»» критерии относятся к отдельным кластерам. Простейшая постановка такова: достаточно ли однородны два кластера (две совокупности) для их объединения:? Если объединение возможно, то кластеры не являются «естественными». Преимущество этой постановки в том, что она допускает применение статистических критериев однородно¬сти двух выборок. В одномерном случае (классификация по одному признаку) разработано большое число подобных критериев - Кра-мера-Уэлча, Смирнова, омега-квадрат (Лемана-Розенблатта), Вилкок-сона, Ван-дер-Вардена, Лорда, Стьюдента и др. Имеются крите¬рии и для многомерных данных. Для одного из видов объектов нечисловой природы - люсианов - статистические методы выделе¬ния «реальных» кластеров развиты в работе. Что касается глобальных критериев, то для изучения устойчиво¬сти по отношению к малым отклонениям исходных данных естест¬венно использовать метод статистических испытаний и проводить расчеты по «возмущенным» данным. Некоторые теоретические ут¬верждения, касающиеся влияния «возмущений» на кластеры раз¬личных типов, получены в работе. Опишем практический опыт реализации анализа устойчивости. Несколько алгоритмов классификации были применены к данным, полученным при проведении маркетинга образовательных услуг и приведенным в работе. Для анализа данных были использованы широко известные алгоритмы «ближайшего соседа», «дальнего со¬седа» и алгоритм кластер-анализа из работы. С содержательной точки зрения полученные разбиения отличались мало. Поэтому есть основания считать, что с помощью этих алгоритмов действительно выявлена «реальная» структура данных. Идея устойчивости как критерия «реальности» иногда реализу¬ется неадекватно. Так, для однопараметрических алгоритмов один из специалистов предлагал выделять разбиения, которым соответст¬вуют наибольшие интервалы устойчивости по параметру, т.е. наи¬большие приращения параметра между очередными объединениями кластеров. Для данных работы это предложение не дало полез¬ных результатов - были получены различные разбиения: три алго¬ритма - три разбиения. И с теоретической точки зрения предложе¬ние этого специалиста несостоятельно. Покажем это. Действительно, рассмотрим алгоритм «ближайшего соседа», ис-пользующий меру близости d(x, у), и однопараметрическое семейство алгоритмов с мерой близости cf(x, у), а > 0, также являющихся алгоритмами «ближайшего соседа». Тогда дендрограммы, получен¬ные с помощью этих алгоритмов, совпадают при всех а, поскольку при их реализации происходит лишь сравнение мер близости между объектами. Другими словами, дендрограмма, полученная с помо¬щью алгоритма «ближайшего соседа», является адекватной в поряд¬ковой шкале (измерения меры близости d{x, у)), т.е. сохраняется при любом строго возрастающем преобразовании этой меры. Однако выделенные по обсуждаемому методу «устойчивые раз¬биения» меняются. В частности, при достаточно большом а «наибо¬лее объективным» в соответствии с предложением этого специали-ста будет, как нетрудно показать, разбиение на два кластера. Таким образом, разбиение, выдвинутое им как «устойчивое», на самом де¬ле оказывается весьма неустойчивым.


Скачиваний: 1
Просмотров: 0
Скачать реферат Заказать реферат