Задача получения данных (data mining problem)

Выборкой называется конечное множество S = {s₁,…,s_m} строк над алфавитом S и целевое условие на S – двоичная функция С: S®{0,1}. Каждая строка s_i Î S называется документом, C(s_i) – его метка. Документ s_i положительный(позитивный) если C(s_i) = 1 и отрицательный (негативный) в противном случае. Пусть a - некоторая метка. Обозначим за Sa множество {sÎS | C(s) = a}. Для подмножеств T множества S, мы определим count(P,T) как число документов s Î T удовлетворяющих образцу P.

Первая рассматриваемая проблема – максимизация доверия (confidence maximization) [10]. Для образца P определим поддержку P как supp_s(P) = count(P,S₁)/card(S) и доверие P как conf_s(P) = count(P,S₁)/count(P,S). Минимальная поддержка – действительное число 0£s£1. Образец P считают s-частым если supp_s(P) ³ s.

Определение 1. Задача оптимизации доверия образца (Optimized Confidence Pattern Problem). Дана пятерка объектов (S, S, C, k, s) – алфавит S, выборка S, целевое условие C на S, константы k³0 и 0£s£1. Задача состоит в нахождении s-частого образца зависимых k-близких слов P, который максимизирует conf_s(P).

Другими словами, задача оптимизации доверия образца состоит в нахождении значений образца P®C с наивысшей условной вероятностью среди тех правил, которые удовлетворяют по крайней мере s процентам документов в S. В 3-ем и 4-ом разделе приводятся эффективные алгоритмы для решения этой задачи.

Вторая проблема – рассмотрение минимизации эмпирической ошибки [17,20]. Пусiть S – выборка, С – целевое условие на S, P - образец зависимых k-близких слов над алфавитом S. Определим P(s)Î{0,1} равным единице, если P удовлетворяет строке s. Эмпирическая ошибка образца P относительно S и С есть число документов из S неклассифицированных по P (misclassified by P), то есть, error_s,c(P) = S_sÎS|P(s)-C(s)|.

Определение 2. Задача минимизации эмпирической ошибки.

Дана четверка объектов (S, S, C, k) – алфавит S, выборка S, целевое условие на S, константа k³0. Задача состоит в нахождении образца зависимых k-близких слов P, который минимизирует error_s,c(P).

Как мы увидим в разделе 5, задача минимизации эмпирической ошибки имеет близкое отношение к задачи распознавания в зашумленных средах.

Суффиксные деревья

Суффиксные деревья – структура данных для хранения всех подслов данного текста в очень экономном виде (McCreight [24]). Пусть A = a₁a₂…a_n-1$ текст длины n. Мы примем, что текст всегда заканчивается специальным символом $ÏS отличным от символов алфавита. Для каждого 1£p£n обозначим суффикс, начинающийся в позиции p как A_p= a_p…a_n-1$.

Тогда суффиксное дерево для текста A – в точности компактный луч (compact trie) для всех суффиксов(suffices) A, полученный из луча (trie) для A последовательным удалением внутренних вершин с только одним ребенком и слиянием меток удаленных ребер.

Более точно, суффиксное дерево для A – корневое дерево Tree_A, которое удовлетворяет следующим условиям.

(i) Каждое ребро помечено подсловом a  из А, которое кодируется парой (p,q) позиций вхождения a в строку A, то есть A[p]A[p+1]…A[q] = a.

(ii) Метки любых двух ребер исходящих из одной и той же вершины не могут начинаться с одной и той же буквы.

(iii) Каждая вершина v представляет собой строку Word(v) полученную конкатенацией меток на пути от корня до вершины v.

(iv) i-ый лист (1£i£n) l_i представляет собой суффикс ранга i в лексикографически отсортированном списке всех суффиксов A.

Пусть a - подслово A. Локус (местоположение) a в дереве Tree_A, обозначаемый как Locus(a), есть уникальная вершина v дерева Tree_A, такая что a - префикс строки Word(v) и Word(w) – подходящий префикс a, где w – предок вершины v.

Из свойств (iv) и (iii), дерево Tree_A имеет в точности n листьев и максимум n-1 внутренних вершин. Таким образом, из свойства (i) требуется O(n) пространства памяти, представляющее O(n²) подслов A. Кроме того, McCreight (1976) нашел изящный алгоритм, который строит дерево Tree_A за линейное время с линейным объемом памяти. Известно, что средняя высота суффиксного дерева для строки длины n есть O(log n) [7]. Это также верно для случая генетических последовательностей.

Региональный поиск

Пусть n – положительное целое число. Имеется конечный набор точек X с целочисленными координатами на двумерной плоскости [1..n]x[1..n]. Процедура регионального поиска должна найти все точки из множества X, лежащие в заданном прямоугольнике [x1..x2]x[y1..y2].

Было предложено несколько решений этой задачи, и среди них мы принимаем метод, описанный в Preparata и Shamos [27] для простоты, хотя это - не оптимум по времени вычисления. Их решение использует структуру данных, называемую региональное дерево (orthogonal range tree), требующее O(m log m) памяти, O(m log m) операций предобработки и O(log²m) операций поиска, где m – число точек в X. Для алгоритма в 4-ом разделе, мы расширяем эту структуру для поиска в суффиксном дереве.

Алгоритм

В этом разделе мы покажем, существование эффективного алгоритма который вычисляет оптимизированный образец за время O(mn² log(n)²), при затратах памяти O(kmn log n), используя такие структуры данных, как суффиксные деревья и деревья регионального поиска. Затем, в следующем разделе, мы покажем, что региональные запросы можно осуществлять прямо на суффиксном дереве, вместо регионального дерева. Это дает более быстрый алгоритм для задачи оптимизации доверия образца.

Ниже дан алгоритм Find_Optimal, который находит оптимизированные образцы. Ключевыми в алгоритме являются шаги перечисления образцов в канонической форме и быстрое вычисление supp(P) и conf(P). Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца.

Procedure Find_Optimal;

Вход: Выборка S = {s₁,…,s_m}, целевое условие C, близость k ³ 0 и Минимальная поддержка 0£s£1.

Выход: Оптимизированные образцы (a, k, b) в канонической форме.

Используемые структуры: приоритетная очередь Q.

Begin

1 Q := Æ;

2 A := s₁$s₂…$s_m$ и вычислить doc;

3 Построитьсуффиксное дерево Tree_A и суффиксные массивы suf, pos.

4 Вычислить Diag_k и Rank_k из A.

5 for (каждой вершины v дерева Tree_A) do вычислить I(v);

6 for (каждой вершины v дерева Tree_A) do

7 for (каждой вершины u дерева Tree_A) do

8 P := (Word(u), k, Word(v));

9 Вычислить count(P,S₁) и count(P,S₀) путем выполнения

10 регионального запроса I(u) x I(v) для Rank_k.

11 Вычислить supp(P) и conf(P);

12 If (supp(P) ³ s) then добавить P в приоритетную очередь Q с ключом conf(P);

13 end for;

14 end for;

15 Вывести все оптимизированные образцы из Q.

End proc.