Первая рассматриваемая проблема – максимизация доверия (confidence maximization) [10]. Для образца P определим поддержку P как supps(P) = count(P,S1)/card(S) и доверие P как confs(P) = count(P,S1)/count(P,S). Минимальная поддержка – действительное число 0£s£1. Образец P считают s-частым если supps(P) ³ s.
Определение 1. Задача оптимизации доверия образца (Optimized Confidence Pattern Problem). Дана пятерка объектов (S, S, C, k, s) – алфавит S, выборка S, целевое условие C на S, константы k³0 и 0£s£1. Задача состоит в нахождении s-частого образца зависимых k-близких слов P, который максимизирует confs(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), то есть, errors,c(P) = SsÎS|P(s)-C(s)|.
Определение 2. Задача минимизации эмпирической ошибки.
Дана четверка объектов (S, S, C, k) – алфавит S, выборка S, целевое условие на S, константа k³0. Задача состоит в нахождении образца зависимых k-близких слов P, который минимизирует errors,c(P).
Как мы увидим в разделе 5, задача минимизации эмпирической ошибки имеет близкое отношение к задачи распознавания в зашумленных средах.
Суффиксные деревья – структура данных для хранения всех подслов данного текста в очень экономном виде (McCreight [24]). Пусть A = a1a2…an-1$ текст длины n. Мы примем, что текст всегда заканчивается специальным символом $ÏS отличным от символов алфавита. Для каждого 1£p£n обозначим суффикс, начинающийся в позиции p как Ap= ap…an-1$.
Тогда суффиксное дерево для текста A – в точности компактный луч (compact trie) для всех суффиксов(suffices) A, полученный из луча (trie) для A последовательным удалением внутренних вершин с только одним ребенком и слиянием меток удаленных ребер.
Более точно, суффиксное дерево для A – корневое дерево TreeA, которое удовлетворяет следующим условиям.
(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) li представляет собой суффикс ранга i в лексикографически отсортированном списке всех суффиксов A.
Пусть a - подслово A. Локус (местоположение) a в дереве TreeA, обозначаемый как Locus(a), есть уникальная вершина v дерева TreeA, такая что a - префикс строки Word(v) и Word(w) – подходящий префикс a, где w – предок вершины v.
Из свойств (iv) и (iii), дерево TreeA имеет в точности n листьев и максимум n-1 внутренних вершин. Таким образом, из свойства (i) требуется O(n) пространства памяти, представляющее O(n2) подслов A. Кроме того, McCreight (1976) нашел изящный алгоритм, который строит дерево TreeA за линейное время с линейным объемом памяти. Известно, что средняя высота суффиксного дерева для строки длины 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(log2m) операций поиска, где m – число точек в X. Для алгоритма в 4-ом разделе, мы расширяем эту структуру для поиска в суффиксном дереве.
В этом разделе мы покажем, существование эффективного алгоритма который вычисляет оптимизированный образец за время O(mn2 log(n)2), при затратах памяти O(kmn log n), используя такие структуры данных, как суффиксные деревья и деревья регионального поиска. Затем, в следующем разделе, мы покажем, что региональные запросы можно осуществлять прямо на суффиксном дереве, вместо регионального дерева. Это дает более быстрый алгоритм для задачи оптимизации доверия образца.
Ниже дан алгоритм Find_Optimal, который находит оптимизированные образцы. Ключевыми в алгоритме являются шаги перечисления образцов в канонической форме и быстрое вычисление supp(P) и conf(P). Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца.
Procedure Find_Optimal;
Вход: Выборка S = {s1,…,sm}, целевое условие C, близость k ³ 0 и Минимальная поддержка 0£s£1.
Выход: Оптимизированные образцы (a, k, b) в канонической форме.
Используемые структуры: приоритетная очередь Q.
begin
1 Q := Æ;
2 A := s1$s2…$sm$ и вычислить doc;
3 Построить суффиксное дерево TreeA и суффиксные массивы suf, pos.
4 Вычислить Diagk и Rankk из A.
5 for (каждой вершины v дерева TreeA) do вычислить I(v);
6 for (каждой вершины v дерева TreeA) do
7 for (каждой вершины u дерева TreeA) do
8 P := (Word(u), k, Word(v));
9 Вычислить count(P,S1) и count(P,S0) путем выполнения
10 регионального запроса I(u) x I(v) для Rankk.
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.
3.1 Перечисление образцов в канонической форме с использованием суффиксного дерева
Пусть $ Ï S, такой что $ ¹ $. Возьмем в качестве входных данных S = {s1,…,sm} и С ® {0,1}. Наш алгоритм строит текст A := s1$s2…$sm$, называемый входным текстом, путем конкатенации всех документов из S, разделенных символом $. Пусть n = |A|. Для каждого 1£p£n определим doc(p) = i, если i-ый текст si включает p. Без потери общности, примем что существует некоторое 1£p£m, такое что С(si) = 1 для всех 1£i£p, С(si) = 0 для всех p<i£m.
Далее, мы строим суффиксное дерево TreeA для входного текста за линейное время [24]. Это дерево изоморфно обобщенному суффиксному дереву (generalized suffix tree, GST), являющегося компактным лучом (compacted trie) для всех суффиксов документов из S, кроме меток ребер направленных к листьям. Затем, для каждого листа мы переопределяем Word(v) как наибольший префикс суффикса, представленного вершиной v, не содержащий символов $. Это фактически стандартный метод построения GST за линейное время [3].
Введем отношение эквивалентности ºA следующим образом. Для строк a, b, a ºA b если OccA(a)=OccA(b) (совпадают местонахождения). Для образцов зависимых k-близких слов P=(a1, k, a2), Q=(b1, k, b2), P ºA Q, если a1 ºA b1 и a2 ºA b2. Если P ºA Q, тогда говорят, что P и Q эквивалентны.
Лемма 1. Эквивалентные образцы дают одинаковые значения для suppS(P) и confS(P).
Доказательство. По определению, эквивалентные шаблоны P, Q имеют то же самое множество местонахождений (occurrences) для любого текста A. Таким образом count(P,T) = count(Q,T) для любого подмножества T Í S. Из того, что suppS(P) и confS(P) определены через count, следует утверждение. ÿ
Образец считают находящимся в канонической форме, если он имеет форму (Word(u), k, Word(v)), для некоторых вершин u, v дерева TreeA. По определению, число образцов зависимых k-близких слов O(n2). Пусть ^S Î S - произвольная строка длины max{|s| | sÎS} + 1. Очевидно, что Ds, x(^S) = 0.
Лемма 2. Для любого образца зависимых k-близких слов P, если P удовлетворяет документу из S, тогда существует эквивалентный ему образец в канонической форме.
Доказательство. Пусть P=(a, k, b). Для любой подстроки A a, существует вершина w дерева TreeA, такая что a ºAWord(w). Предположим, что мы имеем неуплотненный суффиксный луч (uncompacted suffix trie) TreeA. Тогда существует вершина v дерева TreeA, которая представляет a. Пусть w – самый высокий потомок v, который имеет, по меньшей мере, двух детей. Теперь, отобразим вершины TreeA в те TreeA, стандартным способом (we map the nodes in TreeA into those in TreeA in a standard way). Теперь, легко видеть, что v и w отобразились в те же самые ребра в компактном варианте TreeA. Мы знаем, что поддерево(v) и поддерево(w) имеют одинаковое множество листьев и, таким образом, мы имеем одинаковое множество местонахождений (occurrences) в A. Поскольку w = Locus(a) в TreeA, мы имеем Word(w) ºA a. Следовательно, получаем утверждение леммы. ÿ
Лемма 3. Для любого оптимального образца из образцов зависимых k-близких слов найдется эквивалентный образец P, который является либо каноническим либо ^S.