\begin{slide}{What is data mining?}
\twocolumn[lineheight=7cm,lcolwidth=1.9in,%
           rcolwidth=1.9in,%
           lineprop={linestyle=solid,linewidth=0.25pt}
]{
\bi
\item
	Diamonds in the dust
\item	Summarization: not 1000 records, but 3 rules
\item
	Example \#1: 
\bi
\item
text mining issue reports
\item
\ei
\item
		901 NASA records, PITS issue tracker:  \{severity, free text\}
\ei

~\\

{\footnotesize
			\begin{tabular}{l|r@{~}l}
			severity & frequency& \\\hline
			1 (panic)        & 0 &\\
			2        & 311 &\rule{20mm}{2mm}\\
			3        & 356 &\rule{22mm}{2mm}\\
			4        & 208 & \rule{16mm}{2mm}\\
			5 (yawn)       & 26  & \rule{1mm}{2mm}
			\end{tabular}}
}{
\bi
\item
		All unique words, sorted by ``magic'' (see below)
\item
		Rules learned from  N best 
\item
		Severity 2 predictors:\newline 
10*\{(train,test) = (90,10)\%\}
\ei
 
{\scriptsize		\begin{tabular}{r|rr|l}
	N & a=recall  & b=precision& $F=\frac{2*a*b}{a+b}$\\\hline
		100      &    0.81                            &0.93    & 0.87  \\
		50       &    0.80                           & 0.90    & 0.85  \\
		25       &    0.79                           & 0.93    & 0.85  \\
		12       &    0.74                              & 0.92  & 0.82  \\
		6        &    0.71                           & 0.94    & 0.81  \\
		3        &    0.74                           & 0.82    & 0.78 \\\hline 
		\end{tabular}}

~\\

Rules (from N=3 words):

{\scriptsize	\begin{tabular}{r@{~}l@{~}r}
            & if (rvm $\le$ 0) \& (srs = 3) &$\rightarrow$ sev=4\\
        else &if (srs $\ge$ 2)              &$\rightarrow$ sev=2 \\
        else  &                         & $\rightarrow$ sev=3\\
		\end{tabular}}
\bi
\item
	Diamonds in the dust
\bi
\item
		Not  9414 words total 
\item
or 1662 unique words
\item
 but 3 highly predictive words
\ei
\ei
}
\end{slide}
\begin{slide}[method=file]{Dumb Luck?}
%\twocolumn[lineheight=7cm,lcolwidth=1.9in,%
%           rcolwidth=1.9in,%
%           lineprop={linestyle=solid,linewidth=0.25pt}
%]{
\bi
\item
Nope. 
\item 
In four other case studies, learning from just the top 3 terms ...
\bi
\item
10*\{(train,test) = (90,10)\%\}
\item
yields probability of detection of highest severity class of 93\% to 99.8\%.
\ei
\item (Note: ignoring real rare classes.)
\ei

~\\

\begin{minipage}{.5\linewidth}
Project ``b'': 984 records
{\scriptsize \begin{verbatim}
a   b   c   d   <-- classified as
1 380   0   0 |   a = _4
1 520   0   0 |   b = _3 pd=99.8%
0  59   0   0 |   c = _5
0  23   0   0 |   d = 2\end{verbatim}
} 
\end{minipage}
\begin{minipage}{.45\linewidth}
Project ``d'': 180 records
{\scriptsize\begin{verbatim}
  a   b   c   <-- classified as
157  23   0 |   a = _4
  9 121   0 |   b = _3 pd=99.4%
  6   1   0 |   c = _5 

\end{verbatim} 
  

} 
\end{minipage}

\vspace{0.5cm}

\begin{minipage}{.5\linewidth}
Project ``c'': 317 records
{\scriptsize\begin{verbatim}
  a   b   c   <-- classified as
  9 121   0 |   b = _3 pd=93.1%
157  23   0 |   a = _4
  6   1   0 |   c = _5 

\end{verbatim} 
} 
\end{minipage}
\begin{minipage}{.45\linewidth}
Project ``e'': 832 records
{\scriptsize\begin{verbatim}
a   b   c   d   <-- classified as
0  23   0   0 |   a = _2
0 498   0  18 |   b = _3 pd=96.5%
0  34   0   7 |   c = _5
0 178   0  65 |   d = _4 \end{verbatim} 
}
\end{minipage}
\end{slide}
%
%\begin{slide}{Methods}%
%\bi%
%	\item	Too many data mining methods to list here%
%			\bi%
%				\item But there are common themes amongst the methods.%
%			\ei%
%	\item	``Use, don't dictate''%
%	\bi%
%		\item	Basili et.al. ``Learning Organizations'' %
%			\bi%
%			\item carefully design their data collection%
%			\ei%
%		\item		Me, chasing the ice-cream truck%
%		\bi%
%			\item Use whatever is around.%
%			\item Savage pace of organizational change.%
%		\ei%
%	\ei%
%	\item ``Less is more''%
%	\bi%
%		\item Pruning features is a good idea%
%	\ei%
%\ei%
%\end{slide}%
%%
\begin{slide}{How is this Possible?}  
	\bi
		\item	Feature subset selection (FSS) (\cite{hall03, miller02})
		\bi
			\item $y = \beta_0 + \beta_1f_1 + \beta_2f_2 + \beta_3f_3 ..$.
			\item	Variance in $y$ reduced by pruning some $f_i$
			\item	But don't prune too much: 
					\bi
					 	\item e.g. $\forall f_i, y=\beta_0$ 
					\ei
            \item Analogous argument holds for other representations.
		\ei
		\item Q: How to do FSS? 
        \item A1:Apply domain knowledge
		\bi
			\item e.g., in text mining, TF*IDF: 
			\bi
				\item {\em term frequency inverse document frequency}
				\item Frequent terms, but only in a small number of documents
			\ei
			\item TF*IDF = $F[i,j] * log(IDF)$
			\bi
				\item $F[i,j]$ = frequency of word i in document j
				\item $IDF$ =  \#documents / (\#documents with i)
				\item Above study used top 100 $TF*IDF$ words.
			\ei
		\ei
	\ei
\end{slide}
\begin{slide}{Less is More} 
	\bi
	\item Q: How to do FSS?
    \item A2: Exponential time FSS	
		\bi
			\item 	Try all $2^F$ subsets of $F$ on a {\em target learner} 
			\item 	Possible, with small feature sets, with some heuristic search 
			\bi
				\item best first search, STALE=5 (\cite{kohavi97}).
			\ei
		\ei
	\item	A3: Linear time FSS (not as thorough as $2^F$):
		\bi
			\item Sort $F$, somehow; 
			\item Try first $1\le f\le F$ features
			\item Above study sorted top 100 TF*IDF terms on \underline{infogain}
			\bi
				\item Initially:  
				\bi
					\item $H(C) = - \sum_{c\in C}p(c)log_2p(c)$.
				\ei
				\item 		After seeing feature $f$: 
					\bi
						\item $H(C|f) = - \sum_{x \in f}p(x) \sum_{c in C} p(c|x) log_2p(c|x)$
					\ei
				\item 	So $InfoGain = H(C) - H(C|f)$
			\ei
		\ei
	\ei
\end{slide}
\begin{slide}{Less is more (2)}
	\bi
		\item Over-fitting avoidance
		\bi 
			\item After learning ``it'' ...
			\item ... Try throwing away bits of ``it''
		\ei
		\item e.g. RIPPER (\cite{cohen95r}),
			\bi
				\item If you learn a conjunction, prune with  greedy back select
				\item If you learn a set of rules, prune with greedy back select
				\item For the surviving rules, try replace it with..
					\bi
						\item a dumb alternative 
						\item or a carefully selected modification
					\ei
				\item Very fast: $O(m(log(m))^2)$ for $m$ examples
				\item Often produces smaller theories than other methods 
					\bi
						\item as above:

							~\\

{\scriptsize	\begin{tabular}{r@{~}l@{~}r}
            & if (rvm $\le$ 0) \& (srs = 3) &$\rightarrow$ sev=4\\
        else &if (srs $\ge$ 2)              &$\rightarrow$ sev=2 \\
        else  &                         & $\rightarrow$ sev=3\\
		\end{tabular}}
						\ei
			\ei
	\ei
\end{slide}
