Discovering Most Classificatory Patterns for
Very Expressive Pattern Classes
Masayuki Takeda1,2, Shunsuke Inenaga3,
Hideo Bannai4, Ayumi Shinohara1,2,and Setsuo Arikawa1
1Department of Informatics, Kyushu University

2Japan Science Technology Corporation Agency

3Department of Computer Science, University of Helsinki
4Human Genome Center, University of Tokyo

Background and Motivation
Distinguish two given string datasets- to obtain a good rule and/or useful knowledge

Grade up BONSAI system- so that it can deal with more expressive patternclasses

Machine Discovery System BONSAI
Datasets

Positive
ExamplesNegativeExamples

BONSAI
posPOSneg[Shimozono et. al 1994]

NEG

ABCDEFGHIJKLMNOPQRSTUVWXY
0011001010001110000011010

Indexing
I(pos)I(neg)

Decision Tree
Generator

I(POS)

I(NEG)

Combinatorial
Optimization
Algorithm

Accuracy
Evaluation

x 11 yPx 101 y

PIndexing

Decision Tree AccuracyN

x 111 yN

Pattern Discovery from Datasets
Find a pattern string that occurs in all strings of A
and in no strings of B.

AB

AKEBONO MUSASHIMARU

WAKANOHANA TAKANOHANACONTRIBUTIONS OF AICONTRIBUTIONS OF UN

BEYOND MESSY LEARNINGTRADITIONAL APPROACHESBASED ON LOCAL SEARCH ALGORITHMSGENETIC ALGORITHMS

BOOLEAN CLASSIFICATIONPROBABILISTIC RULE

SYMBOLIC TRANSFORMATIONNUMERIC TRANSFORMATIONBACON SANDWICH

PLAIN OMELETTE

PUBLICATION OF DISSERTATIONTOY EXAMPLES

Answer: BONSAI

Optimization Problem
Two sets S, T of strings
 Output: A pattern p that maximizes thescore function f(xp, yp, |S|, |T|).
 Input:

xp : The num. of strings in S that p matches.
yp : The num. of strings in T that p matches.

Score function f expresses the goodness of pin terms of separating the two sets S and T.

Process of Computation
SINPUTT
computing the “goodness”
for all possible patterns
OUTPUT

the pattern of best score

as fast aspossible!!

Previous Work• BONSAI(discovering best Substring pattern), Shimozono et al., 1994
• Discovering best Subsequence pattern, Hirao et al., 2000
• Discovering best Episode pattern, Hirao et al., 2001
• Discovering best VLDC pattern, Inenaga et al., 2002
• Discovering best Window Accumulated VLDC pattern,Inenaga et al., 2002

This Work
We present efficient algorithms to discover:• the best Fixed/Variable Length Don’t Care Pattern• the best Approximate FVLDC Pattern
The aim is to apply more expressive pattern classes to BONSAI• the best Window Accumulated FVLDC Pattern• the best Window Accumulated Approx. FVLDC Pattern
The aim is to add a more classificatory power to the pattern classes

Score Function
The goodness of pattern pgood(p, S, T) = f(xp, yp, |S|, |T|)
S, T : two given sets of strings
xp : num. of strings in S that p matches
yp : num. of strings in T that p matches
If score function f is conic, then we can apply an efficientpruning technique for speeding up the computation.

Score Function to be Conicyfxxxfyy

Conic Function Property(0, y)(x, y)(x’, y’)f(x’, y’) ≤ upperBound(x, y)(0, 0)(x, 0)

upperBound(x, y) : the max value on the square= max{f(0, 0), f(x, 0), f(0, y), f(x, y)}numOfMatchedStr(p, T)

Pruning Techniqued∗scod∗scovernumOfMatchedStr(p, S)
The goodness ofd∗scover≤

The upperBound ofd∗sco<The current
best score

FVLDC Pattern
A Fixed/Variable Length Don’t Care Patternis an element of Π = (Σ∪{○, ★})∗, where ○ matches
any character and ★ matches any string.
e.g. FVLDC pattern ab○a○★b matches abbaabbb.
ab baa bb

FVLDC Pattern Matching
We use an NFA that recognizes the language of agiven FVLDC pattern p. The num. of states is m+1,
where m is the num. of constants and ○’s in p.
p = ★ab○★baΣbb

ΣΣUsing the bit-parallel technique, we can domatching for p in O(m|Σ|) preprocessing timeand O(n) running time .

Approximate FVLDC PatternAn Approximate FVLDC Pattern is an element ofΠ×Ν, where Ν is the set of non-negative integers.
Approx. FVLDC pattern <p, k> is said to matcha string w within distance k if the Hamming Distance
between p and w is within k.
e.g. Approx. FVLDC pattern <ab○a○★b, 1>
matches abbaabba.
ab baa bb a

Approx. FVLDC Pattern Matching
We use an NFA that recognizes the languageof a given approx. FVLDC pattern <p, k>.
The NFA has (m+1)(k+1) states, but (m-k+1)(k+1)
bits are actually enough.
If (m-k+1)(k+1) is not larger than the computer
word length, our bit-parallel algorithm runsin O(|n|) time after O(m|Σ|)-time preprocessing for p.

Approx. FVLDC Pattern Matchingp = <★ab○★b, 2>ΣΣΣ

m=4k=2ab

Σ

b

Σ

Σ

Σ

Σ

ab

Σ

Σ

Σb

Σ

Σ

a

Σ

Σ

Mismatches=0b

Mismatches=1

Σb

Mismatches=2

Σ
The NFA has (m+1)(k+1) states.

Approx. FVLDC Pattern Matchingp = <★ab○★b, 2>

ΣΣ

Σ

m=4
k=2ab

Σ

b

Σ

ΣΣΣab

Σ

ΣΣb

Σ

ΣaΣ

Σ

Mismatches=0b

Mismatches=1

ΣbMismatches=2

Σ
Only (m-k+1)(k+1) states are necessary.

More Classificatory Pattern Class
p = ★d○★sc○★very★

any pattern similar
to “discovery”?

w = fhdihertlhglehglioogfrg
xawpolmkhhjqirvnbotuhxxxxr
ylnvhbtriscovbgneinmvgerig
eooitrnrnvevroigreintnnvoi
woireohirlneroiveryniritro
eitruijnnbrymxbairive

Window Accumulation
Bound the length of occurrence of p
by a window size h.
p = ★d○★sc○★very★
hThis way we can get rid of redundantmatches, and obtain better classification!

Window Accumulated Pattern Matching
We use two NFAs each recognizes the languageof either a given FVLDC pattern p or its reversal.

prev = b★○ab★
bΣ
Σab
Σ

Using the bit-parallel technique, we can dopattern matching for <p, h> in O(m|Σ|) preprocessing
time and in O(n2) running time .
Same for Win-Acc. approx. FVLDC patterns.

Experimental Environment
Machine: Alpha Station XP1000
CPU: Alpha21264 processor of 667MHz
OS: Tru64 Unix OS V4.0F
Datasets:(1) completely random data
(2) VLDC pattern embedded data
(3) FVLDC pattern embedded data
(4) 2-approx. VLDC pattern embedded data(5) window-accumulated 2-approx.
VLDC pattern embedded data

Experimental Result 1

Experimental Result 2

Experimental Result 3

Experimental Result 4
datasetpattern class

(1)

(2)

(3)

(4)

(5)

(5)

VLDC

423

109

236

182

224(554)

FVLDC

1068

331

645

514623 (1579)

approx. VLDC (kmax= 1)

2203

725 1088

approx. VLDC (kmax= 2)4569 1660 2185 1790 2035 (3558)

approx. VLDC (kmax= 3)6973 2739 3324 2868 3146 (5679)approx. VLDC (kmax= 4)9396 3880 4492 4008 4304 (8377)

853 1026 (1820)

Execution times (in seconds) for different pattern classes:
The maximum pattern length was set to 7.
Execution time for each window-accumulated version with dataset (5)is shown in parentheses.