The Java Implementation of the Polygonal Line Algorithm
The program generates the principal curve of arbitrary
dimensional data sets by using the
Polygonal Line
Algorithm. The software can be run as an applet by
clicking on the button above, or as an standalone
application by downloading the Java classes
(tar.gz or
zip), and executing the
PrincipalCurve.PrincipalCurveGUI class. Applets have
restricted
capabilities (e.g., no I/O), so if you want to experiment with
your own data, you have to download and run the program as an
application.
For the most serious, the source code is also
available
(tar.gz or
zip). It is free for non-commercial use, and you can
apply it to your data, modify it,
and integrate it into another program as long as you
notify me beforehand. I am not
responsible for any implications from the use of this software.
The Polygonal Line Algorithm has been extended to find "principal
graphs" of data sets, and applied to handwritten character
skeletonization
(reference). The
implementation of the Principal Graph Algorithm is available
here.
User's manual
Data
- You can download some pre-generated data sets
by using the "Sample -> Built-in samples..."
menu. You can also
access other data sets by downloading them from
here.
- You can load and download sets and curves
by using the "Sample -> Load data..."
and "Sample -> Download data..."
menus, respectively. The data files of the following
names are loaded from the selected directory:
Each file contains one point per line, and
coordinates of points are separated by
spaces. In wsample.dta, the
last number in each line is the weight of the point.
Curves are created by connecting consecutive points.
pcurve.dta can contain more than one curve. Curves are
separated by empty lines. Equal points will be unified
so principal graphs can be loaded in this way.
For a successful loading, the selected directory must contain at
least a sample.dta or a wsample.dta. If it contains a pcurve.dta, the
algorithm will be
initialized by the loaded curve/graph. Press the
"Continue"
button to start the optimization from this curve ("Start"
will
use the first principal component instead of the loaded curve/graph.)
- You can save data sets and curves
by using the "Sample -> Save data..."
menu. The
sample (sample.dta or
wsample.dta), the principal curve
(pcurve.dta), and the projection points of the sample points to the
principal curve (project.dta) in the order of the sample points will be saved in the
selected directory using the format described above.
- You can initialize the principal curve by
choosing the "Principal curve -> Initialize curve..."
menu.
You can draw a curve in the current
projection plane using the following
"extended xfig polyline protocol".
- Start a new curve by a left click,
add new vertices
by left clicks, and finish the single curve
with a middle click.
- Repeat the procedure for additional curves, and
finish the set of curves with a right click.
Any two vertices within a distance of two pixels
will be unified.
- To clear the canvas, simply finish with a right click,
and start drawing a new set of curves.
- If you want to see the coordinates of the added vertices, turn on the
"Coordinate balloon"
checkbox.
- Press "Done"
when the curve is ready.
Running
- You can run the entire
algorithm
by clicking on the "Start"
button. You can
go step by step by using the "Init"
,
"Inner step"
, "Outer step"
, and "Add vertex"
buttons.
You can switch between automatic and manual
modes by using the "Stop"
and the "Continue"
buttons.
- You can adjust the parameters of the
algorithm
by choosing the "Principal curve -> Parameters..."
menu.
The role of the parameters are described
here and
here. The following is a short
summary.
- The "penalty coefficient"
determines the trade-off between "closeness"
to the data and "smoothness" of the curve. The larger the coefficient, the
smoother the curve is.
- The "length penalty coefficient at end segments"
determines how much we penalize
the length of end-segments compared to the angle penalty at inner segments. The larger
the coefficient, the shorter the end-segments are.
- The "terminating condition coefficient"
determines when the algorithm
stops adding vertices if "Add one vertex"
or
"Add midpoints to all segments"
is selected. The larger the coefficient,
the more vertices are added.
- The "maximum segment length"
determines when the algorithm
stops adding vertices if
"Add midpoints to the longest segment"
is selected. The larger the length,
the fewer vertices are added.
- The "optimization threshold"
determines when the inner loop would stop
optimizing the curve. The larger the threshold, the faster the algorithm is.
- You can choose the policy of adding new vertices by selecting the
corresponding option. Note that vertices are deleted if neither any of the incident
edges, nor the vertex itself has data points projecting to it. So, if the terminating
thresholds are two small, the algorithm can get into an infinite loop which can be
only terminated by clicking on the "Stop"
button.
- You can follow the numerical results (objective function, MSE, penalty)
by choosing the "Principal curve -> Diagnosis"
menu.
Display (appearance)
- The center panel displays the data points and the principal curves generated by the
different
algorithms.
The initial colors are:
- Data Points
- Generator curve
- Hastie-Stuetzle curve (if available)
- Banfield-Raftery curve (if available)
- The polygonal principal curve
You can modify the sizes, colors and types of the different points and curves
by choosing the "Appearance -> Colors & sizes..."
menu.
- Choose the "Appearance -> Pack"
menu if you want to equalize the horizontal and vertical
scales after resizing
the window. (If your window is too small, you might have to
click twice.)
- You can connect the data points to their projections by
turning on the "Appearance -> Connect to projection"
checkbox.
-
You can change the projection plane onto which the points and curves
are projected (for displaying them in 2D) by choosing the "Appearance -> Projection plane..."
menu. This feature is useful for more than two (but not too high) dimensional data.
The plane is represented by three vectors: the "Origin"
(a point in the plane), the
"X axis"
, and the "Y axis"
(the coordinate axes). The vectors can be
changed manually, or by clicking to the "Reset"
button (the projection
plane is spanned by the first two coordinates, origin = 0) or to the "First 2 PC's"
button (the projection plane is spanned by the first two principal component lines of a
randomly chosen 100 data points, origin = center of gravity of the same sample). To keep the
two axes orthogonal/normalized, turn on the corresponding checkboxes.
To change the projection plane "offline", turn off the
"Repaint"
checkbox (for large
and high-dimensional data the rendering can be slow).
- You can save the displayed image directly into a postscript file by
choosing the "Sample -> Save image..."
menu. The properties of the postscript image are
determined by the colors, sizes, and types of the points and curves. Other properties
can be set in the upcoming dialog.
Known bugs
- Under SunOS and Solaris, Netscape 3.x and and 4.x seem
to have problems with the applet. Try Netscape 2.x.
The standalone application runs fine.
- Under Windows 98, Internet Explorer seems to run the applet much faster than Netscape.
- Under Linux you need at least Java 1.1.