How to cite this WIREs title:
WIREs Comp Stat

Class cover catch digraphs

Advanced Review

David Marchette

Published Online: Mar 19 2010

DOI: 10.1002/wics.70

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Abstract The class cover problem is one of finding a small number of sets covering (containing) points from one class without covering any points from a second class. The class cover catch digraph provides a solution to the class cover problem, which can be extended to a nonparametric classifier, similar in flavor to a reduced nearest neighbor classifier. This article describes the class cover catch digraph and its application to classification. Copyright © 2010 John Wiley & Sons, Inc. This article is categorized under: Data: Types and Structure > Graph and Network Data

A class cover problem with n = 10 (black points) and m = 3 (red points). The catch digraph that solves the constrained class cover problem is shown, with its defining set of balls. A minimal set of balls covering all the black points and none of the red points is shown in blue.

[ Normal View | Magnified View ]

Solution ball centers chosen by the CCCD for each class, plotted in two parallel coordinates plots. On the top the axes are unscaled, on the bottom each axis is scaled independently. The axes are in the order of Table 2, with the ball radius appended as the last axis. Black corresponds to ‘normal’ and red to ‘abnormal’.

[ Normal View | Magnified View ]

An example training set for a three‐class classification problem, and the resulting decision regions defined by the class cover catch digraph classifier of Eq. (11).

[ Normal View | Magnified View ]

References

Cannon, AH, Cowen, LJ. Approximation algorithms for the class cover problem. Ann Math Artif Intell 2004, 40: 215–223.
J DeVinney., The Class Cover Problem and its Applications in Pattern Recognition. PhD thesis, The Johns Hopkins University, 2003.
Priebe, CE, DeVinney, J, Marchette, DJ. On the distribution of the domination number for random class cover catch digraphs. Stat Prob Lett 2001, 55: 239–246.
DeVinney, J, Wierman, JC. A new family of proximity graphs: Class cover catch digraphs. Discrete Appl Math 2006, 154: 1975–1982.
Ceyhan, E. The distribution of the domination number of class cover catch digraphs for non‐uniform one‐dimensional data. Discrete Math 2008, 308: 5376–5393.
DeVinney, J, Wierman, JC. A SLLN for a one‐dimensional class cover problem. Stat Prob Lett 2003, 59: 425–435.
Wierman, JC, Xiang, P. A general SLLN for the one‐dimensional class cover problem. Stat Prob Lett 2008, 78: 1110–1118.
Xiang, P, Wierman, JC. A CLT for a one‐dimensional class cover problem. Stat Prob Lett 2009, 79: 223–233.
Ceyhan, E. An Investigation of Proximity Catch Digraphs in Delaunay Tessellations. PhD thesis, The Johns Hopkins University, 2004.
Ceyhan, E, Priebe, CE. The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association. Stat Prob Lett 2005, 73: 37–50.
Ceyhan, E, Priebe, CE. On the distribution of the domination number of a new family of parameterized random digraphs. Model Assisted Stat Appl 2007, 1: 231–255.
Ceyhan, E, Priebe, CE, Wierman, JC. Relative density of the random r‐factor proximity catch digraphs for testing spatial patterns of segregation and association. Comput Stat Data Anal 2006, 50: 1925–1964.
Ceyhan, E, Priebe, CE, Marchette, DJ. A new family of random graphs for testing spatial segregation. Can J Stat 2007, 35: 27–50.
Priebe, CE, Marchette, DJ, DeVinney, J, Socolinsky, D. Classification using class cover catch digraphs. J Classification 2003, 20: 3–23.
Devroye, L, Gyrofi, L, Lugosi, G. A Probabilistic Theory of Pattern Recognition. New York: Springer; 1996.
Marchette, DJ, Priebe, CE. Characterizing the scale dimension of a high dimensional classification problem. Pattern Recogn 2003, 36: 45–60.
DeVinney, J, Priebe, CE, Marchette, DJ, Socolinsky, D. Random walks and catch digraphs in classification. Comput Sci Stat 2002, 34: 107–117.
Marchette, DJ. Random Graphs for Statistical Pattern Recognition. New York: John Wiley %26 Sons; 2004.
Eveland, CK, Socolinsky, DA, Priebe, CE, Marchette, DJ. A hierarchical methodology for one‐class problems with skewed priors. J Classification 2005, 22: 17–48.
Priebe, CE, Solka, JL, Marchette, DJ, Clark, T. Class cover catch digraphs for latent class discovery in gene expression monitoring by DNA microarrays. Comput Stat Data Anal 2003, 43: 621–632.
Marchette, DJ. Computer Intrusion Detection: a Statistical Viewpoint. New York: Springer; 2001.
Solka, JL, Clark, BT, Priebe, CE. A visualization framework for the analysis of hyperdimensional data. Int J Image Graphics 2002, 2: 145–161.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

Class cover catch digraphs

Browse by Topic

Access to this WIREs title is by subscription only.

The latest WIREs articles in your inbox