  This work deals with the problem of classifying uncertain data. With this aim
the Uncertain Nearest Neighbor (UNN) rule is here introduced, which represents
the generalization of the deterministic nearest neighbor rule to the case in
which uncertain objects are available. The UNN rule relies on the concept of
nearest neighbor class, rather than on that of nearest neighbor object. The
nearest neighbor class of a test object is the class that maximizes the
probability of providing its nearest neighbor. It is provided evidence that the
former concept is much more powerful than the latter one in the presence of
uncertainty, in that it correctly models the right semantics of the nearest
neighbor decision rule when applied to the uncertain scenario. An effective and
efficient algorithm to perform uncertain nearest neighbor classification of a
generic (un)certain test object is designed, based on properties that greatly
reduce the temporal cost associated with nearest neighbor class probability
computation. Experimental results are presented, showing that the UNN rule is
effective and efficient in classifying uncertain data.
