Презентацию к лекции 7 Вы можете скачать здесь.
Введение: Функция конкурентного сходства
После общего введения в когнитивный анализ данных мы переходим к детальному рассмотрению функции конкурентного сходства (FRiS-функции). Рассмотрим ее вычисление в задаче распознавания.
Представим объекты в пространстве признаков, принадлежащие к двум классам. Например, это могут быть здоровые и больные люди, качественные и бракованные изделия, заемщики с хорошей и плохой кредитной историей. Для оценки сходства нового объекта с этими классами мы вычисляем расстояния до каждого из них. Затем, на основе этих расстояний, рассчитывается количественная величина конкурентного сходства.
Ключевое свойство этой величины — её нормированность: она изменяется от –1 до +1. Значение 0 означает, что объект одинаково похож (или не похож) на оба класса. На основе этой, казалось бы, простой гипотезы, был разработан целый ряд алгоритмов для решения различных задач: таксономии (FRiS-Tax), построения решающего правила (FRiS-Stolp), выбора информативной системы признаков, прогнозирования, заполнения пробелов и других.
Задача распознавания (Обучение с учителем)
В задаче распознавания целевой признак (имя класса) известен для части объектов — обучающей выборки. Существует множество подходов к ее решению, каждый из которых основан на определенной модели или гипотезе. Проблема в том, что алгоритм, хороший в рамках одной модели, может плохо работать, если реальные данные этой модели не соответствуют. Цель — найти модель, подходящую для как можно большего числа реальных задач.
Классификация подходов к распознаванию:
- Статистические: Предполагают, что объекты — это реализации случайных величин. Задача сводится к восстановлению плотностей распределения. В параметрических подходах тип распределения задан, и оцениваются его параметры. В непараметрических подходах плотность оценивается по локальным окрестностям точек.
- Эвристические:
- Основанные на сходстве: Гипотеза: похожие объекты принадлежат к одному классу. Сюда относятся метод ближайших соседей, метод потенциальных функций и методы отбора эталонных объектов.
- Основанные на разделимости: Строят границу между классами в пространстве признаков. Примеры: линейный дискриминант Фишера, метод опорных векторов (SVM).
- Основанные на логических закономерностях: Используются для разнотипных признаков, где трудно ввести метрику.
- Нейросетевые: Стоят несколько особняком.
Подход на основе функции конкурентного сходства использует идею отбора эталонных объектов, которые будем называть «столпами». Такой подход перспективен для больших данных (Big Data), так как позволяет принимать решения на основе небольшого числа отобранных наиболее важных объектов, а не всей выборки.
Столпы должны обладать двумя свойствами: их количество должно быть небольшим, и они должны быть наиболее представительными, то есть важными для описания выборки и точного расположения границы между классами. Набор столпов также позволяет оценить компактность выборки — характеристику, помогающую выбирать наиболее информативные признаки.
Распознавание нового объекта происходит по правилу ближайшего соседа: объект относится к тому классу, к которому принадлежит ближайший к нему столп.
Количество столпов может варьироваться в зависимости от сложности задачи:
- Для простых, хорошо разделимых классов достаточно по одному столпу на класс.
- Для сложных, пересекающихся распределений количество столпов увеличивается.
- В крайне сложных случаях, когда почти каждый объект становится столпом, гипотеза вырождается, и используется понятие локальной компактности.
Таким образом, выбор числа столпов — это автоматический подбор гипотезы, наиболее адекватной сложности решаемой задачи.
Алгоритм FRiS-Stolp
Работа алгоритма состоит из этапов:
- Выбор базового множества: Находится по одному наилучшему столпу для каждого класса. При оценке качества кандидата предполагается, что его класс описывается только им одним, а конкурирующий класс — всеми своими объектами.
- Наращивание системы столпов: Процесс продолжается до достижения условия остановки. Одним из условий может быть достижение заданной точности распознавания обучающей выборки, но оно ведет к переобучению — модель хорошо работает на обучающих данных, но плохо на новых. Более целесообразный подход — ограничить число столпов долей от объема выборки (например, 10%). Это позволяет избежать построения слишком сложного правила.
Оценка качества объекта как столпа
Качество объекта A как столпа для своего класса складывается из двух компонентов:
- Защищающая способность (Defensive ability): Насколько хорошо A «защищает» объекты своего класса. Для каждого объекта своего класса расстояние до ближайшего «своего» столпа приравнивается к расстоянию до A, а расстояние до «чужого» — к ближайшему объекту противоположного класса. Затем вычисляется средняя функция конкурентного сходства.
- Толерантность (Tolerance): Насколько A не мешает правильному распознаванию объектов чужого класса. Здесь, наоборот, A рассматривается как потенциальный «чужой» столп для объектов противоположного класса.
Общее качество — это баланс между защищающей способностью и толерантностью. Алгоритм выбирает объект с наилучшим сочетанием этих двух характеристик. Процесс повторяется итеративно: после добавления каждого нового столпа система пересматривается, и уже существующие столпы могут быть перемещены для более точного описания выборки.
Задача таксономии (Обучение без учителя)
В отличие от распознавания, в задаче таксономии правильные ответы (имена классов) отсутствуют в принципе. Наша цель — самостоятельно обнаружить или «навести» классовую структуру в данных.
Зачем это нужно?
Таксономия упрощает анализ больших объемов данных. Вместо анализа тысяч объектов можно рассматривать небольшое количество кластеров или их типичных представителей. Пример: сотовая компания хочет разработать несколько тарифных планов. Для этого ей нужно сначала выделить группы пользователей со схожим поведением (звонки, SMS, интернет), а затем для каждой группы создать свой тариф.
Как измерить сходство?
Ключевой вопрос — как измерять сходство между объектами. Для этого используется функция конкурентного сходства. Методы таксономии можно классифицировать по разным признакам. По типу разделения они делятся на иерархические (дают целую иерархию разбиений) и неиерархические (дают одно разбиение, например, алгоритм k-means). По базовой гипотезе их можно разделить на вероятностные (предполагают, что данные — это смесь распределений) и геометрические (основываются на вычислении расстояний).
Алгоритм FRiS-Tax относится к геометрическим. Он использует функцию конкурентного сходства и критерий похожести объектов на столп — типичного представителя таксона.
Алгоритм FRiS-Tax
В задаче таксономии нет заранее известных «своих» и «чужих». Чтобы применить функцию конкурентного сходства, вводится понятие виртуального конкурента. Считается, что на некотором фиксированном расстоянии R* от каждого объекта всегда находится «чужой». Это позволяет заменить расстояние до ближайшего конкурента на константу R* и вычислить конкурентное сходство.
Работа алгоритма FRiS-Tax состоит из двух этапов:
- FRiS-Cluster: Формируется множество столпов. Каждый столп порождает кластер, и эти кластеры линейно разделимы. Процесс итеративный: на каждом шаге выбирается лучший кандидат в столпы, после чего уже существующие столпы могут быть перемещены для оптимизации общей картины.
- FRiS-Class: Линейно разделимые кластеры объединяются в классы более сложной формы. Кластеры объединяются, если на границе между ними есть объекты, и их распределение аналогично распределению внутри кластеров. Если граница пуста, кластеры остаются разделенными.
Выбор количества кластеров — нетривиальная задача. В алгоритме FRiS-Tax используется анализ кривой качества (например, компактности) в зависимости от количества столпов. Ищутся локальные экстремумы на этой кривой, которые соответствуют оптимальным вариантам таксономии. Такой подход позволяет найти решение, согласующееся с интуицией эксперта, даже для сложных структур данных (например, «кольцо и центр»).
Задача частичного обучения
Это промежуточный случай между распознаванием и таксономией. У нас есть выборка, где для части объектов имена классов известны, а для части — нет. Часто информации о классифицированных объектах может быть недостаточно для построения хорошего решающего правила. В таких случаях ценность представляет и неразмеченная выборка, содержащая информацию о структуре данных.
Основные подходы:
- Статистические: Основаны на восстановлении смеси распределений, активно используют EM-алгоритм.
- Co-training: Использует две независимые системы описания объектов для взаимного обучения.
- Графовые методы: Опираются на классифицированные объекты как на «опору». Пример: алгоритм таксономических решающих функций.
- Метод опорных векторов (SVM): Один из популярных методов, также адаптированный для этой задачи.
Обобщенная классификация
Задачи распознавания, таксономии и частичного обучения похожи. Возникает идея создать единый алгоритм для решения всех трех задач. Такой подход называется обобщенной классификацией.
Требования к решению:
- Геометрическая компактность: Объекты в одном кластере похожи, в разных — нет.
- Одноклассовая однородность: Если в один кластер попали классифицированные объекты, они должны принадлежать одному классу.
Схема работы алгоритма обобщенной классификации аналогична предыдущим: пошаговое наращивание системы столпов. Ключевой момент — вычисление функции конкурентного сходства для смешанной выборки.
Для объекта из классифицированной части выборки поиск «своего» ведется среди объектов его класса и всех неразмеченных объектов. Это оправдано, так как в силу локальной компактности вероятность того, что неразмеченный объект, находящийся очень близко, является «чужим», мала. Поиск «чужого» ведется среди объектов противоположного класса. Если ближайший конкурент находится среди неразмеченных объектов, вводится виртуальный конкурент для компенсации неопределенности.
Эффективность частичного обучения иллюстрируется примером: когда обучающая выборка очень мала, использование неразмеченных данных позволяет провести границу между классами значительно точнее, чем если бы мы опирались только на размеченные данные.
Преимущество остановки по локальному экстремуму:
Использование локального максимума функции конкурентного сходства в качестве критерия остановки позволяет получить дополнительную информацию о структуре данных. На примере видно, что в данных есть два четко выраженных кластера, не содержащих ни одного классифицированного объекта. Это знание позволяет либо запросить у эксперта дополнительную информацию именно по этим кластерам, либо предположить, что они представляют собой новый, третий класс. Таким образом, алгоритм помогает не только строить модели, но и обнаруживать «белые пятна» в знаниях о данных.
Заключение
Функция конкурентного сходства оказалась универсальным инструментом. На ее основе можно формулировать и решать задачи трех типов: распознавания, таксономии и частичного обучения. Единый алгоритм, автоматически подстраиваясь под условия задачи, способен строить качественные решения, оперируя небольшим количеством информативных объектов — «столпов».
Краткие итоги
Анализ представленного материала демонстрирует, что в основе эффективного решения широкого круга задач анализа данных лежит не столько сложность математического аппарата, сколько выбор адекватной базовой гипотезы. Гипотеза конкурентного сходства, при всей своей внешней простоте, оказалась чрезвычайно продуктивной. Ее ключевое преимущество — в отсутствии жестких ограничений на природу данных, что позволяет применять ее в ситуациях, где другие модели могут быть неадекватны. Это прагматичный подход, ставящий во главу угла адаптивность.
Центральная идея, проходящая через все рассмотренные задачи, — редукция сложности через выделение эталонных объектов («столпов»). Этот принцип позволяет не только резко снизить вычислительные затраты, что критически важно при работе с большими данными, но и автоматически подобрать модель нужной сложности. Количество столпов становится регулятором: простые задачи требуют простых моделей, сложные — более детализированных. Это изящный способ избежать как недообучения, так и переобучения, находя баланс между точностью и обобщающей способностью.
Особую ценность представляет переход от отдельных алгоритмов к единой концепции обобщенной классификации. Способность одного и того же инструмента работать в режимах обучения с учителем, без учителя и частичного обучения имеет важное практическое значение. В реальных проектах данные часто бывают гетерогенными: какая-то часть размечена, какая-то нет. Идея о том, что неразмеченные данные — это не «второсортная» информация, а ценный источник сведений о структуре предметной области, может существенно повысить качество моделей там, где получение разметки затруднено или дорого. Более того, предложенный метод не просто использует эти данные, но и позволяет выявлять в них новые, неизвестные ранее закономерности или классы, что превращает процесс анализа из пассивного моделирования в активное исследование данных.
В конечном счете, сила подхода заключается в его целостности. Он предлагает не разрозненный набор инструментов, а единую методологию, в которой выбор «столпов» служит универсальным механизмом для понимания и описания структуры данных, независимо от степени их изученности. Это открывает путь к созданию более гибких, масштабируемых и интеллектуальных систем анализа.
Введение
Функция конкурентного сходства (FRiS-функция) — это нормированная мера (от –1 до 1), показывающая, насколько объект похож на один класс относительно другого. Она вычисляется на основе расстояний до объектов классов. Эта простая гипотеза оказалась универсальной для решения множества задач анализа данных.
1. Задача распознавания (Обучение с учителем)
Здесь имена классов известны. Ключевая идея подхода — отбор эталонных объектов («столпов») — небольшого числа наиболее представительных объектов, заменяющих всю выборку. Это критически важно для больших данных (Big Data).
Классы алгоритмов распознавания:
- Статистические: Восстанавливают распределения (параметрические и непараметрические).
- Эвристические: Делятся на основанные на сходстве, на разделимости (граница между классами) и на логических закономерностях.
- Нейросетевые.
Алгоритм FRiS-Stolp наращивает систему «столпов». Критерием остановки служит не точность на обучающей выборке (ведет к переобучению), а лимит на количество столпов (например, 10% от выборки). Количество столпов — это регулятор сложности: простые задачи требуют 1–2 столпа, сложные — больше.
Качество объекта как столпа оценивается балансом защищающей способности (как хорошо защищает своих) и толерантности (как мало мешает чужим).
2. Задача таксономии (Обучение без учителя)
Здесь имен классов нет. Цель — найти структуру в данных. Так как «своих» и «чужих» нет, вводится понятие виртуального конкурента, который находится на фиксированном расстоянии R* от каждого объекта.
Алгоритм FRiS-Tax работает в два этапа:
- FRiS-Cluster: Строит линейно разделимые кластеры вокруг «столпов».
- FRiS-Class: Объединяет кластеры в классы сложной формы, если на их границе есть объекты.
Оптимальное число кластеров определяется по локальным экстремумам на кривой качества таксономии.
3. Задача частичного обучения
Здесь часть данных размечена, часть — нет. Использование неразмеченных данных помогает строить более качественные модели, так как они несут информацию о структуре данных, которой нет в малой размеченной выборке.
4. Обобщенная классификация
Единый алгоритм решает все три задачи. Требования: геометрическая компактность и одноклассовая однородность.
Для вычисления FRiS-функции в смешанной выборке:
- «Свой» ищется среди объектов своего класса и всех неразмеченных.
- «Чужой» ищется среди объектов противоположного класса. Если ближайший «чужой» неразмечен, используется виртуальный конкурент.
Преимущество остановки на локальном экстремуме: алгоритм может выявить кластеры, не содержащие размеченных объектов, сигнализируя о возможном новом классе или пробеле в знаниях.
Заключение
FRiS-функция позволяет построить универсальный, адаптивный подход к анализу данных, основанный на отборе «столпов» и решающий задачи с любой степенью размеченности данных.
1. Функция конкурентного сходства — нормированная мера, оценивающая сходство объекта с одним классом относительно другого.
2. Малые допущения гипотезы конкурентного сходства делают ее применимой к широкому кругу задач анализа данных.
3. Отбор эталонных объектов («столпов») позволяет снизить вычислительную сложность и повысить интерпретируемость модели.
4. Количество «столпов» в модели является регулятором ее сложности, автоматически подстраиваясь под задачу.
5. Остановка по достижении точности на обучающей выборке ведет к переобучению, в отличие от остановки по лимиту числа «столпов».
6. Качество объекта как «столпа» определяется балансом его защищающей способности и толерантности.
7. Для применения функции конкурентного сходства в таксономии вводится понятие виртуального конкурента.
8. Алгоритм FRiS-Tax строит сначала линейно разделимые кластеры, а затем объединяет их в классы произвольной формы.
9. Оптимальное число таксонов можно определить по локальным экстремумам кривой качества таксономии.
10. Неразмеченные данные несут ценную информацию о структуре классов и могут значительно улучшить качество модели.
11. Единый алгоритм обобщенной классификации способен решать задачи распознавания, таксономии и частичного обучения.
12. Остановка на локальном экстремуме позволяет выявлять не описанные классами сгустки данных, что является сигналом для дополнительного анализа.
1. Каков диапазон значений функции конкурентного сходства и что означает каждое из крайних и нулевое значение?
2. В чем принципиальное различие между статистическими и эвристическими подходами к распознаванию?
3. Почему подход на основе отбора эталонных объектов перспективен для больших данных?
4. Как количество «столпов» связано со сложностью решаемой задачи распознавания?
5. Почему критерий остановки по 100% точности на обучающей выборке считается неудачным?
6. Из каких двух компонентов складывается качество объекта как «столпа» и что они характеризуют?
7. Как в задаче таксономии можно вычислить функцию конкурентного сходства, если изначально нет «своих» и «чужих»?
8. В чем состоит назначение этапа FRiS-Class в алгоритме FRiS-Tax?
9. Как определяется оптимальное количество кластеров в алгоритме FRiS-Tax?
10. Почему в задаче частичного обучения выгодно использовать неразмеченные данные?
11. Каким двум основным требованиям должно удовлетворять решение задачи обобщенной классификации?
12. Какую дополнительную информацию о структуре данных можно получить, если остановить наращивание «столпов» на локальном экстремуме?
