Почему BIDE использует полу-максимальный период для сокращения пространства поиска?

Question

Согласно статье, которая определяет BIDE:

BIDE: эффективный майнинг частых замкнутых последовательностей

Теорема 2 (обрезка пространства поиска BackScan):

Пусть префиксная последовательность будет n-последовательностью, Sp=e1e2...en, Если ∃i(1≤i≤n) и существует пункт e′ который появляется в каждом из i-го полумаксимальных периодов префикса Sp в SDBмы можем смело прекратить растущий префикс Sp,

Доказательство:

Потому что пункт e′ появляется в каждом из i-го полумаксимального периода префикса Sp в SDBмы можем получить новый префикс S′p=e1e2...ei−1e′ei...en(1<i≤n) или же S′p=e′e1e2...en(i=1)и оба (Sp ‎⊂ S′p) а также (supSDB(Sp)=supSDB(S′p)) держать. Любой местный частый предмет e′′ WRT префикс Sp также часто встречается на местном уровне S′p, в это время (〈Sp,e′′〉⊂〈S′p,e′′〉) а также (supSDB(〈Sp,e′′〉)=supSDB(〈S′p,e′′〉)) держать. Это означает, что нет надежды на майнинг частых закрытых последовательностей с префиксом Sp,

Я понимаю, что, например, если у меня есть AB шаблон, и я нахожу e', например C, который находится во 2-м максимальном периоде паттерна, поэтому между A а также B для каждой последовательности, которая содержит ABтогда я могу перестать расти ABпотому что я мог бы использовать обратное расширение, чтобы сделать ACB, который будет иметь такую ​​же поддержку, но это дольше. Таким образом, любой шаблон, который я получил бы, расширяя AB вперед, конечно, не будет закрытой моделью, потому что C отсутствует в нем. Вот почему я должен перестать расти AB и подождите пока PrefixSpan вырастет A -> AC -> ACB с передним выдвижением. Что я не понимаю, почему максимальный период должен быть ограничен полумаксимальным периодом в этом контексте и почему тестирование на полумаксимальный период в порядке. Статья не пишет реального объяснения. Любая идея? Можете ли вы написать пример, где мы теряем закрытые частые паттерны, используя максимальный период вместо полу-максимального периода?

Answer 1

Я думаю, что получил ответ. Вот пример, в котором есть новые события в максимальном периоде, но не в полу-максимальном периоде:

[AxByB,AqBtyB], AB
2nd max period: [xBy,qBty] -> By
2nd semi-max period: [x,q] -> 0

В соответствии с этим я не могу перестать расти AB, потому что нет e' в полумакс периоде с той же поддержкой. С другой стороны, есть e' в максимальный период с той же поддержкой, чтобы мы могли достичь A{By}B шаблон с обратным расширением от AB, Но я обнаружил, что мы можем достичь AB{yB} с выдвижением вперед от AB тоже. С большим количеством совпадений, например, такими шаблонами, как ABAB мы получим такой же вывод; мы можем вырастить начальный AB с продлением вперед в AB{*A*B}, но мы не можем добавить любой символ к полу макс периоду A{*}Bпотому что мы не можем достичь этого с помощью прямого AB и PrefixSpan увеличивает шаблон только с прямым расширением. Так, например, если мы найдем x во 2-м полумакс периоде AB с той же поддержкой, то мы должны перестать расти AB и ждите, пока PrefixSpan будет расти AxB в A -> Ax -> AxB путь, и продолжать расти AxB шаблон, а не AB шаблон. Ofc. здесь мы ищем закрытые частые шаблоны, а не частые, поэтому мы можем безопасно сократить пространство поиска таким образом. Я не уверен, возможно ли разработать алгоритм частого анализа паттернов, который выполняет как прямое, так и обратное расширение. Возможно, позже я попытаюсь разработать такой алгоритм только для вызова, но сейчас BIDE - это то, что я делаю.