§2 Алгоритм ZET.

Алгоритм ZET предназначен для прогнозирования и редактирования (проверки) значений в таблицах "объект-свойство". В таких таблицах строки соответствуют рассматриваемым объектам, а столбцы есть значения характеристик, описывающих эти объекты. Таким образом, на пересечение строки с номером "i" и столбца с номером "j", будет находиться значение j-ой характеристики для i-го объекта. Клетку таблицы, расположенную на пересечение i-ой строки и j-го столбца, обозначим символом Aij. Пусть значения Aij неизвестно. Можно достаточно уверенно предсказать это значение, если использовать имеющиеся в таблице закономерности. В реальных таблицах многие столбцы связаны друг с другом. Есть в таблицах и строки, похожие друг на друга по значениям своих характеристик. В алгоритме ZET выявляются такие связи, и на их основе выполняется предсказание искомого значения. Предсказание осуществляется на основе принципа локальной линейности. Это одна из основных идей, позволившая построить эффективный метод и получать хорошие результаты. Она заключается в том, что предсказание выполняется не на всей информации, имеющейся в таблице, а только на той ее части, которая наиболее тесно связана со строкой и столбцом, в которых этот пробел находится. Другими словами, в алгоритме ZET, в отличии от многих других алгоритмов заполнение пробелов, реализуется "локальный" подход к предсказанию каждого пропущенного значения. Для вычисления этого значения строится своя "предсказывающая подматрица", содержащая только имеющую отношение к делу информацию. В подматрицу отбираются в порядке убывания сходства строки, т.е. строки, самые похожие на строку, содержащую интересующий нас пробел, а затем для выбранных строк отбираются также в порядке убывания сходства столбцы "самые похожие" на столбец, содержащий этот пробел.

Предсказание элемента Aij по k-му столбцу Aij(k) делается на основание гипотезы о линейной зависимости между столбцами, при этом сначала вычисляются коэффициенты линейной регрессии Вjk и Сjk ,и по ним находится элемент Aij(k):

Aij(k)=Bjk*Aik+Cjk.

После того, как будут сделаны предсказания Аij(k) по всем р столбцам, не имеющим пропуска в i-ой строке, вычисляется средневзвешенная величина элемента:

Aij(стб)=(Aij(k)*Qkj)/(Qkj)

Вклад каждого столбца (строки) в результат предсказания зависит от их "компетентности" Q, являющейся функцией двух аргументов: "близости" между j-м и k-м столбцами (i-ой и l-ой строками) и "взаимной заполненность" этих столбцов (строк). "Близость" представляет собой степенную функцию модуля коэффициента линейной корреляции (Rkj)а (или (Ril)а). "Взаимная заполненность" k-го и j-го столбцов (Lkj) равна числу непустых пар элементов этих столбцов Alk и Alj для всех l от 1 до m. Отсюда:

Qil=(Ril)a*Lil

Qkj=(Rkj)a*Lkj .

Выбор показателя степени а осуществляется следующим образом, при каждом из последовательных значений а (из некоторого заданного диапазона amin<a<amax) выполняется предсказание всех известных элементов k-го столбца матрицы A(i,j). При каждом a вычисляется расхождение между фактическими и предсказанными значениями. Для предсказания Aij выбирается то из значений a, при котором была получена лучшая средняя точность dj предсказания этих известных значений. Легко увидеть, что, чем больше (Rkj)a, тем с большим весом будут учитываться сведения от самых "похожих" столбцов и тем сильнее будут подавляться подсказки от менее "похожих".

Аналогичная процедура построения формулы и оценки точности вычисления всех элементов i-ой строки выполняется для проверки возможности предсказания Aij как элемента строки.

Aij(стр)=(*Qil)/()

Данные в матрице A(i,j) предварительно нормированы так, чтобы элементы каждого столбца изменялись в пределах от 0 до 1. После получения оценок предсказания по строкам и столбцам сравнивается точность, с которой удалось предсказать известные элементы i-ой строки di и j-го столбца dj. Окончательно для предсказания выбирается либо Aij(стб), либо Aij(стр), в зависимости от того, где точность d оказалась выше. Эта точность рассматривается в качестве ожидаемой ошибки предсказания Aij.

Итак, в алгоритме ZET можно выделить основные этапы:

1. Проводится нормировка столбцов таблицы исходных данных по дисперсиям.

2. Выбирается пробел Aij, находящийся на пересечение i-ой строки и j-го столбца.

3. При определение сходства столбцов производится их предварительная нормировка к интервалу [0,1], и для строк и для столбцов степень сходства определяется на основе евклидова расстояния