Ядерное представление и мера сходства для неполных данных

Основная информация

• ID статьи: 2510.13352
• Название: Kernel Representation and Similarity Measure for Incomplete Data
• Авторы: Yang Cao, Sikun Yang, Kai He, Wenjun Ma, Ming Liu, Yujiu Yang, Jian Weng
• Классификация: cs.LG (Машинное обучение)
• Дата публикации: 15 октября 2024 г. (отправка на arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.13352v1

Аннотация

В данной работе предлагается метод ядра близости (proximity kernel) для решения фундаментальной задачи измерения сходства неполных данных. Традиционные подходы либо отбрасывают неполные данные, либо применяют предварительное заполнение пропусков, что приводит к потере информации и смещению оценок сходства. Ядро близости вычисляет сходство между неполными данными непосредственно в пространстве ядерных признаков без явного заполнения в исходном пространстве. Метод вводит механизм зависящего от данных разбиения на интервалы в сочетании с назначением близости, проецируя данные в высокомерное разреженное представление, адаптирующееся к локальным изменениям плотности. Для обработки пропущенных значений предлагается каскадная стратегия отката для оценки распределения пропущенных признаков. Эксперименты кластеризации на 12 реальных неполных наборах данных показывают, что метод превосходит существующие подходы, сохраняя линейную временную сложность.

Исследовательский контекст и мотивация

Основная проблема

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

Значимость проблемы

1. Повсеместное распространение: В системах рекомендаций пользователи обычно оценивают только небольшое количество товаров, создавая высокоразреженные матрицы пользователь-товар
2. Гетерогенность данных: Пропуски могут одновременно влиять на числовые, категориальные или смешанные признаки
3. Влияние на нижестоящие задачи: Измерение сходства является основой для кластеризации, классификации и обнаружения аномалий; неточные оценки сходства значительно снижают производительность задач

Ограничения существующих методов

1. Методы удаления: Игнорируют пропущенные значения или полностью удаляют неполные образцы, что приводит к серьезной потере информации и смещению
2. Методы заполнения: Используют статистические величины или сложные методы для заполнения пропусков, часто не могут захватить базовое распределение данных и могут вводить искусственные закономерности, не отражающие истинную структуру сходства
3. Методы глубокого обучения: Хотя и перспективны, обычно требуют больших наборов данных и значительных вычислительных ресурсов, не имеют теоретических гарантий и чувствительны к гиперпараметрам

Исследовательская мотивация

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

Основные вклады

1. Предложение метода ядра близости: Проецирование данных в высокомерное разреженное представление через равночастотное разбиение на интервалы и назначение близости на основе диаграмм Вороного, адаптирующееся к локальной плотности без явной оценки плотности
2. Каскадная стратегия отката: Предложение прогрессивной стратегии ослабления ограничений от пересечения к объединению и глобальному априору для обработки пропущенных значений
3. Линейная временная сложность: Достижение линейной временной сложности, позволяющей масштабировать метод на большие наборы данных
4. Экспериментальная проверка: Демонстрация превосходящей производительности на задачах кластеризации на 12 наборах данных

Подробное описание метода

Определение задачи

Дан набор данных D = {x₁, x₂, ..., xₙ} с n образцами, где каждый образец xᵢ ∈ ℝᵈ является d-мерным вектором признаков, который может содержать пропущенные значения (обозначаемые как NaN). Цель состоит в вычислении функции сходства s : D × D → 0,1, количественно определяющей сходство между любыми двумя образцами для использования в нижестоящих задачах, таких как кластеризация.

Архитектура модели

1. Зависящее от данных разбиение на интервалы и назначение близости

Выбор центров интервалов: Для каждого признака j выбираются nᵦᵢₙₛ центров интервалов с использованием равночастотного разбиения:

c_{j,k} = percentile(X_{obs,j}, (k-1)×100/(n_{bins}-1))

где k ∈ {1,2,...,nᵦᵢₙₛ}, Xₒᵦₛ,ⱼ обозначает все наблюдаемые значения признака j.

Механизм назначения близости: Используется назначение близости вместо традиционного членства в интервале:

b_{i,j} = argmin_{k∈{1,...,n_{bins}}} |x_{i,j} - c_{j,k}|

Это создает диаграмму Вороного пространства признаков, где каждый центр cⱼ,ₖ определяет ячейку Вороного.

Свойство адаптации к плотности:

• В плотных областях: расстояния между последовательными центрами малы, создавая маленькие ячейки Вороного; две точки на одинаковом расстоянии более вероятно попадают в разные ячейки
• В разреженных областях: расстояния между последовательными центрами велики, создавая большие ячейки Вороного; две точки на одинаковом расстоянии более вероятно попадают в одну ячейку

2. Построение one-hot кодирования

Для каждого признака j и образца i строится бинарный вектор hᵢ,ⱼ ∈ {0,1}^{n_}:

h_{i,j,k} = {1 если b_{i,j} = k; 0 иначе}

Полное кодирование представляет собой конкатенацию всех признаков: zᵢ = hᵢ,₁, hᵢ,₂, ..., hᵢ,ₐ

3. Каскадная стратегия отката для обработки пропущенных значений

Уровень 1 - Совпадение по пересечению: Поиск образцов, совпадающих по всем наблюдаемым признакам:

S₁(i) = ∩_{j∈O_i} C_{i,j}

где C_{i,j} = {m : m≠i, b_{m,j} = b_{i,j}}

Уровень 2 - Совпадение по объединению: Если S₁(i) = ∅, ослабление до совпадения по любому наблюдаемому признаку:

S₂(i) = ∪_{j∈O_i} C_{i,j}

Уровень 3 - Глобальный априор: Если S₂(i) = ∅, использование глобального распределения:

p_{j,k} = количество образцов в интервале k для признака j / количество образцов с наблюдаемым признаком j

Для каждого уровня используется встраивание среднего ядра (KME) для оценки пропущенного кодирования:

h_{i,j,k} = 1/|S(i)| ∑_{m∈S(i)} h_{m,j,k}

Технические инновации

1. Адаптация к плотности без явной оценки: Комбинация равночастотного разбиения и назначения близости естественным образом реализует адаптивное разбиение, чувствительное к плотности
2. Совместная обработка в пространстве ядра: Обработка пропущенных значений в пространстве представления, а не в исходном пространстве, избегая введения искусственных закономерностей
3. Прогрессивная стратегия совпадения: Критерии совпадения от строгих к мягким максимизируют использование доступной информации

Определение ядра близости

K(x_m, x_n) = 1/d · z_m^T z_n = <z_m, z_n>

Это ядро удовлетворяет условию Мерсера (симметричность и положительная полуопределенность) и имеет вероятностную интерпретацию: вычисляет ожидаемую вероятность того, что два образца попадают в один и тот же интервал по всем признакам.

Экспериментальная установка

Наборы данных

Используются 12 реальных наборов данных из UCI, охватывающих несколько областей:

• Медицинская диагностика: Kidney, Hepatitis, Heart, Tumor, Cancer
• Биологическая классификация: Soybean, Mushroom
• Финансовый анализ: Credit
• Демографическое прогнозирование: Adult
• Политический анализ: Voting
• Прочие: Mammography, Horse

Наборы данных содержат от 155 до 48 842 образцов, размерность от 5 до 35, процент пропусков от 0,15% до 19,39%.

Метрики оценки

Используется нормализованная взаимная информация (NMI) для оценки качества кластеризации; применяется кластеризация K-means с числом кластеров, равным числу истинных классов.

Методы сравнения

9 репрезентативных методов:

1. Простое заполнение: заполнение средним значением
2. Статистические методы: MissForest, MICE, KNN, EM
3. Глубокое обучение: GAIN, MIRACLE, MIWAE
4. Методы ядра: HI-PMK

Детали реализации

• Каждый эксперимент повторяется 10 раз и берется среднее значение
• Гиперпараметры всех базовых методов оптимизируются
• Число интервалов для ядра близости выбирается из {2,3,4,6,8}

Результаты экспериментов

Основные результаты

1. Общая производительность: Достигает лучшей или второй лучшей производительности на 10 из 12 наборов данных, с наивысшим средним NMI (0,4245)
2. Статистическая значимость: Тест Фридмана-Немени показывает, что ядро близости значительно превосходит все другие методы, кроме HI-PMK
3. Стабильность: Диаграммы размаха показывают, что ядро близости не только имеет лучшую среднюю производительность, но и более согласованные результаты на различных наборах данных

Эксперименты по робастности к проценту пропусков

Тестирование на 10%-50% пропусков на наборах данных 3L и Messidor:

• Сохранение стабильного превосходства при низком и среднем проценте пропусков (10%-40%)
• Поддержание разумной производительности при экстремальном проценте пропусков (50%)
• В сравнении KNN и MissForest показывают почти нулевую производительность при 30% пропусков

Анализ масштабируемости

• Временная сложность: O(nd + d·n log n), линейна по числу образцов при фиксированной размерности
• Пространственная сложность: O(nd), линейна по числу образцов и признаков
• Фактическое время выполнения: Значительно быстрее, чем HI-PMK и MIWAE

Анализ чувствительности

При изменении числа интервалов от 2 до 10 на трех наборах данных изменение NMI минимально (например, на наборе Mammo колеблется между 0,30-0,33), что демонстрирует нечувствительность метода к гиперпараметрам.

Связанные работы

Традиционные методы заполнения

• Простое заполнение: Заполнение средним/модой, вычислительно эффективно, но не сохраняет естественную вариативность данных
• KNN заполнение: На основе k наиболее похожих образцов, но плохо работает на высокомерных разреженных данных
• Алгоритм EM: На основе оценки максимального правдоподобия плотности, требует сильных предположений о распределении
• MICE: Создает несколько заполненных наборов данных, вычислительно дорого и требует тщательного задания модели
• MissForest: Использует итеративное заполнение случайным лесом, может переобучаться и не имеет гарантий сходимости

Методы глубокого обучения

• GAIN: Использует генеративные состязательные сети для изучения распределения пропущенных данных
• MIWAE: Использует глубокие модели с латентными переменными для максимизации нижней границы правдоподобия наблюдаемых данных
• MIRACLE: Комбинирует причинный вывод и глубокое обучение для улучшения качества заполнения

Методы ядра

• Традиционные расстояния: Евклидово расстояние не применимо непосредственно к неполным данным
• HI-PMK: Метод ядра, зависящий от данных, но с высокой вычислительной сложностью и чувствительностью к гиперпараметрам

Заключение и обсуждение

Основные выводы

1. Ядро близости успешно реализует прямое вычисление сходства неполных данных в пространстве ядерных признаков, избегая явного заполнения в исходном пространстве
2. Зависящее от данных разбиение на интервалы в сочетании с назначением близости создает представление, адаптирующееся к локальной плотности, без явной оценки плотности
3. Каскадная стратегия отката эффективно использует доступную информацию, постепенно ослабляя критерии от строгого совпадения к глобальному априору
4. Метод достигает превосходящей производительности, сохраняя линейную временную сложность

Ограничения

1. Предположение о механизме пропусков: Текущая оценка в основном основана на механизме MCAR (полностью случайные пропуски); реальные данные часто демонстрируют более сложные паттерны MAR и MNAR
2. Стратегия разбиения: Равночастотное разбиение может быть не оптимальным для всех распределений данных
3. Теоретические гарантии: Отсутствуют теоретические гарантии сходимости каскадной стратегии отката

Направления будущих исследований

1. Исследование поведения метода при механизмах пропусков MAR и MNAR
2. Изучение стратегий адаптивного выбора числа интервалов
3. Установление теоретических гарантий сходимости каскадной стратегии отката
4. Расширение на более сложные типы данных и структуры

Глубокая оценка

Преимущества

1. Инновационность метода: Объединение заполнения и вычисления сходства в пространстве ядерного представления, избегая проблем традиционных двухэтапных методов
2. Теоретическая основа: Предоставление строгого доказательства эффективности ядра, удовлетворяющего условию Мерсера
3. Практичность: Линейная временная сложность делает метод применимым к крупномасштабным приложениям
4. Полнота экспериментов: Всестороннее оценивание на множестве наборов данных, включая проверку статистической значимости
5. Робастность: Нечувствительность к гиперпараметрам, стабильная производительность при различных процентах пропусков

Недостатки

1. Ограничение механизма пропусков: Оценка в основном при предположении MCAR; адаптивность к более сложным паттернам пропусков недостаточно проверена
2. Оценка плотности: Хотя заявляется об отсутствии явной оценки плотности, равночастотное разбиение по сути является неявной оценкой плотности
3. Независимость признаков: Моделирование зависимостей между признаками в каскадной стратегии может быть недостаточным
4. Справедливость сравнения: При сравнении с методами глубокого обучения могут быть различия в вычислительных ресурсах и степени оптимизации

Влияние

1. Академический вклад: Предоставление новой теоретической базы для измерения сходства неполных данных
2. Практическая ценность: Прямое применение в системах рекомендаций, интеллектуальном анализе сетей и других приложениях
3. Воспроизводимость: Предоставление ссылки на код способствует проверке и распространению метода

Сценарии применения

1. Системы рекомендаций: Обработка разреженности матриц пользователь-товар
2. Интеллектуальный анализ сетей: Обработка неполноты данных о поведении пользователей
3. Анализ медицинских данных: Обработка пропущенных значений в клинических данных
4. Обработка больших данных: Линейная сложность подходит для крупномасштабных приложений

Библиография

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

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