2023-03-31T12:09:48Z
https://repository.nii.ac.jp/oai
oai:repository.nii.ac.jp:02000327
2023-01-11T04:28:36Z
136
NII Technical Report (NII-2015-002E)：Inlierness, Outlierness, Hubness and Discriminability: an Extreme-Value-Theoretic Foundation
Houle, Michael E.
テクニカルレポート
Technical Report
For many large-scale applications in data mining, machine learning, and multimedia, fundamental operations such as similarity search, retrieval, classification, clustering, and anomaly detection generally suffer from an effect known as the `curse of dimensionality'. As the dimensionality of the data increases, distance values tend to become less discriminative, due to their increasing relative concentration about the mean of their distribution. For this reason, researchers have considered the analysis of similarity applications in terms of measures of the intrinsic dimensionality (ID) of the data sets. This theory paper is concerned with a generalization of a discrete measure of ID, the expansion dimension, to the case of continuous distance distributions. This notion of the ID of a distance distribution is shown to precisely coincide with a natural notion of the indiscriminability of distances, thereby establishing a theoretically-founded relationship among probability density, the cumulative density (cumulative probability divided by distance), intrinsic dimensionality, and discriminability. The indiscriminability function proposed in this paper is shown to completely determine an extreme-value-theoretic representation of the distance distribution. From this representation, a characterization in terms of continuous ID is derived for the notions of outlierness and inlierness of data, as well as the hubness phenomenon in data sets.
国立情報学研究所
2015-03-31
eng
departmental bulletin paper
https://doi.org/10.20736/0002000327
https://repository.nii.ac.jp/records/2000327
10.20736/0002000327
1346-5597
NIIテクニカル・レポート
NII Technical Report
1
32
https://repository.nii.ac.jp/record/2000327/files/15-002E.pdf
application/pdf
477 KB
2022-06-08