Обнаружение ошибок и заполнение пробелов в кубах данных

д.т.н. Загоруйко Николай Григорьевич

2

Обнаружение ошибок

Таблица не имеет пробелов. Требуется обнаружить ошибки или умышленные искажения.

Х1

Х2

…

xj

…

xN

a1

*

*

*

*

*

*

a2

*

*

*

*

*

*

…

*

*

*

*

*

*

ai

*

*

*

* ?

*

*

…

*

*

*

*

*

*

aM

*

*

*

*

*

*

3

Постановка задачи

4

5

Предсказание по похожим объектам

Гипотеза многомерной аналогии: «Объекты, похожие по n свойствам, похожи и по (n+1)-му свойству»

bij ?

Bij/bsj =bi1/bs1 bij=bsj*bi1/bs1 bij – ср. Значение bij

x1

x2

…

xj

…

xN

ai

bi1

bi2

bi…

bi…

biN

as

bs1

bs2

bs…

bsj

bs…

bsN

6

Предсказание по похожим столбцам

Варианты подсказок bji по всем столбцам k усредняются с весом Lk компетентности k столбца

xj

xk

Если есть связь между значениями признаков на m объектах, то такая же связь есть и на (v+1)-м объекте.

a1

bj1

bk1

a2

bj2

bk2

a…

bj…

bk...

Xj bji

* * * * * *

ai

bji

bki

a…

bj…

bk…

aM

bjM

biM

bki xk

7

Формирование компетентной подматрицы (КП)

Использовать только компетентные столбцы и строки Ядро КП – пересечение k наиболее компетентных элементов, выбранных из всей таблицы по каждой координате. AdDel расширение КП – поочередное добавление n1 наиболее компетентных элементов (строк или столбцов), исключение n2 наименее компетентных элементов. Оценка компетентности в пространстве растущей размерности. На каждом шаге оценивается компактность КП

8

Компетентность и компактность

Компетентность FА элемента элемента А **** * * * * * * * *

FА=(r2-r1)/(r2+r1) Остановка, если FА<0

Компактность Q КП = (Q столбцов + Q строк)/2 Q столбцов = среднему значению сходства столбцов КП с целевым столбцом в конкуренции с наиболее компетентным столбцом, не входящим в КП. Q строк =среднему значению сходства строк КП с целевой строкой в конкуренции с наиболее компетентной строкойм, не входящей в КП.

A

r1

r2

9

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

Тот же метод, что и при редактировании. Новая проблема – оценка ожидаемой ошибки. Компактность С компетентной подматрицы Дисперсия ? подсказок Ошибки заполнения известных элементов целевой строки и целевого столбца КП

10

ZET – прогнозирование Алгоритм «Змейка»

Алгоритм FRiS-Pro

2009 г. Международный конкурс по DM. Таблица имела 1962 столбца. Обучающих объектов 2394, контрольных – 2418. Нужно было заполнить 19 344 клеточки. Участвовало 618 команд из 42 стран. Отобрано лучших 49 результатов. Самый слабый результат – до 100 единиц ошибок на клеточку. Лучший - 0.89. FRiS-Pro – 0.95. 4-е место.

1

2

3

4

5

6

7

8

9

10

11

12

?

?

?

3

4

5

6

7

8

9

10

11

12

1

2

3

?

?

?

6

7

8

9

10

11

12

1

2

3

4

5

6

?

?

?

11

Применение ZET

Восстановление скрытых или утерянных данных. Обнаружение ошибок или умышленных искажений (Fraud detection). Обнаружение сбоев в технологическом процессе или в системе измерений. Прогнозирование динамических объектов.

12

ZET на кубах данных

13

Требуется заполнить клеточку на пересечении 3-х «целевых» плоскостей. a0 из A, |A|=M, x0 из X, |X|=N, t0 из T, |T|=T.

x0

А0

t0

14

Формирование компетентного подкуба (КП)

Зародыш КП – пересечение 3-х самых компетентных плоскостей, выбранных их всего куба по каждой координате. AdDel расширение КП – поочередное добавление n1 наиболее компетентных элементов (строк, столбцов или рядов), исключение n2 наименее компетентных элементов. Компетентность плоскостей в постранстве меняющейся размерности.

15

Критерий остановки

1. А – очередная присоединяемая плоскость. R1 – расстояние от А до k соседей из КП R2 –расстояние от А до k соседей среди не входящих в КП. Остановка, если FA=(r2-r1)/(r2+r1)<0, 2. Остановка, если количество плоскостей в КП по каждой координате > n*

16

Ожидаемая ошибка

При заполнении каждого пробела делается редактирование известных клеточек компетентных плоскостей. Полученное среднее значение ошибок является оценкой ожидаемой ошибки заполняемого пробела.

17

Применение 3D-ZET

18

Применение 3D-ZET

19

Редактирование данных о нефтяных скважинах

20

Ошибка редактирования

21

Гистограмма ошибок

22

Решаемые проблемы

Обучение без переобучения Прогнозирование на кубах данных Универсальная программа SDX Таблицы и кубы с разнотипными свойствами Адаптация к большим данным