Введение: задача обнаружения ошибок
Рассмотрим задачу обнаружения ошибок и заполнения пробелов в таблицах данных. Представьте таблицу, где есть M объектов и N признаков, а на их пересечении стоят некие значения. Таблица полная, но нет уверенности, что все данные верны. Ошибки могут возникать из-за сбоев аппаратуры или неверной перезаписи данных.
Существует много способов проверки правильности таблицы. Можно сравнивать значение в ячейке со средним по столбцу или использовать линейную регрессию, предсказывая значение на основе других столбцов. Однако наша цель — выбрать метод, который минимизирует сумму ошибок между фактическими и предсказанными значениями.
Алгоритм Z и его принципы
Для решения этой задачи был разработан алгоритм Z (и его модификации). Он опирается на два ключевых постулата.
Первый постулат — избыточность. В реальных таблицах есть похожие строки (объекты-«близнецы») и связанные между собой признаки (с высокой корреляцией). Этим можно пользоваться для предсказания.
Второй постулат — локальная компактность. В отличие от ранних подходов, которые анализировали всю таблицу целиком, алгоритм Z учитывает, что закономерности могут действовать лишь на её отдельных участках (би-кластерах). Предсказание должно опираться только на «компетентные» данные, а не на всю выборку.
Из всех видов зависимостей применяются только линейные. Это обосновано тем, что выборка в локальной области обычно мала, и использовать сложные полиномы нет оснований.
Механизм предсказания
В основе предсказания лежит простая гипотеза: объекты, похожие по одним свойствам, похожи и по другим. Если у нас есть похожие строки, то отношения их значений по всем признакам одинаковы. На основе этого можно вычислить значение пропущенной ячейки, усреднив оценки от разных пар объектов. Аналогично работает предсказание по столбцам: строится линейная регрессия по известным значениям признака, и с её помощью восстанавливается пропуск.
Построение компетентной подматрицы
Для реализации принципа локальности алгоритм работает не со всей таблицей, а с её частью — компетентной подматрицей.
- Создание «зародыша»: Для целевых строки и столбца (содержащих пробел) выбираются несколько самых похожих строк и столбцов. Их пересечение образует начальную матрицу.
- Жадное добавление: К матрице по очереди добавляются наиболее похожие строки или столбцы (плоскости), если их добавление улучшает компактность подматрицы. Важно, что сравнение происходит в пространстве уже включенных элементов, а не по всей таблице.
- Проверка и «чистка»: После добавлений проверяется, все ли элементы матрицы действительно полезны. «Слабые» элементы удаляются, после чего жадное добавление возобновляется.
Критерий компетентности. Для оценки нового элемента (например, объекта A) вычисляются два расстояния: до K ближайших соседей внутри текущей подматрицы (R1) и до K ближайших соседей вне неё (R2). Далее используется функция конкурентного сходства: (R1 - R2) / (R1 + R2). Если результат больше нуля, объект A больше похож на «своих», и его можно добавить. Если меньше — добавление разрушит структуру.
Остановка происходит, когда ни по строкам, ни по столбцам не находится претендентов, удовлетворяющих проверке. Компетентность всей подматрицы оценивается как среднее от компетентности входящих в неё столбцов и строк.
Оценка ожидаемой ошибки
Прямо оценить ошибку для заполненного пробела невозможно. Поэтому используются косвенные оценки. Один из способов — редактирование известных элементов в «кресте» (целевой строке и столбце). Мы предсказываем известные значения тем же методом, вычисляем среднюю ошибку предсказания и переносим эту оценку на заполняемый пробел. Это позволяет сказать заказчику, например: «Ошибка заполнения может достигать плюс-минус 5%. Устраивает ли вас это?».
Применение для прогнозирования
Алгоритм Z применим и для прогнозирования. Он основан на предположениях о постоянстве (например, цикличности) или монотонности процессов.
Пример: прогнозирование временных рядов. Для предсказания значений на будущий квартал данные сдвигаются так, чтобы известные периоды совпали с неизвестными. На основе этой таблицы с пробелами алгоритм предсказывает пустые ячейки. Ошибка прогноза быстро растет («раструб») с удалением от известных данных, поэтому надежные прогнозы возможны лишь на ближайшие шаги.
Практические задачи:
- Прогнозирование урожайности зерновых по данным на середину лета.
- Прогнозирование надоев молока (с 1946 года). Была замечена связь точек минимума надоя со сменой правительства.
- Прогнозирование падежа скота в Якутии.
Пример успеха: соревнование по прогнозированию
В 2009 году на конференции по интеллектуальному анализу данных (Data Mining) в Германии было проведено соревнование. Задача: предсказать продажи 8 авторов в ~2000 книжных магазинах на основе данных за прошлый год. Исходная матрица содержала много пробелов, нужно было заполнить около 20 000 пустых клеточек. Мы применили упрощенную версию алгоритма Z (используя сходство только по строкам). В соревновании участвовало более 600 команд, до финиша дошло 230. Наш результат оказался четвертым в списке из 49 лучших. Ошибка победителя составляла 0,89 книги на клеточку, наша — 0,95. Для сравнения, у 49-й команды ошибка была более 100 книг на клеточку. Это подтвердило эффективность подхода.
Работа с кубами данных
Подход был обобщен для кубов данных (объекты, свойства, время). Пробел находится на пересечении трех измерений. Философия та же:
- Формируется «зародыш» — небольшой кубик (например, 4x4x4) из целевых плоскостей и самых похожих на них.
- Жадно добавляются новые плоскости по каждой из трех координат (объекты, признаки, время). Сравниваются лучшие претенденты по каждой координате, и добавляется тот, кто дает наибольшее улучшение.
- Проводится «чистка» слабых плоскостей.
- Критерий остановки — как и в двумерном случае (отрицательное конкурентное сходство) или достижение порога. На практике оптимальный размер подкуба — 6-7 плоскостей по каждой координате.
Примеры применения:
- Анализ данных спортсменов: Куб 10x10x10 (10 спортсменов, 10 характеристик, 10 моментов времени). Цель — поиск выбросов. Средняя ошибка при перекрестной проверке составила 14%, что на грани инженерной точности. Важный результат: анализ частоты попадания плоскостей в компетентный подкуб позволил выявить наиболее информативные характеристики. Характеристики, которые никогда не включались, можно не измерять в будущем.
- Анализ нефтяных скважин: Куб 13 (скважин) x 11 (характеристик) x 122 (дня). Задача — прогноз дебита скважин. Общая ошибка редактирования составила 2.24%, что хорошо. График фактического и предсказанного дебита практически совпадал.
Открытые проблемы
В настоящее время мы работаем над следующими проблемами:
- Обучение без переобучения. Есть вариант решения, но он неэлегантен, ведется поиск более изящного.
- Прогнозирование на кубах данных. Идея понятна, но еще не реализована и не апробирована.
- Универсальная программа SDX. Уже есть программа, которая объединяет решение задач распознавания, восстановления пропусков и (в перспективе) кластеризации с выбором признаков. Сочетание кластеризации с выбором признаков — сложная проблема.
- Таблицы с разнотипными свойствами. Теоретически задача решена, но нет надежных рабочих программ.
- Адаптация к большим данным (Big Data). Алгоритмы (особенно Z) громоздки и не оптимизированы для больших объемов. Интересно, что 40 лет назад мы уже решали задачу «больших данных» для машины M20 (память на 4 096 чисел). Тогда мы использовали алгоритм Форель для кластеризации данных по частям: исходные данные разбивались на небольшие шары, для них запоминались центры и число объектов, а затем происходила вторичная кластеризация этих центров. Сейчас мы собираем эвристики для ускорения работы наших алгоритмов с большими данными.
Краткие итоги
Представленный материал описывает целостный подход к анализу табличных и многомерных данных, где центральной проблемой является их неполнота или недостоверность. В основе лежит эмпирическое наблюдение о природе реальных данных: информация в них избыточна, а закономерности часто носят не глобальный, а локальный характер. Игнорирование этой локальности — общий недостаток многих классических методов, пытающихся строить единую модель для всего набора данных. Такой подход неизбежно терпит неудачу, когда в данных существуют группы объектов со своими уникальными, но устойчивыми связями.
Практическая ценность предложенного метода заключается в его способности адаптироваться к структуре данных. Отказ от глобальных моделей в пользу динамически формируемой «компетентной» области вокруг каждой конкретной задачи (будь то ячейка с ошибкой или пробел) позволяет более точно улавливать релевантные зависимости и отсекать информационный шум. Это особенно важно при решении задач восстановления данных, где ключевым становится не только само предсказанное значение, но и оценка его надежности. Возможность сообщить заказчику границы ожидаемой ошибки — принципиальный шаг от простого «угадывания» к инженерному подходу с измеримым качеством результата.
Методология демонстрирует свою работоспособность не только на синтетических примерах, но и в реальных, коммерчески значимых сценариях — от прогнозирования урожайности до анализа работы нефтяных скважин. Успех в международном соревновании по прогнозированию продаж подтверждает, что даже упрощенная версия алгоритма конкурентоспособна на фоне специализированных решений. Это говорит о мощности базовых принципов, заложенных в основу.
Однако очевиден и естественный предел развития. Опора на линейные зависимости оправдана на малых выборках, но ограничивает применимость. Более серьезным вызовом является масштабируемость. Вычислительная сложность жадного перебора и поиска соседей делает прямое применение метода к действительно большим данным проблематичным. Проблема адаптации к Big Data — это не просто техническая задача ускорения кода. Она требует переосмысления архитектуры алгоритма, возможно, через переход к иерархическим или распределенным вычислениям, как это показано в примере с алгоритмом «Форель». История показывает, что «большие данные» — понятие относительное, но вычислительная эффективность всегда была и остается ключевым фактором, определяющим, будет ли метод востребован на практике или останется лишь теоретическим изысканием.
