Классификация задач. Функция конкурентного сходства

Введение: задачи анализа данных

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

Протоколы наблюдений обычно имеют форму таблиц. Это либо двумерные таблицы «объекты–свойства», либо трехмерные таблицы «объекты–свойства–время» (кубы данных). Трехмерные данные становятся особенно востребованными, поскольку потоки информации о множестве объектов с большим числом характеристик поступают непрерывно во времени.

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

Основные типы задач

Задача редактирования

Рассматривается плоская таблица, где строки — объекты, столбцы — описывающие признаки, а последний столбец — целевая характеристика (классификация). Например, описывающие характеристики — показатели пациента, целевой столбец — диагноз «болен» или «здоров».

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

Такие задачи актуальны для обнаружения мошенничества (fraud detection). Например, в задачах для Госплана РФ методы указывали области, где отчетные данные противоречат закономерностям: завышенная или заниженная урожайность при имеющихся площадях, качестве почв и количестве удобрений.

Задача распознавания образов

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

Задача кластеризации

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

Промежуточный случай

Часть объектов верифицирована (класс известен), большая часть — нет. Классификация всех объектов должна опираться на известные факты и не противоречить им, но одновременно руководствоваться критериями компактности, как при кластеризации.

Выбор признаков

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

Заполнение пробелов

В реальных таблицах много пустых клеток, разбросанных по всей таблице. В историях болезни у разных пациентов измерены разные наборы симптомов. Встречались геологические задачи, где 82% клеток протокола были пустыми. Заполнение пробелов и поиск ошибок — отдельный класс алгоритмов заполнения эмпирических таблиц.

Комбинированные задачи

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

Задача SDX — самая сложная: одновременное формирование кластеризации, построение правил распознавания кластеров в информативном подпространстве признаков и выбор признаков. Практическая потребность в таких задачах породила направление Data Mining (интеллектуальный анализ данных): заказчик с большим объемом данных просит разложить их по группам, определить важные признаки и научить отличать одну группу от другой.

Нерешенные задачи

Цензурирование — удаление из обучающей выборки шумящих объектов (выбросов), порожденных сбоями аппаратуры или ошибками записи, с сохранением «ядра» выборки.

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

Проблема разнообразия методов

В 2007 году опубликована статья об онтологии Data Mining, описывающая структуру этой области. Существует огромное разнообразие алгоритмов — «пышное дерево» методов. Однако это признак слабости: по выражению академика Велихова, такое разрастание — «не мускулатура, а раковая опухоль».

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

Отечественные школы внесли значительный вклад в развитие области:

• Алгебраический подход — школа Ю. И. Журавлёва и К. В. Рудакова (Вычислительный центр, Москва)
• Статистический подход — С. А. Айвазян и ученики школы Колмогорова
• Метод опорных векторов — работы Вапника и Червоненкиса
• Эвристический подход — А. Г. Ивахненко (Киев), также Б. Г. Миркин, Ю. А. Воронин, А. С. Дорофеюк

Проблема традиционных мер сходства

Традиционные меры сходства между объектами A и B зависят только от этих двух объектов и ни от чего другого. В литературе описано более сорока таких мер. Однако человеческое восприятие сходства устроено иначе.

Мысленный эксперимент

Ситуация 1. Два шарика на расстоянии R. Похожи ли они настолько, чтобы объединить их в один класс? Ответа нет: одному кажется — похожи, другому — нет.

Ситуация 2. Шарики A и B на том же расстоянии R, но рядом с B появился близкий объект C. Можно ли объединить A и B? Скорее нет: логичнее объединить B и C, а A отдельно.

Ситуация 3. A и B на том же расстоянии R, но объект C находится на большом удалении. Похожи ли теперь A и B? Да, их можно объединить.

Вывод: ответ о сходстве зависит от ответа на вопрос «по сравнению с чем?». Фраза «всё познаётся в сравнении» — фундаментальный закон природы. В классификации решение должно приниматься не по абсолютному значению расстояния, а по относительной оценке в контексте.

Функция конкурентного сходства (FRiS-функция)

Рассмотрим задачу: средний шарик находится между левым и правым, нужно решить, к какому из них его присоединить. Измеряются два расстояния: R₁ — до первого шарика, R₂ — до второго.

Формула FRiS-функции:

Функция принимает значения от +1 до −1:

• F = +1 — контрольный объект полностью совпадает с первым объектом (R₁ = 0)
• F = −1 — контрольный объект совпадает со вторым объектом (максимальная непохожесть на первый)
• F = 0 — объект находится посередине, принадлежность не определена

Функция конкурентного сходства — относительная мера сходства, используемая во всех алгоритмах авторов.

Исторические аналоги относительной меры

Относительная мера не является полностью новым изобретением. Ранее она использовалась в различных формах:

• Правило Байеса — решение принимается по отношению вероятностей двух гипотез: объект относится к классу A, если вероятность принадлежности к A больше вероятности принадлежности к B. Учитывается не только расстояние до одного класса, но и конкуренция с другим.
• Метод k ближайших соседей (k-NN) — контрольный объект сравнивается с соседями первого и второго образа; вычисляются средние расстояния до каждого образа, и объект относится к тому, где расстояние меньше.
• Алгоритм ReliefF — использует количественную меру: (R₂ − R₁) / D, где D — диаметр обучающей выборки. Недостаток: диаметр может быть большим, а интерес представляет локальная ситуация вокруг распознаваемого объекта.
• Ширина профиля (silhouette width) — числитель тот же, знаменатель — максимум из R₁ и R₂. Недостаток: нормировка непредсказуема.

Преимущество FRiS-функции: знаменатель (R₁ + R₂) обеспечивает нормировку относительно локальной ситуации. Результаты при использовании ширины профиля близки к результатам FRiS, однако наработанные алгоритмы ориентированы на FRiS. Замена одного блока меры сходства на другой принципиально не меняет работу алгоритмов.

Краткие итоги

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

Сначала очерчивается спектр задач: от проверки уже имеющихся классификаций до формирования новых групп и восстановления пропусков. Каждая из них по отдельности имеет развитый инструментарий, однако именно это многообразие методов становится симптомом глубинной проблемы. Разрозненность алгоритмов, каждый из которых настроен на частный случай, отражает отсутствие единого основания. Авторская диагностика указывает на ключевой источник этого разнообразия — способы измерения сходства между объектами.

Традиционные меры сравнивают пару объектов изолированно, игнорируя окружение. Мысленный эксперимент с шариками наглядно показывает несостоятельность такого подхода: один и тот же пространственный интервал воспринимается по-разному в зависимости от наличия поблизости других объектов. Отсюда следует принципиальный вывод: оценка сходства должна быть не абсолютной, а относительной, учитывающей конкуренцию альтернатив. Это соответствует и естественному человеческому восприятию, и логике статистических решений, где гипотезы всегда сравниваются друг с другом.

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

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