数理解析研究所講究録 1477 巻 2006 年 223-231

223

有効ターム数の確率的解析(Probabilistic Analyses on the Number of Reliable Rules
and the Needed Data Size)
柳浦 睦憲 (Mutsunori Yagiura) \dag er

原口 和也 (Kazuya Haraguchi) *Abstract
Suppose that we are given a data set of examples, where each example is an n-dimensional
Boolean vector and labeled either true or false. A pattern $r=(J, b)$ is defined by a subset, . ’of the Boolean variables and a Boolean vector $b\in\{0, 1\}^{J}$ of the variables in J.
If 7 appears frequently in the true examples and infrequently in the false examples, we call agood rule. In this paper, we consider how many examples are needed for generating “reliable”
good rules, in the sense that they capture the essential properties of the data domain. Suppose
are uniformly distributed and labeled
the random data domain where all examples inat random. A small random data set may contain good rules superficially, although there is noproperty in the data domain. Our claim is that the data set should contain sufficiently many
ex amples to avoid such deceptive good rules existing even in a random data set. We makeprobabilistic analyses to estimate such am ounts of examples, and show experimental studies.

$J\underline{\subseteq}\{1$

$n\}$

$n$

$r$

$\{0, 1\}\mathrm{n}$to justify our claim.
Keywords: $frequent/infrequent$ item sets, association rules, knowledge discovery,

probabilistic analysis.

Introduction

1

Assume that we are given a data set $X$ of examples Each example in $X$ is an n-dimensional) the set of(resp.,
Boolean vector, and is labeled either 1 (true) or 0 (false). We denote by. A patter ntrue (resp., false) examples in X. (Hence, $X=X_{1}\cup X_{0}.$ ) Let us denote, ..
of the Boolean variables and a Boolean vector$r=$ $(J, b)$ is defined by a subset$r=(J_{r}b)$
and aBoolean vector $x\in$ Bn, we say thatpattern.
Forainvariablesof theappears in if $x|J=b$ holds. Let $X(r)$ denote the set of examples in $X$ in which appears;
is defined similarly. We define the frequency
i.e., $X(r)=\{x\in X|x|_{J}=b\}$ . Note that$(r, X)=|X(r)|/|X|$ , which is the ratio of examples in $X$ in which appears. For a constant) holds, then we call an a-frequent (resp., an( , $X$ )$a(0\leq a\leq 1)$ , if $f(r, X)\geq a$ (resp.,$X_{1}$$X_{0}$$\mathrm{B}=\{0,1\}$$J\subseteq\{1$

’

$n\}$

$n$

$J$

$b\in \mathrm{B}^{J}$

$r$

$x$

$r$

$\mathrm{B}^{n}(r)$

$r$

$f$

$f$

$r$

$r$

$\leq a$a-infrequent) pattern in .
patterns is an important issue in such fields as data
The generation of frequent,mining and bioinformatics (e.g., knowledge discovery from genome databases) [1, 4, 11]. (Theset” is widely used in the literature, but in order to avoid the confusion
term ’.
with a simple set of elements, we use the term “pattern’ 可 this paper) It is well-known thatpatterns in incremental polynomial time [1], and many fast
one can generate
algorithms for this task have been proposed so far (e.g.) [10] .
hold, then we call$(0\leq a_{1}, a_{0}\leq 1)$ , if $f(r, X_{1})\geq a_{1}$ andFor constants ,examples (under
true
in
$X$
featureatodescribe
isconsidered
.
an
Such
-good rule inandata set $X$
randomasmall,even$a_{1}\gg a_{0}$ )
are
and
ev
en
;
e.g.,
and
reasonable$X$$/\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{t}$$‘ \mathrm{f}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{t}/\mathrm{i}_{\mathrm{I}1}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{t}$$\mathrm{n}$$\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{t}/\mathrm{i}\mathrm{n}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{t}$$)$$f(r, \lambda_{0}^{t})\leq a_{0}$$a_{1}$$r$$a_{0}$$r$$(a_{1}, a_{0})$$a_{1}$$|X_{1}|$$a_{0}$$|X_{0}|$*京都大学大学院情報学研究科数理工学専攻 (Department of Applied Mathematics and Physics, Graduate School.kyoto-u. .
of Informatics, Kyoto University) e–mail名古屋大学大学院情報科学研究科計算機数理科学専攻 (Department of Computer Science and Mathematical Infor. jp
matics, Graduate School of Information Science, Nagoya University) e-mail:$\mathrm{k}\mathrm{a}\mathrm{z}\mathrm{u}\mathrm{y}\mathrm{a}\mathrm{h}\Phi \mathrm{a}\mathrm{m}\mathrm{p}$.

$\mathrm{i}$$\mathrm{a}\mathrm{c}$$\mathrm{j}\mathrm{p}$$\ovalbox{\tt\small REJECT}$$\mathrm{y}\mathrm{a}\mathrm{g}\mathrm{i}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{G}\mathrm{n}\mathrm{a}\mathrm{g}\mathrm{o}\mathrm{y}\mathrm{a}-\mathrm{u}$224

may contain many good rules that have nothing to do with the inherent structure of $X$ and are
deceptive. In this paper, we consider how many examples should be collected or sampled as thedata set for generating “reliable” good rules, avoiding such deceptive ones.
We estimate such amounts through a probabilistic analysis on random data sets. Suppose a datawith the uniform probability (i.e., 1/2”), and is labeled
domain where an example is drawn fromeither 1 or 0 at random. Essentially, there is no pattern that describes inherent information of thedata set. However, if the given random data set $X$ contains insufficient examples, some patterns
may happen to become good rules due to a bias peculiar to $X$ ; on the other hand, if $X$ contains
sufficiently many examples, good rules will exist very rarely. We analyze upper bounds on thetrue examples and-good rules in a random data set consisting of
expected number ofare larger than thresholds.
andfalse examples, and show that it becomes close to 0 if
We claim that such thresholds give rough estimates on the number of true and false examples
needed to extract reliable good rules from a real data set. We then give some experimental results
to justify our claim based on the random data analysis.
The problem is closely related to the problem of finding association ules. An association ruleis defined by two patterns $(r, r’)=((J, b),$ $(J’, b’))$ with $J\cap J’=\emptyset$ ; it represents that an example
with $x|_{J}=b$ tends to attain $x|_{J’}=b’$ . Patterns in this paper may be regarded as special casesof association rules such that the labels of examples are attached to the original data set as the$(n+1)$ st Boolean variable andis limited to $r’=(\{n+1\}\}$(1) .
An association ruleis usually evaluated by support (which is the frequency of in $X$ ) and), while we evaluate a pattern by its frequency
confidence (which is the frequency of inin. Thus, the generation of frequent patterns corresponds to finding
and infrequency inassociation rules of a basic form. This task on a huge data set is too time-consuming, and Li etal. [7] and Toivonen [8] discussed the proper size of a subset of a huge data set $X$ from which
frequent patterns are generated. Suppose a subset $X’\subseteq X$ of examples and a pattern . They
consider how many examples are needed as $X’$ for ( , Xf) to be close enough to $f(r, X)$ with highprobability, if $X’$ is randomly selected from $X$ .
While they consider the random sampling from the given data set to deal with the situation
where the size of the given data set is huge (i.e. , their objective is to approximate the given data
set with a sample of manageable size), we consider the situation where the size of the given data
set is small and our objective is to judge whether the extracted good rules are reliable or not. Thisis the main difference of our approach from the existing ones.
$\mathrm{B}^{n}$$(a_{1}, a_{0})$$m_{1}$$m_{1}$$m_{0}$$m_{0}$

$x$

$r’$

$)$

$(r, \mathrm{r}’)$

$r$

$r’$

$X_{1}$$r$$\mathrm{d}(\mathrm{r})$$X_{0}$

$r$

$f$

2

Probabilistic Analyses

2,1Preliminaries$r$

We first describe the assumption on the generation of examples.
Assumption 1 The generation of examples is mutually independent. An example (x,uj) is generated by the following process:Step 1: The label is set to 1 with probability p $(0\leq\rho\leq 1)$ , and to 0 otherwise (i.e., withprobability l-p).
$\omega$

Step 2: Let ,:to the distribution$P_{1}$

Since$P_{1}$

and$P_{0}$$P_{0}$$\mathrm{B}^{n}arrow[0, 1]$$P_{\omega}$

denote probabil$ity$ distributions. The vector$x$

is drawn according.

are probability distributions,$\sum_{x\in \mathrm{B}^{n}}P_{1}(x)=\sum_{x\in \mathrm{B}^{n}}P_{0}(x)=1$.

(1)

Consider a pattern . Under the condition that a generated example is labeled 1 (resp., 0) in
Step 1 of Assumption 1, the probability ci (r) (resp.,) that appears in this new example is:$r$$c_{0}(r)$ci (r)$(\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{p}.$$= \sum_{x\in \mathrm{B}^{n}(r)}\mathrm{P}\mathrm{r}\mathrm{i}\mathrm{x})$, ci(r)$r$$= \sum_{x\in \mathrm{B}^{\mathrm{n}}(r)}P_{0}(x))$

(2)

225
examples are labeled 1 andMore generally, under the condition thatfrequent in the0, the probability that istrue examples is:$m_{1}$$r$$U(m_{1}, a_{1}, c_{1}(r))$

and the probability that

$r$

is

$m_{0}$

examples are labeled$m_{1}$$a_{1}$$a_{0}$$=$$(\begin{array}{l}m_{1}s\end{array})$$\sum_{s=\lceil a_{1}m_{1}\rceil}^{m_{1}}$infrequent in the$L(m_{0}, a_{0_{\}}c_{0}(r))$$=$$\sum_{s=0}^{s=\lfloor a_{0}m_{0}\rfloor}$$m_{0}$$c_{1}(r)^{s}(1-c_{1}(r))^{n_{1}-s}$,false examples is:$(\begin{array}{l}m_{0}s\end{array})$$c_{0}(r)^{s}(1-c_{0}(r))^{m_{0}-s}$.

Note that (resp. , $UL$ ) is also the expectation that is an -frequent pattern in the true examples(resp., an ( , )-good rule in the true and false examples).
the set ofthe size of . We denote by
For a pattern $r=(J, b)$ , let us call the cardinality
holds and thatall possible patterns of size $k(1\leq k\leq n)$ . Note that $|R_{k}|=2^{k}$, , Qo)) be the expected number of,) (resp., ’( ,holds for any $r\in R_{k}$ . Let, , , )
(resp,,-frequent patterns (resp., ( , )-good rules), andbe the expectations (resp., $UL$ ) of those of size . Prom the linearity of expectations, they arecomputed as follows:$U$$a_{1}$$r$$a_{1}$$\mathrm{a}\mathrm{o}$$|J|$$R_{k}$$r$$|\mathrm{B}^{n}(r)|=2^{n-k}$$(\begin{array}{l}nk\end{array})$$\mathrm{B}\mathrm{n},$$a_{1}$$a_{1}$$m_{1},$$E$$a_{1}$$m_{1}$$m_{0}$$a_{1}$$E_{k}.(n, m_{1}, a_{1})$$U$$E_{k}^{\mathrm{r}}(n,$$m_{1}$$m_{0}$$a_{1}$$a_{0})$$k$$E(n, m_{1}, a_{1})$$\mathrm{B}\mathrm{n},$$n$$a_{0}$$m_{1},$ $m_{0},$ $a_{1},$ $a_{0})$,$=$$\sum_{k=1}^{n}2k(l|$ $m_{1}$$=$$\sum_{k=1}^{n}‘\sum_{\in R_{k}}U(m_{1\}}a_{1}, c_{1}(r))$$=$$\sum_{k_{-}-1}^{n}E_{k}^{*}(n, m_{1}, m_{0}, a_{1}, a_{0})$$=$$\sum_{k=1}^{n}\sum_{r\in R_{h}}U(m_{1}, a_{17}c_{1}(r))L$$a_{1}\rangle$

,

(3)

(

$m_{0},$ $a_{0}$, Co (r)).

(4)

Suppose that the size of a pattern is large. Prom $|\mathrm{B}^{n}(r)|=2^{n-k}$ , appears in a small, and thus may not be frequent in the given true examples. Then, it isportion of vectors inandwith large are close to 0. On the other hand, a pattern of a small
anticipated that, and thus may not be infrequent in the given false examples.
size appears in many vectors in
is close to 0 for allwith small is close to 0. Hence, if
It is therefore anticipated that
subsection,that it surely holds
we
show
$=1$
In
the
next
be
close
to
0.
will also, . . ’ , thenA
in the random data under some conditions.
and
For the analysis, we need the following assumption on
$k$

$r$

$r$

$\mathrm{B}^{n}$$E_{k}$$r$$k$$E_{k}^{*}$$\mathrm{B}^{n}$

$k$

$k$

$E_{k}^{*}$$n$$E_{h}^{*}$$E^{*}$$P_{0}$$P_{1}$

Assumption 2 For any x$\in \mathrm{B}^{n}$, Py (x)$\leq p$and Py(x)$\geq q$hold for some constants p and q.

. Note that the above assumption enables
From (1), it is implied that $p\geq 1/2^{n}$ and
us to cover various distributions including the uniform distribution (which is realized by setting$q\leq 1/2\mathrm{n}$$p=q=1/2^{n})$ .

2.2

Upper Bounds on$E_{k}$

and$E_{k}^{*}$

We first introduce some well-known bounds in the probability theory.
Theorem 1 (Chernoff [3]) Given a positive integer $m$ and $0\leq\mu\leq 1$ , lettaking the value as follows:$1-\mu$$Y_{i}$$=$$\{$$-\mu$

with probability ,with probability $1-\mu$ ,$\mu$$Y_{i}$

be a random variable

228

and let$Y= \sum_{i=1}^{m}Y_{i}$. Then, for any $\beta>1$ ,$\mathrm{P}\mathrm{r}(Y\geq(\beta-1)\mu m)$(5)$<(\exp(\beta-1)\beta^{-\beta})^{\mu\prime n}$holds.
Theorem 2 (Hoeffding [6]) For a positive integer m and $0\leq a\leq 1$ , if $0\leq/4$$a\leq\mu\leq 1$(6)$L(m, a, \mu)\leq\exp(-2m(\mu-a)^{2})$ .

(7), thenVariations of Theorem 1 are found in ], for example.
(and thus
Now we show two types of upper bounds on$|2$$E_{k}$

Theorem 3 For given parameters ,holds, where
then
$n$

$E_{k}$ $(n_{1}m_{1},a_{1})$$a_{1}$$e$$E_{k}^{*}$

and , and for any$p$$\epsilon$$\in(0,1]$

, if

$k$

.

$k\geq k_{1}$ant$m_{1}\geq M_{1}$,,$M_{1}= \frac{n\ln(\underline{?}n)-\ln\epsilon}{a_{1}}$,denotes the base of the natural logarithm.

be a pattern of size $k\geq k_{1}$ . Prom Assumption 2 and $|\mathrm{B}^{n}(r)|=2^{n-k}$ , $c_{1}(r)\leq$holds. Let
holds; now since $2^{n-k}\leq 2^{n-k_{1}}=a_{1}/(e^{2}p)$ , Ci (r)be a random variable taking the value as follows:

Proof. Let$r$$\min\{1,2^{n-k}p\}$$Z_{i}$) for “large”$\leq\epsilon$$k_{1}=n- \log_{2}\frac{a_{1}}{e^{2}p}$and, then.

$\exp(-2m(a-\mu)^{2})$$\mathrm{L}(\mathrm{m}, a, \mu)\leq$

If$\leq a$$\leq 2^{\mathrm{n}-k}p\leq a_{1}/e^{2}<1$

1with probability
0 with probability 1$2^{\mathrm{n}-k}.p$$Z_{j}$and let$Z= \sum_{i=1}^{m_{1}}Z_{i}$

$=$

$\{$

,

$-\underline{9}^{n-k}p$(8),. Let $Y_{i}=Z_{i}-2^{n-k}p$ and $Y= \sum_{i=1}^{7n_{1}}Y_{i}=Z-2^{n-k}pm_{1}$ . Then, we have$E_{k}(n, m_{1}, a_{1})$$=$$\sum_{\gamma\in R_{k}}U(m_{1}, a_{1}, c_{1}(r))$$\leq$$\mathrm{L}(\mathrm{m}, a_{1\}}2^{n-k}p)\mathrm{x}$$=$$\mathrm{P}\mathrm{r}(Z\geq a_{1}m_{1})\mathrm{x}$$=$$\mathrm{P}\mathrm{r}(Y\geq 2^{r\iota-k}pm_{1}(\frac{a_{1}}{2^{n-k}p}-1))\mathrm{x}$$2^{k}$$|R_{k}|$$(\begin{array}{l}nk\end{array})$$2^{k}$$(\begin{array}{l}nk\end{array})$.

From $k\geq k_{1}$ , $a_{1}/(2^{n-k}p)\geq e^{2}>1$ . By applying Theorem 1 with $m=m_{1}$ , $\mu=2^{n-k}p$ and, we have$\beta=a_{1}/(2^{n-k}p)$Then,$m_{1},$$a_{1}$)$e^{-a_{1}m_{1}}\mathrm{x}$$\leq$The right hand side of (9) is not more than$m_{1}$$\geq$$2^{k}$$( \frac{2^{n-k}pe}{a_{1}})^{a1m_{1}}\mathrm{x}$$<$$\epsilon$$(2n)^{n}$$(\begin{array}{l}nk\end{array})$(9).

if and only if$\frac{n\ln(2n)-\ln_{\Xi}}{a_{1}}=M_{1}$.

(10)$\square$227

and , and for any
Theorem 4 For given parameters ,holds, where, then $E_{k}(n, m_{1}, a_{1})$(?) and$n$$k\geq k_{1}$$p$$a_{1}$$m_{1}\geq l\mathfrak{i}^{l},I_{1}(t)$$k_{1}(t)=n- \log_{2}\frac{a_{1}-t}{p}$Proof. Let$r$$\min\{1,2^{n-k}p\}$$\in(0,1]$$\epsilon$

and any $t\in(0, a_{1})$ , if$\leq\epsilon$,$M_{1}(t)= \frac{n\ln(2n)-\ln\epsilon}{2t^{2}}$.

be a pattern of size $k\geq k_{1}(t)$ . From Assumption 2 and $|\mathrm{B}^{n}(r)|=2^{n-k}$ , ci $(r)\leq$$2^{n-k-}p\leq a_{1}-t<a_{1}\leq 1$ . Thus, ci $(r)\leq 2^{n-k}p$ andholds; now since$k\geq \mathrm{h}$$U$($m_{1},$$(\mathrm{t})$$a_{1}$, ci ( )(11)$\leq$$\mathrm{r}$$a_{1},\underline{?}^{n-k}p$).

By applying (6) of Theorem 2 with $m=m_{1}$ , $a=a_{1}$ and $\mu=2^{n-k}p$ ,$U(m_{1}, a_{1},2^{n-k}p)$$\exp(-2m_{1}(a_{1}-2^{n-k}p)^{2})$$\leq$,and thus$E_{k}(n, m_{1}, a_{1})$$\leq$$\exp(-2m_{1}(a_{1}-2^{n-k}p)^{2})\mathrm{x}$ $2^{k}$$\leq$$\exp(-2m_{1}t^{2})\mathrm{x}$The right hand side of (11) is not more than

(11)

.

if and only if$\epsilon$$\frac{n\ln(2n)-\ln\epsilon}{2t^{2}}=M_{1}(t)$$\geq$$m_{1}$$(2\mathrm{n})\mathrm{n}$$(\begin{array}{l}nk\end{array})$.

(12)$\square$in Theorem 4 depends on thein Theorem 3 is a constant whileand ,For given ,parameter . The following corollary about the range of helps in obtaining an upper boundby Theorem 4.
with
Corollary 1 For a nonnegative number l, if $0<t\leq a_{1}(1-2^{\ell}/e^{2})$ , then $k_{1}-k_{1}(t)\geq p$ .
$n$$a_{1}$$p$$k_{1}(t)$$k_{1}$$t$$t$$E_{k}\leq\epsilon$$\mathrm{h}(\mathrm{t})\leq k\leq k_{1}$Proof. It directly comes from the definition of
Now we show an upper bound on

Theorem 5 For given parameters ,, thenand
if$fk$$n$$\leq \mathrm{k}\mathrm{o}(\mathrm{s})$$k_{1}$

andfor “small”$E_{k}^{*}$$m_{1}$,$a_{1}$,$a_{0}$$k$$k_{1}(t)$.

$\square$.

and , and for any $\in(0, 1]$ and any $s\in(0, 1)$ ,holds, where$\epsilon$$q$$E_{k}^{*}(n, m_{1}, m_{0}, a_{1},a_{0})\leq\epsilon$$m_{0}\geq \mathrm{k}\mathrm{o}(\mathrm{s})$$k_{0}(s)=n- \log_{2}\frac{a_{0}+s}{q}$,$M_{0}(s)= \frac{k_{0}(s)\ln(2n)-\ln\epsilon}{2s^{2}}$Proof. The proof is similar to that of Theorem 4. Let
andAssum than 2,of Theorem 2 with $m=m_{0}$ , $a=a_{0}$ and $\mu=2^{n-k}q$ ,$|\mathrm{B}^{n}(r)|=2^{n-k}$$k\leq \mathrm{k}\mathrm{o}(\mathrm{s})$$L(m_{0}, a_{0}, c_{0}(r))$$r$.

be a pattern of size $k\leq k_{0}(s)$ . From$>a_{0}$ holds. By applying (7)$\mathrm{c}\mathrm{o}(\mathrm{r})\geq 2^{n-k}q\geq a_{0}+s$$\leq$$L(m_{0}, a_{0},2^{n-k}q)$$\leq$$\exp(-2m_{0}(2^{\mathrm{n}-k}q-a_{0})^{2})$holds and hence we have$E_{k}^{*}(n, m_{1}, m_{0}, a_{1}, a_{0})$$\leq$$\exp(-2m_{0}(2^{n-k}q-a_{0})^{2})\mathrm{x}2^{k}$$\leq$$\exp(-2m_{0}s^{2})\mathrm{x}(2n)^{k_{0}(s)}$The right hand side of (13) is not more than$m0$$\geq$$\epsilon$.

$(\begin{array}{l}nk\end{array})$(13)

if and only if$\frac{k_{0}(s)\ln(2n)-\ln\epsilon}{2s^{2}}=M_{0}(s)$.

(14)$\square$228

Corollary 2 For given parameters n,$a_{1}$,$a_{0}$

s $\in(0,$ 1), if s $\leq q(a_{1}-t)/p-a_{0}$ holds, then

, p andand for any tholds.

$q_{y}$

Proof. It directly comes from the definitions of k% (t) and
Finally,$E^{*}$(0, al 1 $-1/e^{2}$ )] and any$\mathrm{k}\mathrm{o}(\mathrm{s})$.

$\square$is sufficiently small under the conditions given in the following theorem.

Theorem 6 For given parameters , , ,and $\in(0,$ , if $m_{1} \geq\max$ { , Mi } and$n$$M_{1}$$1|$$\epsilon$$\in$$k_{0}(s)\geq k_{1}(t)$$(\mathrm{t}$$E^{*}(n, m_{1}, m_{0}, a_{1}, a_{0})$$a_{1}$$a_{0}$$p$and , and for any $t\in(0, a_{1}(1-1/e^{2})]$ , $s\in(01)\}$, then$q$$m_{0}\geq\Lambda I_{0}(s)$$\}$$. \sum_{k=1}^{[k_{\mathrm{O}}(s)\rfloor}$$\leq$$\epsilon- 1$

holds. Moreover, if $s\leq q(a_{1}-t)/p-a_{0}$ , then $E^{*}(n,$$\sum_{k=|k_{0}(\mathrm{s})\rfloor+1}^{\lceil k_{1}(t)\rceil-1}2^{k}$$m_{1}$,$m_{0}$,$a_{1}$$(\begin{array}{l}nk^{\wedge}\end{array})$, aOi$+ \sum_{k=\lceil k_{1}(t)\rceil}^{n}\epsilon$$\leq n\epsilon$

holds.

(e.g., $p\simeq q$ and $a_{1}>>a_{0}$ ), there exist and that
For appropriate values of , ,and), which showssatisfy the above conditions, and we can choose sufficiently small (e.g.,that $E^{*}(n,m_{1}, m_{0}, a_{1}, a_{0})$ converges to 0.
$p$

$q$

$a_{1}$$s$$a_{0}$

3$t$$\epsilon=2^{-n}$$\epsilon$

Experimental Studies

In this section, we observe the expectationin real data sets.

3.1$E^{*}$

for random data sets and the numbers of good rules

Real Data Sets

We take two real data sets fiiom UCI Repository [9]; i.e., BCW and HEART. The examples in thesedata sets are numerical vectors, and we transform them into binary examples by the method usedin [5]. For a data set, let us denote byandthe sets of available true and false examples,
respectively We denote,and. BCW contains 239 true
examples and 444 false examples with 13 Boolean variables (i.e.,$m_{0}^{*}=444,$ $n=13$ ),while HEART contains 120 true examples and 150 false examples with 10 Boolean variables (i.e.,, $m_{0}^{*}=150$ , $n=10)$ .
$X_{1}^{*}$$X^{*}=X_{1}^{*}\cup X_{0}^{*}$$X_{0}^{*}$$|X_{1}^{\mathrm{v}}|=m_{1}^{*}$$|X_{\dot{0}}|=m_{0}^{*}$$rn_{1}^{\mathrm{F}}=239,$$m_{\mathrm{J}}^{*}=120$

3.2$E^{*}$

for Random Data

Let us observe the expectationof good rules for random data sets. In the uniformly distributed$=1/2^{n}$ holds for all
random data domain, Pi (x)By using this, we can compute$(n, m_{1}, m_{0}, a_{1}, a_{0})$ exactly from (2) to (4).
In order to compare
for random data sets to the numbers of good rules in real data sets later,
we use $n=13$ and 10, corresponding to BCW and HEART, respectively. We test all combinationsof $a_{1}\in\{0.10,0.20$ ). and $a_{0}\in\{0.00,0.01, 0.02\}$ . For given ,and , we examine the changeof $(n, m_{1}, m_{0}.a_{1}, a_{0})$ as
increase, where we use
and
with
for
each real data set.
We show $(n, m_{1}, m_{0}, a_{1}, a_{0})$ for two combinations of parameters andcorresponding
to BCW and HEART in Figs. 1 and 2, respectively. Each contains two graphs, where the left (resp.,right) graph is for $a_{1}=$ O.JO (resp., $a_{1}=0.20$ ). In each graph, the horizontal (resp., vertical) axis
represents $m_{1}+m_{0}$ (resp., $E’$ ) and the three curves correspond to different values of . Note thatthe vertical axis is the logarithmic scale.
appears to be an approximately monotone decreasing function of $m_{1}+m_{0}$ . As observed
from the figures,is sufficiently small (i.e., less than 1) as $m_{1}+m_{0}$ is larger than at most several
hundred, Among the examined values of(resp.,), let us denote by $M$; (resp.,) thesmallest value that attains $E^{*}\leq 1$ . Table 1 showsfor each parameter combination
examined in these figures$E^{*}$$x\in \mathrm{B}^{n}$$=\mathrm{P}\mathrm{i}(\mathrm{x})$$E^{*}$$E^{*}$$n$$E^{*}$$m_{1}$$a_{1}$$a_{0}$$(m_{1}, m_{0})$$m_{0}$$E^{*}$$n$$m_{1}/m_{0}=m_{1}^{*}/m_{0}^{*}$$m_{1}/m_{0}$$a_{0}$$E^{*}$$E^{*}$$m_{1}$$m_{0}$$(M_{1}^{*}, M_{0}^{*})$$M_{0}^{*}$

229$a_{1}=0.10$$a_{1}=0.20$

10000

10000

$-$ )

$a_{0}=0.\mathrm{o}\mathrm{o}$$a_{0}a_{0}==0.010.00$

$ 000

100

1

$- \mathrm{s}--*--$$\backslash ^{\backslash }\backslash -\mathrm{g}^{\backslash }\backslash \mathrm{l}\backslash \mathrm{g}\iota_{1}$as $=0.02$$\mathrm{t}^{\mathrm{c}\iota^{\backslash }’-}\backslash \backslash \backslash .\backslash$$ao=0.\mathrm{O}1$$6-\bullet \mathrm{O}^{\cdot}$-a$\backslash$$000\mathrm{t}00$$\mathrm{t}$$\nwarrow 0^{\cdot}\mathrm{r}$$a\mathrm{o}=0.02$,$\iota_{\backslash }$$E’$$E^{*}$$701$$\backslash \mathrm{b}^{\mathrm{b}}\nwarrow\backslash ;_{l}\backslash ^{\mathrm{E}\mathrm{J}}\nwarrow_{\backslash }\mathrm{B}\mathrm{x}_{\backslash }\backslash .\backslash 1$$10\uparrow$$\iota_{\aleph_{1}^{\backslash }}\iota_{1}^{-}\backslash \backslash \backslash$$\vee \mathrm{r}$$\grave{\mathfrak{g}}$$\backslash \backslash \mathrm{o}\mathrm{e}_{1}1$$[searrow]\backslash$01$\tau_{\mathrm{J}}\{\mathrm{D}$i3 a$\mathrm{t}_{\backslash }\backslash \backslash$

001

100

200

300

$\backslash$$\iota_{1}\backslash \mathrm{D}1_{\iota}$$.- \mathrm{r}_{\backslash }$

0OI

683

400

$m_{1}+$

Figure 1:BCW)

07$\backslash .-\cdot\backslash$

mo

100

200

300

400

$m_{1}$$+m_{0}$683

with $n=13$ and $m_{1}/m_{0}=$ 239/444 (corresponding to data set$E^{*}(n, m_{1}, m_{0}, a_{1}, a_{0})$Ql $=010$$a_{1}=0.20$

10000

10000
$a_{0}=0.\mathrm{o}\mathrm{o}$1000$a_{0}=0.\mathrm{o}\mathrm{o}$$a_{0}=0.01$$p_{\iota_{\mathfrak{l}}}\mathrm{A}_{\backslash }$$a_{0}=0.02$$a_{\mathrm{O}}=0.02$$\backslash$.

$70010$$\backslash -\mathrm{x}_{\backslash }^{\backslash }\backslash \backslash \backslash \mathrm{x}_{\backslash }^{-}\backslash \backslash \mathrm{q}_{\backslash \backslash }\backslash \backslash \backslash \cdot.\backslash \backslash \backslash \wedge-\bigwedge_{13}\backslash \backslash$$10010$)$\epsilon---- \mathrm{B}$

$-$

1000

$a_{0}=0.01$$—–\succ \mathrm{I}3$$\backslash \backslash \backslash \mathrm{r}\backslash \backslash \backslash _{\bullet\backslash --arrow}$$E^{*}$’-t3$\backslash \mathrm{a}_{\mathrm{c}}’$1,$\backslash \backslash$1$\mathrm{u}$$\backslash \sim\kappa_{\sim}$$\backslash \backslash _{\backslash _{\backslash }}\backslash _{\backslash ,\backslash \backslash }$$B^{\mathrm{r}}$$\backslash 1\backslash \backslash$$\backslash \backslash \}\iota_{\backslash }\backslash$$\backslash \mathrm{h}\backslash \backslash \backslash .\backslash \backslash$

0101$\backslash \rangle \mathrm{t}$$\backslash$$\backslash 1_{\backslash }\backslash 1$

001

50

100

150

001

200

$\backslash$$\cdot$$E^{*}(n, m_{1}, m_{0}, a_{1}, a_{0})$

270

200

Ml $+m_{0}$$m_{1}+m_{\beta}$

Figure 2
HEART)

150

100

with $n=10$ and $m_{1}/m_{0}=$ 120/150 (corresponding to data set

and $M_{0}(s)$ of Theorem 6 as upper bounds of
Let us mention the values of,and $M_{0}(s)$ by setting
and , we compute, respectively. For given ,and$=1/n$ . We take andsuch that they minimize $\max\{M_{1}, M_{1}(t), M\mathit{0}(s)\}$$p=q=1/2^{n}$ and$10^{-3}\in(0, a_{1}-a_{0}-t]$ for natural numbers
among those $t=\ell \mathrm{x}10^{-3}\in(0, a_{1}(1-1/e^{2})]$ andby the sim ple enumeration. The obtained upper
and ; in this experiment, we obtain suchbounds are not very tight; e.g., if $(n_{\rangle}a_{1}, a_{0})=(13,0.10 0.00)$ , then $M_{1}=$ 449.20, $M_{1}(t)=$ 6036.04
and $M_{0}(s)=$ 6029.60, while $M_{1}^{*}=95$ and $M_{0}^{*}=167$ from Table 1 It indicates that Theorem 1
and 2 do not always give tight bounds.
$\max\{M_{1}, \mathrm{J}/I_{1}(t)\}$$M_{1}^{*}$$n$$\mathrm{J}/I_{0}^{*}$$M_{1}$$a_{0}$$a_{1}$$t$$\epsilon$$\Lambda I_{1}(t)$$s$$s=\ell’\mathrm{x}$

$f$

3.3

$l’$

$(\mathrm{i}, s)$

Number of Good Rules in Real Data

, we would like to observe how the number of good rules
For given real data sets and ( ,of theandincrease and compare its tendency with the values ofandchanges aslast subsection. In order to simulate the situation where we have smaller number of examples thanwith $|X_{1}|=m1$ , $|X_{0}|=m0$
andthe original data set, we randomly sample$X=X_{1}\cup X_{0}$ . We repeat this processin$m_{1}/m_{0}=m_{1}^{*}/m_{0}^{*}$
rules
-good
generate,andand-good rules. In this experiment, we use
times and take the average $N$ of the numbers of$a_{1}$$m_{1}$$a_{0}\rangle$$M_{1}^{*}$$m_{0}$$X_{1}\subseteq X_{1}^{*}$$M_{0}^{*}$$X_{0}\subseteq X_{0}^{*}$$(a_{1}, a_{0})$$\tau$$(a_{1}, a_{0})$.
We show $N$ for BCW and HEART in Figs. 3 and 4, respectively. Note that the vertical axes inthese figures are not the logarithmic scale in contrast to Figs. 1 and 2. In each graph of the figure$\tau=100$

for HEART, the three curves overlap

230

Table 1:$(M_{1}^{*}, M_{0}^{*})$

for various parameter combinations corresponding to real data sets

$a1=0.10$$a_{1}=0.20$

6000

6000

4000

4000

$N2000$$N2000$00$m_{1}+m_{0}$Figure 3: The number $N$ of good rules for data set BCW

For data set BCW, we see that the number $N$ of generated good rules does not change much
, while it drastically decreases when $m_{1}+m_{0}<M_{1}^{*}+M_{0}^{*}$ , for all
when. We observe that if
combinations ofandare small (e.g., 10 to 30), then more than
10 superficial good rules are extracted, while
contains at most 2000 real good rules.
For data set HEART, $N$ becomes 0 with $(m_{1}, m_{0})$ which are smaller than. Somedata sets do not contain good rules although they have some regularities or structures; for example,
suppose such a data set
and each example $x\in X$ is labeled by the par$ity$ function;$m_{1}+m_{0}\geq\Lambda’I_{1}^{*}+M_{0}^{1^{\zeta}}$$(a_{1}, a_{0})$$m_{1}$$m_{0}$$X^{*}$$(M_{\mathit{1}_{1}}’, M_{0}^{*})$$X=\mathrm{B}^{\tau\iota}$$\omega$

1 if
is odd,0otherwise.
$\sum_{j=1}^{n}x_{j}$$\omega$

$=$

$\{$

(15)

Clearly, $X$ does not have-good rules under reasonable
although it has the rule of(15). In the case of such data sets, it is important to detect that there is no good rule of ourdefinition. Figs: 5 and 6 show that, for these data sets, it is sufficient for us to havetrue
examples andfalse examples in order to see that there is no good rule.
The above results justify our claim on the size of the data set needed to generate reliable goodrules. However,and $M_{0}(s)$ are not very good as upper bounds of,andrespectively. It is our future work to derive tighter upper bounds.
$(a_{1}, a_{0})$$(a_{1}, a_{0})$$M_{1}^{*}$$M_{0}^{*}$$\max\{\mathrm{J}/I_{1}, M_{1}(t)\}$4$M_{1}^{*}$$M_{0}^{*}$

Conclusion

In this paper, we consider how many examples are needed in data sets for extracting reliable goodrules. Our claim is that the data set should contain examples more than the value such that arandom data set has good rules very rarely. We derive a required amount of true examples as$\max\{M_{1}, M_{1}(t)\}$ and of false examples as $M_{0}(s)$ . We then show some computational
studies tojustify our claim

231$a_{1}=0.20$$a_{1}=0.10$150$\mathrm{I}50$‘$–\kappa-$$\iota_{1}$

–B-

$00
100

$a0=0.00$$a0=0.00$$a0=0.01$$a0=0.02$$-\cdot-*\sim--k-- \mathrm{B}-$$\dagger_{1}|‘|||$$a_{0}=0.01$$a\mathit{0}=0.02$

100$||\iota_{\mathrm{I}}\downarrow|||$$||\iota_{\mathfrak{l}}$

$N$

$N50$

50

$|\{$

$\xi|$

0$\backslash$

50

100

$50

200

270

0

50

100

150

270

200

$m_{1}+m\mathit{0}$$m_{1}+m\mathit{0}$Figure 4: The number $N$ of good rules for data set HEART

Acknowledgments
We are indebted to Prof. Toshihide Ibaraki of Kwansei Gakuin University, Japan, and Prof. Endre
Boros of Rutgers University, USA, for a number of helpful comments and suggestions. This work
was supported by Grant-in-Aid for Scientific Research on Priority Areas “Comparativefrom the Ministry of Education, Culture, Sports, Science and Technology of Japan.
$\mathrm{G}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{c}\mathrm{s}^{)2}$

References[1] R. Agrawal, T. Imielinski, A. Swami, “Mining Association Rules between Sets of Items in
Large Databases”, ACM SIGMOD Conference on Management of Data, 1993
[2] N. Alon, J. H. Spencer, P. Erdos, eds., “The Probabilistic Method”, , John Wiley & Sons, 1992
[3] H. Chernoff, “A Measure of the Asymptotic Efficiency for Tests of a Hypothesis Based on the
Sum of Observations” , Annals of Mathematical Statistics, vol. 23 (1952), pp. 493-509
Discovery[4] U. Fayyad, G. Piatetsky-Shapiro, S. Padhraic, “Prom Data Mining to Knowledge
in Databases” , AI Magazine, vol. 17, No. 3 (1996), pp. 37-54[5] K. Haraguchi, T. Ibaraki, E. Boros, “Classifiers Based on Iterative Compositions of Features” , Proc, 1st International Conference on Knowledge Engineering and Decision Support(TCKED S 2004), Porto, Portugal (Jul, 2004), pp. 143-150[6] W. Hoeffding, “Probability Inequalities for Sums of Bounded Random Variables”, Journal of
American Statistical Association, vol. 58 (1963), pp. 13-30[7] Y. Li, R. P. GopaLan, “Effective Sampling for Mining Association Rules” , LNAI
Webb and X. Yu eds. (2004), Springer-Verlag, pp. 391-401

3339, G. I.

[8] H. Toivonen, “Sampling Large Databases for Association Rules”, Proc. 22nd VLDB Conference, Bombay, India (1996), pp. 134-145[9] C. L. Blake, C. J. Merz, eds.,. ics.uci.
“UCI Repository of Machine Learning Databases”, http:Repository.html, 1998
for[10] T. Uno, M. Kiyomi, H. Arimura, “LCM ver 2: Efficient Mining Algorithms
FIMF04,
2004
WorkshopProc,
itemsets”, ,IEEE ICDM’04$\mathrm{e}\mathrm{d}\mathrm{u}/\sim \mathrm{m}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}/$$//\mathrm{w}\mathrm{w}\mathrm{w}$$\mathrm{F}\mathrm{r}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{t}/$$\mathrm{C}\mathrm{l}\mathrm{o}\mathrm{s}\mathrm{e}\mathrm{d}/\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{l}$Frequent[11] G. Yang) “The Complexity of Mining Maximal Frequent Itemsets and Maximal
andDiscovery
Knowledge
onPatterns”, , Proc. 10th ACM SIGKDD International Conference344-35(2004),
Seattle,USA
PP.
Data Mining,