Принципы кластеризации образцов

Введение
Проблема распознавания образов давно привлекает внимание психологов, физиологов, инженеров и математиков. В последние годы интерес к данной теме значительно вырос, так как во многих областях науки и техники остро ощущалась необходимость этого решения. Это связано с разработкой большого количества различных устройств (роботов, технических и медицинских диагностических систем, персональных, мобильных и карманных компьютеров), автоматическая работа которых невозможна без распознавания текущего состояния объектов, процессов, явлений и состояния, с которыми работают эти устройства.
Создание устройств, выполняющих функции распознавания различных объектов, во многих случаях открывает возможность замены человека как элемента сложной системы, специализированным автоматом. Такая замена может значительно расширить возможности различных систем, выполняющих сложные информационно-логические задачи. В то же время заменяющий его автомат действует одинаково и всегда обеспечивает одинаковое качество, если он работает.
Большинство современных прикладных задач, решаемых с помощью систем распознавания образов, характеризуются большим объемом исходных данных и возможностью добавлять новые данные уже в процессе работы систем.
В настоящее время основным научным направлением является исследование и разработка алгоритмов и методов построения программного обеспечения интеллектуального анализа данных. Актуальность данной темы определяется наличием ряда важных прикладных задач, решение которых требует анализа больших объемов разнородных, комплексно организованных данных. В то же время объем и сложность организации таких данных часто не позволяют эффективно использовать традиционные инструменты анализа, основанные на методах статистического анализа, поиска информации и экспертных знаний, что определяет необходимость использования интеллектуального анализа данных на основе машин. методы обучения и искусственного интеллекта. Объемы данных настолько впечатляют, что человек просто не может позволить себе анализировать их самостоятельно, хотя необходимость такого анализа совершенно очевидна, поскольку эти «необработанные данные» содержат знания, которые можно использовать при принятии решений.
Именно поэтому принципы кластеризации и фильтрации данных является актуальной научно-технической задачей, требующей разработки современных подходов к ее решению.
Кластеризация информации
Кластеризация (или кластерный анализ) - это задача разбиения несколько объектов на группы, называемые кластерами [2]. Внутри каждой группы должны быть «похожие» объекты, а объекты разных групп должны быть как можно более разными. Основное различие между кластеризацией и классификацией состоит в том, что список групп четко не определен и определяется во время работы алгоритма.
 
Формально задача кластеризации заключается в следующем [5]. Пусть у нас имеется множество объектов, множество номеров (имена, метки) кластеров. Так же задана функция расстояния между объектами. Имеется конечная обучающая выборка объектов. Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике, а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера. [1]
Применение кластерного анализа в целом сводится к следующим этапам:
1. Выбор объектов для кластеризации.
2. Определение набора переменных, по которым будут оцениваться объекты в выборке. При необходимости нормализуйте значения переменных.
3. Расчет значений меры сходства между объектами.
4. Применение метода кластерного анализа для создания групп похожих объектов (кластеров).
5. Представление результатов анализа.
После получения и анализа результатов можно настроить выбранную метрику и метод кластеризации для получения оптимального результата.
Алгоритмы кластеризации могут быть классифицированы в соответствии с методами следующим образом [5]:
- Иерархический подход (направление «снизу-вверх» или «сверху вниз»)

. Результатом иерархического алгоритма является дендограмма (иерархия), которая позволяет разбить исходный набор объектов на любое количество кластеров.
Два самых популярных алгоритма создают разделение снизу-вверх: Single-link на каждом шаге объединяет два кластера с наименьшим расстоянием между любыми двумя представителями, и Complete-link - между двумя самыми удаленными представителями. Наиболее популярным иерархическим алгоритмом с направлением сверху вниз является алгоритм минимального связующего дерева, который, в свою очередь, является представителем семейства алгоритмов для поиска кратчайшего пути в графе.
- вероятностный подход. Предполагается, что каждый рассматриваемый объект принадлежит к одному из k классов. Наиболее известным представителем является алгоритм k-means.
- Подходы на основе систем искусственного интеллекта. Наиболее известным представителем является алгоритм С-means.
Цели кластеризации
• Понимание данных путем определения структуры кластера. Разделение выборки на группы похожих объектов позволяет упростить дальнейшую обработку данных и принятие решений, применяя различные методы анализа к каждому кластеру (стратегия «разделяй и властвуй»).
• Сжатие данных. Если исходная выборка слишком велика, ее можно уменьшить, оставив одного из наиболее типичных представителей каждого кластера.
• Обнаружение новизны (англ. novelty detection). Выбираются нетипичные объекты, которые нельзя прикрепить ни к одному из кластеров.
В первом случае пытаются уменьшить количество кластеров. Во втором случае более важно обеспечить высокую степень сходства объектов в каждом кластере, и может быть как можно больше кластеров. В третьем случае наибольший интерес представляют отдельные объекты, которые не вписываются ни в один из кластеров.
Во всех этих случаях может применяться иерархическая кластеризация, когда большие кластеры делятся на более мелкие, которые, в свою очередь, делятся еще меньше и т. д. Такие задачи называются проблемами таксономии.
Результатом таксономии является древовидная иерархическая структура. Более того, каждый объект характеризуется перечислением всех кластеров, к которым он принадлежит, обычно от большого до малого. [3]
Классическим примером таксономии, основанной на сходстве, является биномиальная номенклатура живых существ, предложенная Карлом Линнеем в середине 18-го века. Подобные систематизации строятся во многих областях знаний, чтобы организовать информацию по большому количеству объектов.
Классификация алгоритмов
- иерархические и плоские. Иерархические алгоритмы (также называемые алгоритмами таксономии) строят не один раздел выборки на непересекающиеся кластеры, а систему вложенных разделов. Таким образом, на выходе мы получаем дерево кластеров, корнем которого является вся выборка, а листьями являются самые маленькие кластеры.
Плоские алгоритмы строят одно разбиение объектов на кластеры.
- Четкие и нечеткие. Четкие (или непересекающиеся) алгоритмы связывают номер кластера с каждым образцом объекта, то есть каждый объект принадлежит только одному кластеру. Нечеткие (или пересекающиеся) алгоритмы связывают с каждым объектом набор действительных значений, которые показывают степень отношения объекта к кластерам. То есть каждый объект принадлежит каждому кластеру с некоторой вероятностью.
Принципы кластеризации
Идея синтеза систем автоматического распознавания основана на методах, которыми классы изображений описываются и разделяются.
Когда класс характеризуется списком его членов, построение системы распознавания образов может основываться на принципе принадлежности к этому списку