7.4.3. Автоматическая классификация неполных данных.

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

Опишем алгоритм МДС автоматической классификации совокупности объектов характеризуемой неполной матрицей данных. Большим достоинством подхода МДС к этой задаче является то, что он не требует предварительного восстановления пропущенных значений и максимально использует специфику разбиения совокупности объектов на классы по принципу минимального дистанционного разбиения, порожденного набором ядер.

Выберем некоторое число (неважно какое) в качестве метки пропущенного значения. Поставим в соответствие объекту , пару где — диагональная -матрица, Диагональный элемент матрицы равен 1, если известно значение признака, а в противном случае. Координата вектора ) равна значению признака, если и равна метке в противном случае.

Введем в евклидову метрику при помощи некоторой положительно определенной симметрической матрицы М (М-метрику).

Квадратом псевдорасстояния от пары до произвольной точки называется

Непосредственно из определения следует, что значение псевдорасстояния не зависит от выбранного значения метки, поэтому можно говорить о псевдорасстоянии от объекта до точки

Пусть — некоторая весовая функция (положительная нормированная мера) на исследуемой совокупности объектов

Выберем некоторый класс . Выражение естественно назвать псевдоразбросом класса относительно точки а точку

— псевдоцентром тяжести класса

Пусть — единичная матрица и S совпадает со всей совокупностью объектов Положим Тогда псевдоцентр тяжести вычисляется по формуле:

В общем случае нетрудно показать [106], что если каждый из признаков наблюдается по крайней мере на одном из объектов класса то матрица

является положительно определенной и псевдоцентр тяжести класса однозначно вычисляется по формуле:

Возвращаясь к общей схеме алгоритмов классификации МДС, получаем, что если в качестве меры сходства взять псевдорасстояние, а в качестве центра класса — псевдоцентр, то можно непосредственно перенести на случай неполных данных алгоритмы метода центра тяжести и метода адаптивных квадратичных расстояний, изложенные в п. 7.4.2. При реализации этих алгоритмов необходимо только предусмотреть коррекцию на тех шагах алгоритма, когда встречается класс, для которого существует хотя бы один признак, ненаблюдаемый у всех элементов этого класса. Продемонстрируем такую коррекцию на примере алгоритма -средних параллельного типа для неполных данных.

Поставим в соответствие исследуемой совокупности объектов набор где — вектор диагональных элементов матрицы (см. выше). В для простоты фиксируем стандартное евклидово расстояние и будем считать, что точки имеют одинаковые веса.

Тогда меру сходства между объектом и точкой можно записать в виде

Схема алгоритма

1. Выберем начальный набор центров

2. Пусть на шаге построен набор центров . Построим минимальное дистанционное разбиение совокупности объектов, используя псевдорасстояние .

3. Для каждого класса вычислим вектор где Построим набор центров где

4. Если хотя бы для одного t, то переходим к 2, заменив m на в противном случае заканчиваем работу алгоритма.