\section{Data Mining with Collars and Clumps}

%\begin{table}
%\center
%\caption{Experts Comprehension of Others' Models}

%\begin{tabular}{|c|c|c|} \hline
%Expert Pairs&Understanding&Agreement\\ \hline
%Expert \#1 and \#2&62.5& 33.3\\
%Expert \#2 and \#1& 61.1& 26.7\\ \hline
%Expert \#1 and \#3&31.2& 8.3\\
%Expert \#3 and \#1& 42.9& 33.3\\ \hline
%Expert \#2 and \#3&44.4& 20.0\\
%Expert \#3 and \#2& 71.4& 33.3\\ \hline
%\end{tabular}
%\label{shawTable1}
%\end{table}
%
%In a similar vein, Shaw reports an experiment in which a group of geological experts built models for the
%same domain.    Twelve weeks later they reviewed each other's knowledge bases as well as their own
%\cite{shaw88}.   These research found that experts disagree significantly with each
%other \cite{shaw88}.  (See table \ref{shawTable1}.)  More surprisingly, they found that, after twelve weeks, an expert's understandability of his/her own knowledge base and even his/her agreement with it were considerably less than total. (See table \ref{shawTable2}.) 
%
%\begin{table}
%\center
%\caption{Experts Comprehension of Their Own Models}
%\begin{tabular}{|c|c|c|} \hline
%Expert&Understanding&Agreement\\ \hline
%Expert \#1&62.5&81.2\\ \hline
%Expert \#2&77.8&94.4\\ \hline
%Expert \#3&85.7&78.6\\ \hline
%
%\end{tabular}
%\label{shawTable2}
%\end{table}

%These examples suggest that humans have considerable difficulty
%comprehending model, even an apparently simple one.
%When manual methods fail, search-based SE can serve as an automatic agent to
%find the subtleties missed by a manual analysis.
%AI
%techniques have proven useful at exploration of such models to
%provide insights that humans are not able to see.  One rising area
%of AI applied to software engineering that has proven its effectiveness
%are those techniques that are described as \emph{search-based
%software engineering.}  We describe these techniques next.
%
%These examples motivate a belief that running and watching modes
%is not enough to understand them. Instead, model comprehension is
%best conducted by teams of   human and artificial intelligences
%working together to understand a domain. In our view, humans are
%best at painting the "whole" story, the big picture, defining the
%model, specifying the range of permissible values, perhaps along
%with some biases about which values are most likely or most
%improbable. Artificial intelligence (AI) techniques and tools are
%good at filling in the "holes"; i.e., all the details that humans
%routinely miss.  
%



%%%% Jim -- Could the ranges of this figure (fig. 2) be labeled with the 
%treatment so that it is more understandable?

%%%% Tim -- hell, why not just delete the figure altogether. it dont add much

\PARstart{T}he TAR2 {\em treatment learner}~\cite{me03e} is a data miner that is specialized
for generating models containing only collar variables.
TAR2 finds the difference between
classes. Formally, the algorithm is a {\em contrast set
learner}~\cite{bay99,webb03} that uses {\em weighted
classes}~\cite{cai98} to steer the inference towards the preferred
behavior. We call TAR2's output ``treatments''  since the minimal
rules generated by the algorithm are similar to medical treatment policies
that try to achieve the most benefit, with the least intervention.
The core intuition of TAR2 is that it is unnecessary to search for the collars--
they will reveal themselves after some limited random sampling. To
see that, recall that collar variables control the settings in the rest
of the system. Any execution trace that reaches
a goal must pass through the collars (by definition). 
Therefore, to find the collars, all an algorithm needs to do is find
the attribute ranges with very different frequencies in traces that
reach different goals.

Detecting collars via this sampling method is very simple to
implement.
Consider a log of golf
playing behavior shown in \fig{golfdata}. This log contains four
attributes (outlook, temperature, humidity, wind) and 3 classes (none, some, lots) that convey the
amount of golf played. 
We recommend an exponential
scoring system for the classes,
starting at two\footnote{If the weights run, say, \{bad=0,ok=1,good=2\}
then the difference from  
{\em bad} to {\em ok} scores the same as {\em ok} to {\em good}.
An exponentially weighting scheme, starting at two, 
finds greater and greater rewards moving to better classes. For further
details, see~\cite{hu02}.}.
For example, our golfer could weight the
classes in \fig{golfdata} 
as  {\em none=2} (worst),  {\em some=4}, {\em lots=8} (best).

TAR2  seeks attribute ranges that occur frequently in the
highly weighted classes and rare in the lower weighted classes. Let $a.r$
be some attribute range e.g. {\em outlook.overcast} means that the outlook is for overcast skies.
$\Delta_{a.r}$ is a heuristic measure of the worth of $a.r$ to
improve the frequency of the $best$ class. $\Delta_{a.r}$ uses the
following definitions:
\begin{description}
\item[$X(a.r)$:] ~~~is the number of occurrences of that attribute
range in class $X$; e.g. in this data {\em lots(outlook.sunny)=2} since there are 
2 cases with outlook = {\em sunny} and class = {\em lots}.
\item[$all(a.r)$:] ~~~is the total number of occurrences of that
attribute range in all classes; e.g. {\em
all(outlook.sunny)=5}. \item[$best$:]  the highest scoring
class; e.g. $best=lots$; \item[$rest$:]   the non-best class; e.g.
$rest=\{none,some\}$; \item[$weight$:] ~~ The weight of a class $X$ is symbolized by
$\$X$;. (Thus, $\$best = 8$.)\end{description}
 $\Delta_{a.r}$ is
calculated as follows:

{\footnotesize
\[
\Delta_{a.r}=\frac{\sum_{X{\in}rest}(\$best-\$X)*
(best(a.r)-X(a.r))}{all(a.r)}
\]
}{\noindent}When {\em a.r} is {\em outlook.overcast}, then
$\Delta_{outlook.overcast}$ is calculated as follows:
\[\frac{\overbrace{((8-2)*(4-0))}^{lots \rightarrow none}+\overbrace{((8-4)*(4-0))}^{lots \rightarrow some}}{4+0+0}=\frac{40}{4}=10
\]

%\noindent The attribute ranges in our golf example generate the
%$\Delta$ histogram shown in \fig{dels}. Note that {\em
%outlook=overcast}'s $\Delta$ is the highest, potentially most
%effective, attribute range.

%-----------------------------------
% deltaf distribution of Golf data
%-----------------------------------


\begin{figure}
\renewcommand{\baselinestretch}{1}
{\small {\em
\begin{center}
\begin{tabular}{rccccl}
outlook & temp($^o$F) &  humidity & windy? & class & weight
\\\hline
sunny&  85&     86&     false&  none & 2\\
sunny&     80&     90&     true&   none& 2\\
sunny&     72&     95&     false&  none& 2\\
rain&  65&     70&     true&         none&  2\\
rain&        71&     96&     true&   none& 2\\\hline
      rain&         70&     96&     false&      some &4\\
      rain&      68&     80&     false&      some & 4\\
      rain&      75&     80&     false&  some & 4\\\hline
      sunny&    69&     70&     false&  lots &8\\
      sunny&    75&     70&     true&   lots&8\\
      overcast&  83&     88&     false&  lots&8\\
      overcast&  64&     65&     true&   lots&8\\
      overcast&  72&     90&     true&   lots&8\\
     overcast&  81&     75&     false&  lots&8\\\hline
\end{tabular}\end{center}}}
\caption{A log of some golf-playing behavior.}
\label{fig:golfdata}
\end{figure}
%-----------------------------------
% treatment of Golf data
%-----------------------------------
%\begin{figure}
%\begin{center}
%{\small
%\begin{tabular}{c}
%\begin{barenv}
%\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
% \setstretch{8}\sethspace{0.5} \setyaxis{0}{3}{1}
%\setxaxis{-5}{10}{1}
% \bar{0}{8} % -5
% \bar{1}{1} %-4
% \bar{0}{8} % -3
% \bar{0}{8} % -2
% \bar{1}{1}  % -1
%  \bar{3}{1} % 0
%  \bar{3}{1} % 1
%\bar{2}{1} % 2
% \bar{0}{8} %3
%\bar{0}{8} %4
%\bar{1}{8} %5
%\bar{1}{8} %6
%\bar{0}{8} %7
%\bar{0}{8} %8
%\bar{0}{8} %9
%\bar{1}{8} %10
%\end{barenv}
%\end{tabular}
%}
%\end{center}
%\caption{$\Delta$ distribution from \fig{golfdata}.
%High $\Delta$ values are shown in black. Y-axis is the
%number of attribute ranges that have a particular $\Delta$.}
%\label{fig:dels}
%\end{figure}
%


To {\em build} a treatment,
TAR2 explores combinations of attribute ranges up to some user-specified
maximum size $s$ (where the size $s$ is
the number of attribute ranges in  a
conjunction of attributes). Given $n$ attributes,
the size of this search is  
$\frac{n!}{s! (n - s)!}$.
To make this search feasible, TAR2 must keep $s$ small.
Therefore, TAR2 first assesses each
attribute range, in isolation, i.e., with s = 1. A preliminary pass
builds one singleton
treatment for each attribute range.  The attribute ranges are then
scored by the $\Delta$ of these singleton treatments.  Treatment
generation is constrained to just the attribute ranges with a score
greater than a user-supplied threshold (default value= 1; maximum
useful value yet found= 7). 
%In \fig{dels}, this corresponds to 
%constraining
%treatment generation to only the right-hand-side attribute ranges.
%%%% Jim --is "right-hand-side" meaningful here?  Perhaps, "larger than the threshold" is better?

\begin{figure}
\renewcommand{\baselinestretch}{1}
\begin{minipage}{.70\linewidth}
{\small\begin{center}
\begin{tabular}{p{1.1in}p{1.1in}l}
$no\; change$  & $outlook=\newline
overcast$\\~\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
     \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{5}{1}
 \bar{3}{4}
 \bar{6}{8}
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{0}{1} \bar{0}{4} \bar{4}{8}
\end{barenv}
\end{tabular}
\end{center}
}\end{minipage}\hfill
\begin{minipage}{.3\linewidth}
\begin{raggedleft}
{\scriptsize
\begin{tabular}{r@{}l}
\protect\legend1{~}&\begin{raggedright}= none
(worst)\end{raggedright}
\\
\protect\legend4{~}&\begin{raggedright}= some\end{raggedright}\\
\protect\legend8{~}&\begin{raggedright}= lots
(best)\end{raggedright}
\end{tabular}}
\end{raggedleft}
\end{minipage}
\caption{Finding treatments that can improve golf playing
behavior. With no treatments, we only play lots of golf in
$\frac{6}{5+3+6}= 57\%$ of cases. However, assuming
{\em
outlook=overcast}, we play golf lots of times in 100\% of
cases. } \label{fig:golft}
\end{figure}

\begin{figure}
\renewcommand{\baselinestretch}{1}
{\small
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|} \cline{3-4}
\multicolumn{2}{c}{}&\multicolumn{2}{|c|}{\# columns}\\\hline
 domain & \# rows & \begin{sideways}\# numeric\end{sideways} & \begin{sideways}\# discrete\end{sideways} & \#class  & time(sec) \\\hline
iris & 150 & 4 & 0 & 3 & $<1$ \\\hline 
wine & 178 & 13 & 0 & 3 & $<1$ \\\hline 
car & 1,728 & 0 & 6 & 4  & $<1$ \\\hline
autompg & 398 & 6 & 1 & 4  & 1 \\\hline 
housing & 506 & 13 & 0 & 4  & 1 \\\hline
 pageblocks & 5,473 & 10 & 0 & 5  & 2 \\\hline
cocomo & 30,000 & 0 & 23 & 4  & 2 \\\hline 
reacheness & 25,000 & 4 & 9 & 4  & 3 \\\hline 
circuit & 35,228 & 0 & 18 & 10  & 4 \\\hline 
reacheness2 & 250,000 & 4 & 9 & 4  & 23 \\\hline
pilot & 30,000 & 0 & 99 & 9  & 86 \\\hline
\end{tabular}
\end{center}}
\caption{Runtimes for TAR2 on different domains. First 6 data sets
come from the UC Irvine machine learning data 
repository~\cite{Blake+Merz:1998};
``cocomo'' comes from a COCOMO software cost estimation model
\cite{me00e}; ``pilot'' comes from the NASA Jet Propulsion
Laboratory \cite{fea02a}.}\label{fig:runtime}
\end{figure}

%\subsection{Weighted Contrast Set Learning}
%
%Due to the limitations of tree-based learning,
%numerous researchers have explored
%other methods including: \begin{itemize} \item Association
%rule learners, e.g. 
%APRIORI~\cite{agrawal94};
%\item Weighted class learner,  e.g. MINWAL~\cite{cai98};
%\item Contrast set learning, e.g. STUCCO~\cite{bay99};
%\item Weighted contrast set learning, e.g. TAR2~\cite{me03c};
%\end{itemize}
%
%Association rule learners 
%seek
%attribute values that commonly
%occur together in a learning set.  If $LHS$ and $RHS$
%are set of attributes with $LHS \cap RHS = \emptyset$, a rule ($LHS \rightarrow RHS$)
%describes the set of examples in which $LHS$ and $RHS$ both appear.  For
%example, in a set of data about student behavior and grades, we
%might find that many times when the \emph{GradeA} then
%\emph{Study=EveryDay}.
%In \fig{gradesTable}, there are four rows with this association.
%\begin{figure}
%\center\scriptsize
%\begin{tabular}{|c|c|c|c|c|c|} \hline
%Student&Sleep&Study&VideoGames&Exercise&Grade\\ \hline
%1&Much&EveryDay&Some&Some&A\\ \hline
%2&Little&BeforeTest&None&Little&B\\ \hline
%3&Average&EveryDay&None&None&A\\ \hline
%4&Average&None&Much&Little&C\\ \hline
%5&Average&BeforeTest&Some&Some&C\\ \hline
%6&Much&BeforeTest&None&Some&A\\ \hline
%7&Much&Little&None&Some&B\\ \hline
%8&Average&None&Much&None&D\\ \hline
%9&Little&None&Much&Little&D\\ \hline
%10&Little&EveryDay&Much&None&C\\ \hline
%11&Average&EveryDay&None&Much&A\\ \hline
%12&Average&Little&Some&Some&C\\ \hline
%13&Little&Little&None&Much&C\\ \hline
%14&Little&EveryDay&Much&Much&A\\ \hline
%15&Little&None&Some&Some&D\\ \hline
%16&Little&Little&Much&None&C\\ \hline
%17&Average&Little&None&Much&D\\ \hline
%18&Average&BeforeTest&Some&None&B\\ \hline
%19&Average&BeforeTest&None&Some&B\\ \hline
%20&Some&BeforeTest&None&Some&A\\ \hline
%\end{tabular}
%\caption{Observations of Grades and Behavior Data of Students}
%\label{Some student grades.}\label{fig:grades}
%\end{figure}
%
%We say that the rule ($LHS \rightarrow RHS$) holds with confidence \emph{c} if
%\emph{c} percent of the examples in the learning set \emph{L} that
%contain $LHS$ also contain $RHS$.  For example, the rule
%$Grade=A \rightarrow Study=EveryData$ has the confidence 
%0.67
%since \[c = \frac {| Examples _{LHS} \cap Examples _{RHS} |}{ | Examples
%_{LHS } |} = \frac{4}{6}=0.67\]
%Also,
%a rule ($LHS \rightarrow RHS$) has \emph{support} \emph{s},
%if \emph{s} percent of all of the learning examples support this
%rule.  That is: \\
%\[s = \frac{ | Examples _{LHS} \cap Examples _{RHS} |} {  | L | }\]
%In assessing the utility of various associations, we prefer those
%with higher \emph{confidence} which is a a measure of the strength
%of this association. However, we temper this selection with the
%\emph{support}.  An association with low \emph{support} is one that
%does a poor job of selecting desired outcomes from the learning set
%(and presumably from a larger set).
%The rule
%$Grade=A \rightarrow Study=EveryData$ had adequate confidence
%($c=0.67$) but low support ($s=\frac{4}{20}=0.2$).
%
%A \emph{weighted class learner} is an association rule learner that
%focuses the learning on issues of interest to a particular stake-holder
%by the assignments of weights to certain classes.  
%Thus, in addition to assessing the value of associations with
%\emph{confidence} and \emph{support}, we value those that lead us
%to certain weighted outcomes.  Of course, these weights may vary
%from stake-holder to stake-holder.
%\emph{Contrast set learning} is another variant of association rule
%learning.  The fundamental feature of a contrast set learner is the
%search for rules that differ in their distribution across groups.
%
%
%
%
%\subsection{TAR2}
%In the language of the last section,
%TAR2 is a minimal weighted
%contrast set learner.  This tool is based on two concepts: \emph{lift} and \emph{best support}.  These concepts both are used to choose among all of the possible \emph{treatments}.  A treatment is a set of attribute choices.  \emph{Lift} is a measure of how well a particular treatment selects desired outcomes as compared to the number of outcomes in the entire learning set.  (This is analogous to the concept of \emph{confidence} discussed above.  \emph{Best support} is analogous to the concept of \emph{support}.    We illustrate these concepts with the following example.
%
%The data in Table \ref{gradesTable} gives a hypothetical report of an observation of the behavior of 20 students, and their grades.  The problem is to learn from this model behaviors that are likely to lead to success as measured in course grades.  We want to mine this data by searching for patterns of behavior that are successful ones.  Here we consider two separate \emph{treatments} form the data from this table, both of which have the effect of producing good grades.  \\ 
%
%Treatment \#1: study = ``Every Day" \par
%Treatment \#2: study = ``Before Test" $\wedge$ \par Video Games = ``None" $\wedge $ Exercise = ``Some" \par
%
%The application of Treatment \#1 results in then selection of five rows of data: four resulting in a grade of A and 1 resulting in a grade of C.  Treatment \#2 selects three rows, two resulting in A, one in a B grade.  To calculate the \emph{lift} of each of these, we first calculate the \emph{baseline} value that includes all of the data.  We assign the typical grade point averages to these grades: A = 4.0, B = 3.0, C = 2.0, D = 1.0.  (There is no reason that we are constrained to these particular values except by convention.  In fact, the treatment learning algorithm would work better if we assigned much higher values to the desired outcome values.)  Note that, in the data of Table \ref{gradesTable}, there are six rows with a grade of A, 4 with a grade of B, 6 with C, and 4 with D. Here is the baseline calculation: \\ \\
%$value(baseline) = \frac{\frac{6}{20}*4.0 + \frac{4}{20}*3.0 + \frac{6}{20}*2.0 + \frac{4}{20}*1.0} {4.0 + 3.0 + 2.0 + 1.0} = 0.26$ \\ \\
%For Treatment \#1, we first calculate the weighted value of that treatment, then the \emph{lift} which is the ration of this treatment's weighted value to that of the baseline. \\ \\
%$value( study = ``Every Day" )\\ =  \frac{\frac{4}{5}*4.0 + \frac{0}{5}*3.0 + \frac{1}{5}*2.0 + \frac{0}{5}*1.0} {4.0 + 3.0 + 2.0 + 1.0} = \frac{18}{50} = 0.36$\\ \\
%$Lift(study = ``Every Day" ) = 0.36 / 0.26 \approx 1.385$\\
%
%For Treatment \#2, the analogous calculations are as follows:
%value( study  =  ``Before Test"  $\wedge$ Video Games = ``None" $\wedge $ Exercise = ``Some" )\\ =  $\frac{\frac{2}{3}*4.0 + \frac{1}{3}*3.0 + \frac{0}{3}*2.0 + \frac{0}{3}*1.0} {4.0 + 3.0 + 2.0 + 1.0} = \frac{11}{30} \approx 0.367$\\ \\
%Lift( study = ``Before Test" $\wedge$ Video Games = ``None" \\ $\wedge $ Exercise = ``Some" ) =  $0.367 / 0.26 \approx 1.41$\\
%
%Thus, both treatments appear to have a positive effect.  Numerically, Treatment \#2 appears to be preferred.  However, our intuition tells us that Treatment \#1 is much better than Treatment \#2 since it is much simpler and has a greater effect in producing 4 A's versus the 2 produced by Treatment \#2.  Tar2 incorporates this latter intuition through its evaluation of treatment preference by using \emph{best support}.   That is, Tar2 requires that a treatment produce adequate support for the desired outcome.  If a treatment does not, then it is rejected.  This allows Tar2 to avoid the problem of \emph{over learning}.
%
%Consider the \emph{best support} of these two treatments.  Treatment \#1 found 4 of the 6 best outcomes in this data for a \emph{best support} of 4/6 = 0.67; Treatment \#2 has a \emph{best support} value of 2/6 = 0.33.  Tar2 rejects any treatment whose best support is less than its \emph{minimum best support level}.  (The default for this value in Tar2 is 0.1.  However, this is user configurable, and with this small data set a more reasonable value would be 0.5)
%
%Note that a side effect of a using the \emph{best support} value is that treatments tend to consist of fewer attribute.  The more tests that are included in a treatment, the more examples from the learning set that are rejected.  This, in turn, lowers the \emph{best support} value.  Learning very specific treatments is a common problem of learning algorithms that is called \emph{over-learning}.
%
%Discuss the efficiency of TAR2 algorithm here
%
%\subsection{Combination of Saturation Effect and Contrast Set Learning}
%In a previous section, we have described a \emph{saturation effect} that is present in many SE models.  These are models whose internal structure is typified by a few dominant parameters among a much larger collection of parameters.  We can think of these as control and dependent parameters.  The strength of contrast set learning is in finding a small number of factors (treatments) that are the most effective at driving a search to solutions that are desired outcomes.  Please note the synergy in the combination of saturation effect and contrast set learning.  When a model displays a saturation effect, contrast set learning is an efficient algorithm for find the control variables.
%
%

To {\em apply}  a treatment,   TAR2 rejects all example entries
that contradict the conjunction of the attribute ranges in the
treatment. E.g., if the treatment was 
\mbox{$ humidity \ge 85 \wedge windy = true$}, then 11 of the 
lines of \fig{golfdata} would be rejected.  The ratio of classes in the remaining examples is
compared to the ratio of classes in the original example set  (in the humidity and wind treatment just given, 
this ratio would be 3/14).
The 
{\em best treatment} is the one that most increases the relative
percentage of preferred classes. In our
golf example, a single  best treatment was generated containing
{\em outlook=overcast}. \fig{golft} shows the class distribution
before and after that treatment. That is, if we select a vacation location
with {\em overcast} weather,
then 
we
should be playing $lots$ of golf, all the time.

In practice, despite the 
$\frac{n!}{s! (n - s)!}$ search, TAR2 scales well.
\fig{runtime} shows TAR2's runtime 
on 11 data sets with varying numbers of rows and columns.
Running on a relatively slow machine 
(a 333 MHz Windows machine with 512MB
of ram),  TAR2 terminated
in tens of seconds, even on data sets with up to 250,000 rows, each with nearly 100 attributes.


