View Full Document

Adaptive Nearest Neighbor Classification Algorithm



View the full content.
View Full Document
View Full Document

5 views

Unformatted text preview:

An Adaptive Nearest Neighbor Classi cation Algorithm for Data Streams Yan Nei Law and Carlo Zaniolo Computer Science Dept UCLA Los Angeles CA 90095 USA ynlaw zaniolo cs ucla edu Abstract In this paper we propose an incremental classi cation algorithm which uses a multi resolution data representation to nd adaptive nearest neighbors of a test point The algorithm achieves excellent performance by using small classi er ensembles where approximation error bounds are guaranteed for each ensemble size The very low update cost of our incremental classi er makes it highly suitable for data stream applications Tests performed on both synthetic and real life data indicate that our new classi er outperforms existing algorithms for data streams in terms of accuracy and computational costs 1 Introduction A signi cant amount of recent research has focused on mining data streams for applications such as nancial data analysis network monitoring security sensor networks and many others 3 8 Algorithms for mining data streams have to address challenges not encountered in traditional mining of stored data at the physical level these include fast input rates and unending data sets while at the logical level there is the need to cope with concept drift 18 Therefore classical classi cation algorithms must be replaced by or modi ed into incremental algorithms that are fast and light and gracefully adapt to changes in data statistics 17 18 5 Related Works Because of their good performance and intuitive appeal decision tree classi ers and nearest neighborhood classi ers have been widely used in traditional data mining tasks 9 For data streams several decision tree classi ers have been proposed either as single decision trees or as ensembles of such trees In particular VFDT 7 and CVFDT 10 represent well known algorithms for building single decision tree classi ers respectively on stationary and timechanging data streams These algorithms employ a criterion based on Hoe ding bounds to decide



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Adaptive Nearest Neighbor Classification Algorithm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Adaptive Nearest Neighbor Classification Algorithm and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?