National Technical Reports Library

The National Technical Information Service acquires, indexes, abstracts, and archives the largest collection of U.S. government-sponsored technical reports in existence. The NTRL offers online, free and open access to these authenticated government technical reports. Technical reports and documents in its repository may be available online for free either from the issuing federal agency, the U.S. Government Publishing Office’s Federal Digital System website, or through search engines.

Details

Some Provable Properties of VERI Clustering.

DE2001760739

Publication Date	2000
Personal Author	Osbourn, G. C.
Page Count	14
Abstract	We present mathematical proofs for two useful properties of the clusters generated by the visual empirical region of influence (VERI) shape. The first proof shows that, for any d-dimensional vector set with more than one distinct vector, that there exists a bounded spherical volume about each vector v which contains all of the vectors that can VERI cluster with v, and that the radius of this d-dimensional volume scales linearly with the nearest neighbor distance to v. We then prove, using only each vector's nearest neighbor as an inhibitor, that there is a single upper bound on the number of VERI clusterings for each vector in any d-dimensional vector set, provided that there are no duplicate vectors. These proofs guarantee significant improvement in VERI algorithm runtimes over the brute force O(N(sup 3)) implementation required for general d-dimensional region of influence implementations and indicate a method for improving approximate O(NlogN) VERI implementations. We also present a related region of influence shape called the VERI bow tie that has been recently used in certain swam intelligence algorithms. We prove that the VERI bow tie produces connected graphs for arbitrary d-dimensional data sets (if the bow tie boundary line is not included in the region of influence). We then prove that the VERI bow tie also produces a bounded number of clusterings for each vector in any d-dimensional vector set, provided that there are no duplicate vectors (and the bow tie boundary line is included in the region of influence).
Keywords	Clusters Algorithms Implementation Shape Vectors Mathematical proofs Properies Visual empirical region of influence(VERI)
Source Agency	Technical Information Center Oak Ridge Tennessee
Corporate Authors	Sandia National Labs., Albuquerque, NM.; Department of Energy, Washington, DC.
Document Type	Technical Report
NTIS Issue Number	200123
Contract Number	AC04-94AL85000

Some Provable Properties of VERI Clustering.

Some Provable Properties of VERI Clustering.
DE2001760739

Publication Date	2000
Personal Author	Osbourn, G. C.
Page Count	14
Abstract	We present mathematical proofs for two useful properties of the clusters generated by the visual empirical region of influence (VERI) shape. The first proof shows that, for any d-dimensional vector set with more than one distinct vector, that there exists a bounded spherical volume about each vector v which contains all of the vectors that can VERI cluster with v, and that the radius of this d-dimensional volume scales linearly with the nearest neighbor distance to v. We then prove, using only each vector's nearest neighbor as an inhibitor, that there is a single upper bound on the number of VERI clusterings for each vector in any d-dimensional vector set, provided that there are no duplicate vectors. These proofs guarantee significant improvement in VERI algorithm runtimes over the brute force O(N(sup 3)) implementation required for general d-dimensional region of influence implementations and indicate a method for improving approximate O(NlogN) VERI implementations. We also present a related region of influence shape called the VERI bow tie that has been recently used in certain swam intelligence algorithms. We prove that the VERI bow tie produces connected graphs for arbitrary d-dimensional data sets (if the bow tie boundary line is not included in the region of influence). We then prove that the VERI bow tie also produces a bounded number of clusterings for each vector in any d-dimensional vector set, provided that there are no duplicate vectors (and the bow tie boundary line is included in the region of influence).
Keywords	Clusters Algorithms Implementation Shape Vectors Mathematical proofs Properies Visual empirical region of influence(VERI)
Source Agency	Technical Information Center Oak Ridge Tennessee
Corporate Authors	Sandia National Labs., Albuquerque, NM.; Department of Energy, Washington, DC.
Document Type	Technical Report
NTIS Issue Number	200123
Contract Number	AC04-94AL85000