.
.
Портал искусственного интеллекта
.
.
.
.
.
 
Карта сайта Портал искусственного интеллекта  -  Каталог статей  -  Автоматическая классификация  -  Методы классификации  
 


Нашли ошибку?

Нашли ошибку?

Нет ничего проще: выделите текст с ошибкой, нажмите CTRL+ENTER и мы уже знаем о ней!

Партнерство

Хотите стать партнером?

Присылайте свои предложения и мы обязательно рассмотрим их

Написать нам

Есть интересная информация?

Пишите нам и мы разместим ее на страницах портала искусственного интеллекта

Методы классификации

Методы классификации, можно разделить на несколько групп. По способу задания показателя качества классификации методы делятся на эвристические и оптимизационные. По способу объединения – на дивизимные, агломеративные и итеративные.
Методы классификации
Эвристические алгоритмы основаны на опыте и интуиции человека. Показатель качества классификации, который необходимо обратить в экстремум, в этих алгоритмах в явном виде не задан. Эвристические алгоритмы реализуют процедуры, обладающие рациональным смыслом с точки зрения логики человека и приводящие во многих случаях к хорошим результатам на практике. К таким алгоритмам относятся, например, алгоритмы «Граф», «Спектр», «Форель».
К оптимизационным алгоритмам относятся методы классификации, в которых в явном виде задан показатель качества, который необходимо обратить в экстремум (максимум или минимум) по множеству допустимых разбиений. В отличие от алгоритмов первой группы, разбиения, получаемые оптимизационными алгоритмами классификации, являются наилучшими с точки зрения выбранного показателя качества. Выбор конкретного показателя зависит от специфики и ограничений решаемой задачи, а также принятых предложений. Следует отметить, что во многих случаях в эвристических алгоритмах показатель качества задан в неявном виде и они могут стать оптимизационными, если удается его формализовать и сформулировать в явном виде.
В общем случае в любом оптимизационном алгоритме классификации можно выделить следующие элементы:
  • показатель качества классификации;
  • ограничения;
  • механизм поиска результирующего разбиения.
Ограничения в методах классификации в основном касаются типа исходных данных – множества допустимых разбиений, на котором ищется результирующее разбиение, и вида самого результирующего разбиения. Поиск результирующего разбиения осуществляется в соответствии с некоторым механизмом оптимизации. Это может быть механизм полного или частичного перебора, случайного перебора и т. д. Если механизм не обеспечивает точного достижения экстремума показателя качества, он является приближенным, а ошибка оценивается величиной отклонения достигаемого значения показателя качества от оптимума. Если величина ошибки незначительна, алгоритм является субоптимальным (близким к оптимальному).
Конкретизация перечисленных элементов приводит к тому или иному методу классификации. Оптимизационные методы классификации могут быть основаны на кластерном анализе.
Кластерный анализ – это совокупность методов, позволяющих классифицировать многомерные наблюдения, каждое из которых описывается набором исходных переменных x_{1}~,~x_{2}~,~...~,~x_{m}. В отличие от комбинационных группировок кластерный анализ приводит к разбиению на группы с учетом всех группировочных признаков одновременно.
Например, если каждый наблюдаемый объект характеризуется двумя признаками p_{1} и p_{2}, то при выполнении комбинационной группировки вся совокупность объектов будет разбита на группы по p_{1}, а затем внутри каждой выделенной группы будут образованы подгруппы по p_{2}. Такой подход получил название монотетического. Определить принадлежность каждого объекта к той или иной группе можно, последовательно сравнивая его значения p_{1} и p_{2} с границами выделенных групп. Образование группы в этом случае всегда связано с указанием ее границ по каждому группировочному признаку отдельно.
В методах классификации, основанных на кластерном анализе, используется иной принцип образования групп, так называемый политетический подход. Все группировочные признаки одновременно участвуют в группировке, т. е. они учитываются все сразу при отнесении наблюдения в ту или иную группу. При этом, как правило, не указаны четкие границы каждой группы, а также неизвестно заранее, сколько же групп целесообразно выделить в исследуемой совокупности.
Кластерные методы классификации важное место занимают в тех отраслях науки, которые связаны с изучением массовых явлений и процессов. Необходимость развития методов кластерного анализа и их использования продиктована прежде всего тем, что они помогают построить научно обоснованные классификации, выявить внутренние связи между единицами наблюдаемой совокупности.
Методы кластерного анализа позволяют решать следующие задачи:
  • проведение классификации объектов с учетом признаков, отражающих сущность, природу объектов. Решение такой задачи, как правило, приводит к углублению знаний о совокупности классифицируемых объектов;
  • проверка выдвигаемых предположений о наличии некоторой структуры в изучаемой совокупности объектов, т.е. поиск существующей структуры;
  • построение новых классификаций для слабоизученных явлений, когда необходимо установить наличие связей внутри совокупности и попытаться привнести в нее структуру;
  • сжатие данных – если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.
Агломеративные методы последовательно объединяют отдельные объекты в группы (кластеры), а дивизимные методы расчленяют группы на отдельные объекты. В свою очередь каждый метод классификации как объединяющего, так и разделяющего типа может быть реализован при помощи различных алгоритмов. Следует заметить, что как агломеративные, так и дивизимные алгоритмы трудоемки и их сложно использовать для больших совокупностей. Кроме того, результаты работы таких алгоритмов (их графическое изображение) трудно поддаются визуальному анализу.
В кластерном анализе существуют также методы классификации, которые трудно отнести к первой или ко второй группе – итеративные методы – кластеры формируются исходя из задаваемых условий разбиения, которые могут быть изменены пользователем для достижения желаемого качества. К итеративным методам относятся, например, метод k-средних, метод поиска сгущений и другие. Итеративные методы относятся к быстродействующим, что позволяет использовать их для обработки больших массивов исходной информации.
В отличие от агломеративных и дивизимных методов классификации итеративные алгоритмы могут привести к образованию пересекающихся кластеров, когда один объект может одновременно принадлежать нескольким кластерам.
Если алгоритм кластеризации основан на измерении сходства между переменными, то в качестве мер сходства могут быть использованы:
  • линейные коэффициенты корреляции;
  • коэффициенты ранговой корреляции;
  • коэффициенты контингенции и т.д.
В заключении отметим, что из всех кластерных методов классификации самыми распространенными являются иерархические агломеративные методы. Сущность этих методов заключается в том, что на первом шаге каждый объект выборки рассматривается как отдельный кластер. Процесс объединения кластеров происходит последовательно: на основании матрицы расстояний или матрицы сходства объединяются наиболее близкие объекты. Если матрица сходства первоначально имеет размерность (m~*~m), то полностью процесс кластеризации завершается за (m~-~1) шагов, в итоге все объекты будут объединены в один кластер. Последовательность объединения легко поддается геометрической интерпретации и может быть представлена в виде графа-дерева (дендрограммы). На дендрограмме указываются номера объединяемых объектов и расстояние (или иная мера сходства), при котором произошло объединение.

п»ї
 
.
Статистика посещений
.
. . .
.