\input{/home/sc/yip/cs201-macro.tex}
\input{psfig}

\setlength{\textwidth}{6.25 in}
%\setlength{\textheight}{9.0 in}
\setlength{\topmargin}{-.6 in}


\begin{document} 
\pagestyle{empty}

\psetheader{Fall Semester, 1996}{Practice Problems -- Oct 31, 1996}

\leftbold{Problem: Nearest Neighbor}

In this question you are asked to explore the decision regions
produced by the nearest neighbor (NN) algorithm for classification
problems.

We use the following training set about allergic reactions to mammals'
milk.  For simplicity, we consider only two attributes of the milk:
the fat and lactose content per serving:
        
\begin{center}
\begin{tabular}{|cc|c|} \hline
 fat & lactose & allergic?\\ \hline
 1.0 &  6.9 & yes\\
 3.4 & 6.8 & no\\
 6.4 & 4.7 & yes \\
 5.1 & 3.7 & no \\
 7.2 & 2.7 & yes \\ \hline
\end{tabular}
\end{center}

For your convenience, a plot of these 5 training cases appears below. 
The horizontal axis is the fat content and the vertical is lactose.
For this problem, we will assume the distance metric is the standard
euclidean distance.

\centerline{\psfig{figure=/homes/yip/6034/1995/nn.data.plot,height=4in}}

\clearpage

\subproblem{}

You are given below a catalog of possible ``decision regions'' in the
feature space (fat,lactose) associated with the samples stored by the
nearest neighbor algorithm.  Each region is made up of all
points in the feature space that are closest to one of the stored
samples.  Within each region, the class ``decision'' made by the
algorithm is the same, namely the class of the sample in that region.

\bigskip

\centerline{\psfig{figure=/homes/yip/6034/1995/nn-regions.ps,height=5in,width=5in}}


Assume the data given above is presented to NN in the order given
above.  Pick a region diagram that is consistent with the samples
stored by NN, and SHADE the regions corresponding to positive allergic
reactions.  If you think none of the diagrams in the catalog is
consistent with the algorithm, write NONE in the answer box.

Answer: \onebox{.5in}{.3in}

\clearpage

\subproblem{}

Suppose the training cases are presented in a different order.  In
general, how 
does a change in the order of presentation affect the number and shape
of the decision regions?  To save writing, use the following answer
keys:

        A = no change \\
        B = change in the number of the decision regions only\\
        C = change in the shape of the decision regions only\\
        D = change in both the number and shape of the decision regions\\

Answer: \onebox{.5in}{.3in}


\subproblem{}

Suppose the fat and lactose attributes are normalized so that their
training sample variances are both equal to 1. How does the rescaling
affect the number and shape of the decision regions?  Use the same
answer keys in part B. 


Answer: \onebox{.5in}{.3in}

\clearpage

\leftbold{Problem: Identification Tree}

Consider the following data set about allergic reactions to
different kinds of food eaten on seven consecutive days:

\begin{tabular}{|c|c|c|c|c|c|c|c|}
Day & Apple & Beef & Cake & Date & Egg & Reaction? \\ \hline
1  & yes & yes & yes & yes & yes & yes \\
2  & no & yes & yes & yes & no & no \\
3  & yes & yes & no & yes & no & yes \\
4  & yes & no & no & yes & no & no \\
5  & yes & yes & yes & no & yes & yes \\
6  & yes & yes & yes & no & no & no \\
7  & no & yes & yes & yes & no & no \\
\end{tabular}

(a) Build the identification tree based on minimizing disorder.

Answer: \\ \onebox{5in}{3in}

(b) What does your tree predict for the following test case:

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
Day & Apple & Beef & Cake & Date & Egg & Reaction? \\ \hline
8  & no & yes & no & yes & yes & ? \\
\end{tabular}
\end{center}

Answer: \onebox{.5in}{.2in}

(c) Would you use the nearest-neighbor classification algorithm for
this data set?  Explain why or why not.

Answer: \\ \onebox{5in}{1in}

\end{document}