Composite Hypercubes on Iterated Random Projections (CHIRP)

A Composite Hypercubes on Iterated Random Projections (CHIRP) is a nonparametric, ensemble classifier based on L-Infinity Norm.

• AKA: CHIRP.
• Context:
  • This classifier was introduced by Wilkinson et al., 2011.
• Example(s):
  • Nonparametric Classifier.
  • Ensemble Classifier.
• Counter-Example(s):
  • L2-Norm.
  • L1-Norm.
• See: Lp Space, L-Infinity Norm, L-Infinity Space, Vector Norm, L1-Norm, L2-Norm, Hypercube Description Region (HDR), Composite Hypercube Description Region (CHDR).

---

---

References

2011

• (Wilkinson et al., 2011) ⇒ Leland Wilkinson, Anushka Anand, and Dang Nhon Tuan. (2011). “CHIRP: A New Classifier based on Composite Hypercubes on Iterated Random Projections.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020418
  • QUOTE: CHIRP is a classifier that was designed to address the curse of dimensionality and exponential complexity by using projection, binning, and covering in a sequential framework.(...) CHIRP is based on a visual analytics framework using what we call Composite Hypercube Description Regions(CHDRs) that can be used to define local and large-scale structures.(...) While the union of open spherical balls is used to define a basis for the L2 Euclidean metric topology, we can alternatively use balls based on other Lp metrics. For CHIRP, we employ the L∞ or sup metric:

[math]\displaystyle{ ||x||_\infty = sup(|x_1|, |x_2|,... |x_n|) }[/math]

when we search for neighbors. In this search, we are looking for all neighbors of a point at the center of a hypercube of fixed size in a vector space. Because we are concerned with finite-dimensional vector spaces in practice, we will use max() instead of sup() from now on.

Definition 1 A hypercube description region (HDR) is the set of points less than a fixed distance from a single point (called the center) using the L∞ norm. A weighted hypercube description region is an HDR that uses the positively weighted L∞ norm:

[math]\displaystyle{ ||x||_\infty = max(w_1|x_1|, w_2|x_2|,...w_n|x_n|) }[/math]

We will assume the term HDR refers to this more general case. Our use of weights implies that different points in a high-dimensional space can have different weights defining their hypercubes.

Definition 2 A composite hypercube description region (CHDR) is the set of points inside the union of zero or more hypercube description regions.

---