\section{Diagnosing Breast Cancer with a Linear Classifier}\label{S:BreastCancer}

\newpar
Breast cancer is the most common form of cancer and the second largest cause of cancer deaths among women.
In the mid-1990's a noninvasive diagnostic tool was developed that can
be described in terms of nonlinear programming.\footnote{Based upon
Mangasarian et al., \cite{Mangasarian_breastcancer}, (1994)}

\newpar
Researchers use small-gauge needles to collect fluid from both malignant and benign tumors of a large number of women. With the aid of a computer program called {\textbf{Xcyt}}, the boundaries of the cell nuclei
are analyzed and categorized with regard to a number of features, including area, perimeter,
number of concavities, fractal dimension, variance of grey scale, etc. Mean values, variance, and other
quantities for these attributes are computed, and ultimately 30 data items for each sample are
represented by a vector in $\R^{30}$.

\newpar
The set of all such vectors constitutes what is known as a ``training set.'' Our aim is to construct a \emph{hyperplane}\index{hyperplane} in $\R^{30}$, using these training vectors\index{training vectors}, that ``best separates'' the training vectors corresponding to benign tumors from those corresponding to malignant ones. This hyperplane can be used to classify, with a reasonable degree of certainty, whether a newly-collected sample corresponds to a benign or malignant tumor. Because the model consists of two-classes and a hyperplane is used to separate the data, we refer to this prediction model as a \emph{linear classifier}\index{linear classifier}. Figure \ref{Fi:linear_classifier_image} illustrates a simplified version of this concept using 20 training vectors in $\R^2$, 10 of each type, in which case the hyperplane is merely a line.

\begin{figure}[h]
\centering
\psfrag{P}[Bc][Bc]{$\vecn^t\vecx+d=0$}
\psfrag{P1}[Bc][Bc]{$\vecn^t\vecx+d=\epsilon$}
\psfrag{P2}[Bc][Bc]{$\vecn^t\vecx-d=-\epsilon$}
\includegraphics[width=.7\linewidth]{images/linear_classifier_image.eps}
\caption{Hyperplane separating two classes of training vectors (circles and boxes).}
\label{Fi:linear_classifier_image}
\end{figure}

\newpar
In this project we will construct the hyperplane by means of solving a constrained nonlinear programming
problem. For the sake of simplicity and in order to visualize the underlying ideas better, we use 20 data vectors in $\R^3$ instead of $\R^{30}$. These vectors are expressed as ordered triples in Table \ref{Ta:BreaseCancerDataSet}. To the training vector, $\vecx_i$, where $1 \leq i \leq 20$, we associate a value $y_i \in
\left\{-1,1 \right\}$,
where $y_i=1$ (resp. $y_i=-1$) if that training vector corresponds a benign (resp. malignant) tumor.

\begin{table}[h]
\centering
\caption{Training set}
\label{Ta:BreaseCancerDataSet}
\begin{tabular}{|c|c|c|}
\hline
$i$ & Training Vector, $\vecx_i$ & $y_i$ \\
\hline \hline
$1$ & $(7.04, 6.52, 24.4)$  & $1$ \\
$2$ &  $(9.57,4.42,23.6)$  & $1$ \\
$3$ &  $(7.00,8.30,32.3)$  & $1$ \\
$4$ &  $(7.02,6.57, 26.5)$  & $1$ \\
$5$ &  $(8.48, 3.62, 17.3)$  & $1$ \\
$6$ &  $(7.7,5.98, 25.5)$  & $1$ \\
$7$ &  $(7.86,5.57,23.7)$  & $1$ \\
$8$ &  $(10.1, 5.97, 31.7)$  & $1$ \\
$9$ &  $(5.10,5.82,15.8)$  & $1$ \\
$10$ &  $(9.14, 5.60,28.7)$  & $1$ \\
$11$ &  $(9.12,7.33,29.7)$  & $-1$ \\
$12$ &  $(7.29,6.03,18.9)$  &  $-1$ \\
$13$ &  $(7.78,7.65, 26.3)$  &  $-1$ \\
$14$ &  $(7.92,6.67,27)$  &  $-1$ \\
$15$ &  $(7.69,5.37,19.6)$  &  $-1$ \\
$16$ &  $(8.54,5.33,21.8)$  &  $-1$ \\
$17$ &  $(9.43,4.85,21)$  &  $-1$ \\
$18$ &  $(6.97,5.09,15.9)$  &  $-1$ \\
$19$ &  $(6.97,5.7,17)$  &  $-1$ \\
$20$ &  $(9.26,2.84,14.4)$  &  $-1$ \\
\hline
\end{tabular}
\end{table}


\newpar
In $\R^3$ the hyperplane takes the form $n_1x_1+n_2x_2+n_3x_3+d=0$ for some
yet-to-be-determined real quantities, $n_1$, $n_2$, $n_3$, and $d$. If we write
$\ds \vecn=\begin{bmatrix} n_1 \\ n_2 \\ n_3 \end{bmatrix}$ (the normal vector) and
$\ds \vecx=\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}$, this equation
is identical to $\vecn^t \vecx+d=0$.

\newpar
Ideally all malignant tumor vectors fall on one side of this plane and all benign
vectors fall on the other. In this case, there
exists some positive constant $\epsilon$ such that
$\vecn^t \vecx_i+d \geq \epsilon$ for $1 \leq i \leq 10$ and
$\vecn^t \vecx_i+d \leq -\epsilon$ for $11 \leq i \leq 20$. We can think of $\epsilon$
as the smallest possible distance between any of the training vectors and the desired plane.
It determines two new planes, $\vecn^t \vecx +d = \epsilon$ and
$\vecn^t \vecx +d = -\epsilon$, as depicted in Figure \ref{Fi:linear_classifier_image}.
The plane $\vecn^t \vecx +d = 0$, separates these two new planes and is a distance $\epsilon$ from
each.

\newpar
Since $y_i=1$ for $1 \leq i \leq 10$ and $y_i=-1$ for $11 \leq i \leq 20$, the preceding two families
of inequalities
may be combined into one and written as
\begin{equation}\label{E:breast_cancer_vector_inequalities}
   y_i \left( \vecn^t \vecx_i + d \right) \geq \epsilon \quad \mbox{ for $1 \leq i \leq 20$.}
\end{equation}

\noi
Of course, by scaling $\vecn$ and $d$ by $\ds \frac{1}{\epsilon}$ if necessary, we may rewrite
(\ref{E:breast_cancer_vector_inequalities}) as follows:
\begin{equation}\label{E:breast_cancer_vector_inequalities2}
   y_i \left( \vecn^t \vecx_i + d \right) \geq 1 \quad \mbox{ where $1 \leq i \leq 20$.}
\end{equation}

\noi
Thus, the three planes
in Figure \ref{Fi:linear_classifier_image} can be expressed as
$\vecn^t \vecx +d=-1$, $\vecn^t \vecx +d=0$, and $\vecn^t \vecx +d=1$.

\be
\item
\item The \emph{margin} is defined to be distance between the two planes,
$\vecn^t \vecx+d=1$ and $\vecn^t \vecx +d =-1$. Because $d$ merely denotes a translation,
the margin is the same as the distance between $\vecn^t \vecx=1$ and $\vecn^t \vecx=-1$.
It is this quantity that we see to maximize, or
equivalently, its reciprocal that we seek to minimize.
Show that the margin equals $\ds \frac{2}{\|\vecn \|}$. (Hint: Choose arbitrary vectors, $\vecx_1$ and $\vecx_2$,
that satisfy $\vecn^t \vecx_1=1$ and $\vecn^t \vecx_2=-1$. Then determine the orthogonal
projection of $\vecx_2-\vecx_1$ onto $\vecn$. The magnitude of this projection is the
distance between the two planes.)

\newpar
It is very unlikely that we can determine a plane that completely ``separates'' the benign
training vectors from the malignant ones, in which case the constraints
\begin{equation}\label{E:breast_cancer_scaled_vector_inequalities}
   y_i \left( \vecn^t \vecx_i + d \right) \geq 1 \quad \mbox{ for $1 \leq i \leq 20$.}
\end{equation}
lead to an infeasible NLP. To address
this problem, we relax each constraint and rewrite (\ref{E:breast_cancer_scaled_vector_inequalities})
as
\begin{equation}\label{E:breast_cancer_scaled_vector_inequalities_with_errors}
   y_i \left( \vecn^t \vecx_i + d \right) \geq 1 - \delta_i \quad \mbox{ for $1 \leq i \leq 20$,}
\end{equation}
where $\delta_i \geq 0$ denotes the amount
of violation in constraint $i$. The family,
$\ds \left\{\delta_i \mid 1 \leq i \leq 20 \right\}$, together with $d$ and the components of $\vecn$, then leads to a total of 24 decision variables for this model, 20 of which we
require to be nonnegative.

\newpar
Of course, we must ensure the total penalty violation is as small as possible.

\item Construct a penalty function\index{penalty function} that is large if the total constraint violation is large.

\item Use Maple to solve the NLP that arises by minimizing the sum of
$\ds \frac{\|\vecn \|}{2}$ and the penalty function, subject to the constraints
in (\ref{E:breast_cancer_scaled_vector_inequalities_with_errors}) together with
the sign
restrictions $\delta_i \geq 0$ for $i=1,2,\ldots,20$.

\item The solution to your NLP determines the equation of the desired plane. Use Maple to
plot this plane, together with the training vectors. To do this, create two \mf{pointplot3d}
structures, one for each of the two vector types. (Specifying different symbols, e.g.,
\mf{symbol=solidcircle} and \mf{symbol=solidbox} for the two plots
will highlight the difference between the two training vector types.) Then create a third
plot structure, this one producing the separating plane. Combine all three plot structures
with the \mf{display} command.

\item Suppose two new sample vectors are given by
$\ds \vecv_1=\begin{bmatrix} 10.1 \\5.97 \\ 31.7 \end{bmatrix}$ and
$\ds \vecv_1=\begin{bmatrix} 8.54 \\5.33 \\ 21.8 \end{bmatrix}$. Use your newly-constructed linear
classifier,
$f:\R^3 \to \R$ given by $\ds f(\vecx)=\vecn^t\vecx+d$, to classify each
 of $\vecv_1$ and $\vecv_2$  as corresponding to benign or malignant vector type.

\ee

