A Nearest Neighbor Classifier for High-Speed Big Data Streams with Instance Selection (spark-IS-streaming)

Here we present an efficient nearest neighbor solution to classify fast and massive data streams using Apache Spark. It is formed by a distributed case-base and an instance selection method that enhances its performance and effectiveness. A distributed metric tree (based on M-trees) has been designed to organize the case-base and consequently to speed up the neighbor searches. This distributed tree consists of a top-tree (in the master node) that routes the searches in the first levels and several leaf nodes (in the slaves nodes) that solve the searches in next levels through a completely parallel scheme.

A improved local version of RNGE [1] in order to control the insertion and removal of noisy instances. For each incoming example, a relative graph is built around each new instance and its subset of neighbors. The local graphs are then used to edit the case-base by deciding what instances should be inserted, removed or left intact.

Associated Spark package: https://spark-packages.org/package/sramirez/spark-IS-streaming

Associated journal paper: S. Ramírez-Gallego, B. Krawczyk, S. García, M. Woźniak, J. M. Benítez and F. Herrera, "Nearest Neighbor Classification for High-Speed Big Data Streams Using Spark," in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 10, pp. 2727-2739, Oct. 2017. doi: 10.1109/TSMC.2017.2700889 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7993020&isnumber=8038140

Parameters:

Our distributed approach includes several user-defined input parameters, which are described below:

• "type": type of file. "keel" for KEEL/ARFF files, "labeled" for Spark generated files with labeled points, or "csv" for standard csv files. Default: "csv".
• "header": path of header file (only valid for KEEL files).
• "output": path of output directory.
• "npart": number of partitions for the first partitioning process. Default: 4.
• "k": number of neighbors selected for prediction. Default: 1.
• "kGraph": number of neighors selected to construct local graphs. Default: 10.
• "rate": number of examples in each batch. Default: 2500.
• "interval": the time interval at which streaming data will be divided into batches. Default: 1000 (ms).
• "seed": seed value for random generator. Default: 237597430.
• "ntrees": number of sub-trees in the slave nodes. It should be set equal or higher than the number of initial partitions. Default: 4.
• "overlap": the distance between elements in sub-trees. 0 means sub-trees are disjoint. Default: 0.
• "edited": if filtering of new noisy examples ocurrs. Default: false.
• "removedOld": if removal of already inserted examples considered as noise ocurrs. Default: false.
• "timeout": milleseconds before shutting the streaming execution. Default: 600000.
• "sampling": percent of sampling w/o replacement on original static data. Default: 0.0.
• "nClass": number of classes in data. Default: 2 (binary).

Example:

spark-submit --class org.ugr.sci2s.mllib.test.QueuRDDStreamingTest spark-IS-streaming.jar --input=hdfs://localhost:8020/train.data --output=hdfs://localhost:8020/output/streaming-test --type=csv --interval=1000 --rate=100000 --ntrees=460 --npart=460 --edited=true

For a more thorough sourc code example, please refer to: src/main/scala/org/ugr/sci2s/mllib/test/QueuRDDStreamingTest.scala

Contributors

• Sergio Ramírez-Gallego ([email protected]) (main contributor and maintainer).

References

[1] J.S. Sánchez, F. Pla, F.J. Ferri, Prototype selection for the nearest neighbour rule through proximity graphs, Pattern Recognition Lett. 18 (1997) 507–513. KEEL project: https://github.com/SCI2SUGR/KEEL / http://sci2s.ugr.es/keel/description.php