Inlierness, Outlierness, Hubness and Discriminability:
an Extreme-Value-Theoretic Foundation
Michael E. HOULE
データの複雑さはどのように測 定するのか？

The Problem

現在、データマイニングは統一理論がまだ提案されていない。 個々の問題のためには、分類また、クラスタリングなどの多くのアドホ ッ ク技術が設計されている。我々は、さまざまな基本的な機械学習とデータマイ ニングタスクを結びつける理論的な枠組みを提案する。

To date, no unifying theory of data mining has been proposed.
I Many ad-hoc techniques have been designed for individual problems,such as classification or clustering.
I Solutions involve much invention and reinvention, with few guidelines.
A theoretical framework that ties together different fundamental machinelearning and data mining tasks (including indexing, clustering, classification, data discriminability, subspace methods, etc.) could help the discipline, and serve as a basis for future investigation.

ID and Scalability

The Curse of Dimensionality
As the number of object features (data dimensionality) rises:
I Similarity values concentrate around their
expected values.
I Items become less and less distinguishable.
I Data analysis based similarity (e.g. clusteringand classification) becomes ineffective.
Some sets have higher intrinsic dimensionality(ID) than others.

Implications for Big Data:
I Data mining is greatly concerned with what
happens in neighborhoods of data (clustering,classification, outlier detection, . . . ).
I As the number of objects increases, thek-nearest neighbor (k-NN) distance tends to 0.
I Indiscriminability of neighborhood distances,and ID of k-NN query result, tend to IDFX (0).

Discriminability of Distances

I (2) in probability measure.
The indiscriminability of X at distance r is:
InDiscrX(r) = lim+
→0FX((1 + )r) − FX(r) · FX(r)!

Local IDWhen FX(r) > 0, the local intrinsic dimensionalityof X at distance r is defined as:!
ln FX((1 + )r) − ln FX(r)IntrDimX(r) = lim+
→0ln(1 + )

If instead IDFX (r) > IDFX (0), p is an outlier.

Let X be an absolutely continuous random distance variable such that FX(r) > 0 wheneverr > 0. Then for any r, w ∈ (0, z), r IDF (0)XFX(r) = FX(w) ·· GFX,0,w(r), whereZ w w
IDFX (0) − IDFX (t)dt .
GFX,0,w(r) := exptr
Furthermore, for any fixed 0 < c < 1, we havew→0+cw6r6w

2nd-Order ID
I Inlierness / outlierness is determined by thesign of IDF0 X (r) as r → 0+.
I Strength is obtained by normalizing IDF0 X (r) for
distance and intrinsic dimensionality:r · IDF0 X (r)IDIDFX (r) == IDFX0 (r) + 1 − IDFX (r),IDFX (r)I However, IDIDFX (0) = 0 always . . . need thegrowth rate ID|IDIDF |(0) of |IDIDFX (r)| instead.
X

Extreme Value Theory
I Profound importance in risk analysis,economics, civil engineering, operations
research, material sciences, geophysics, . . . .
I Here, adapted for the lower tails of distance
distributions.
I One of the three fundamental pillars ofExtreme Value Theory, Karamata
Characterization Theorem (1930):FX(x) = xγX `X(1/x) for some constant γX,
whereZw
εX(1/t)`X(1/x) = exp η X(1/x) +dt .
tx
ID and Extreme Value Theory

This definition is an extension for continuous distance distributions of the Expansion Dimension.

I ID Representation is a more precise
formulation of the Karamata Characterization,
with:Theorem (Equivalence of ID and Indiscriminability)

γX = IDFX (0) ;η X(1/x) = ln FX(w) − IDFX (0) ln w ;εX(1/t) = IDFX (0) − IDFX (t) .

Let X be an absolutely continuous random distance variable. If FX is both positive and differentiable at r, thenr · fX(r)IntrDimX(r) = InDiscrX(r) ==: IDFX (r).
FX(r)

I The drop in indiscriminability (rise indiscriminability) indicates a decrease in local
density as the distance from p increases.

Theorem (ID Representation Formula)

I Let X be an absolutely continuous random
distance variable with c.d.f. FX and p.d.f fX.

I (1) the relative increase in distance, andI The growth rate at distance r is less than thatwhich would be expected within a uniform
distribution of dimension IDFX (0).

Limit effect characterizes the complexity of data.

lim GFX,0,w(r) = 1 .

I Discriminability of the distance measure canbe regarded as a ratio between two quantities
as the distance expands infinitessimally:

If IDFX (r) < IDFX (0) within neighborhood 0 < r < of some point p, then:

I The relationship between p and its
neighborhood is therefore that of an inlier.

I Intuitively, the minimum number ofdimensions or features with which the data
can be represented with minimal distortion.
I Many formalizations have been proposed(such as the Hausdorff dimension, in 1918!).

ID and Inlierness / Outlierness

I IDFX (0) is the well-studied EVT index γX.
I Connections also exist between ID andHausdorff dimension, and ID and the hubness
phenomenon in data.

Michael E. Houle
国立情報学研究所
 : 03 - 4212 - 2538

Example: Distances to a Gaussian
I Vector of normally distributed randomvariables with means µi and variances σ2i .
I Distance from 0 to a point
X = (X1, X2, . . . , Xm), defined asvv
u m 2u m 2uX µiu X Xi
t
Z= t,
and
λ=
22σσi
i=1
i=1 i
is the normalized distance from 0 to theGaussian mean.
I IDFZ (0) = m and ID|IDIDF |(0) = 2 wheneverZ√
λ , m. Also, as r tends to 0, IDIDFZ (r) > 0√when λ > m √(tail region → outliers), and < 0when 0 6 λ < m (central region → inliers).
I Normalization works! Independent of λ & m.
√Inlier Region λ < mReferences[1] M. E. Houle.
“Inlierness, Outlierness, Hubness
and Discriminability: an Extreme-Value-Theoretic Foundation”, NII Technical Report NII-2015-002E.
[2] M. E. Houle. “Dimensionality, discriminability, density &distance distributions”, ICDMW 2013.

(フフー ル マ イ ケ ル )客員教授〒 101-8430 東 京 都千代 田 区一 ツ 橋2-1-2-1403
t : 03 - 4212 - 2120
B : meh @ nii.ac.jp