k-Nearest Neighbors Algorithm in Java Applet - REMASTERED Edition

Hi there! This is my implementation of k-Nearest Neighbors (kNN) algorithm which is written in Java programming language and this aims to simulate on 2-dimensional plain space that contain many data objects distributed randomly and a query object that chooses its k-nearest data objects by calculating Euclidean distances against all; now upgraded to REMASTERED Edition!

Typically, kNN can be encountered in Machine Learning as a classification algorithm, which is simple but effective, easy to implement and yield very good results in most situations. Here, it is applied as the intention of proximity querying for selecting the nearest objects.

Several years ago, I had created this useful applet while I was a PhD student in the university, with the objective to understand how algorithms that focused on proximity could work on open plain space much better. This was a good starting point for moving to other similar implementations in the future. To maintain the corresponding codes remotely, I found GitHub as a convenient place while also I was newcomer of that platform to get the hang of the logic of Git commands. But then, even after leaving PhD, I didn't make any changes and it was left untouched for several years!

As being one of my first repositories here, my initial version of kNN Java was becoming so obsolete through my eyes! For this reason, I overhauled everything, redesigned many pieces of the codebase, improved the general usability and even added new features to make it more educational and entertaining for everyone. As a consequence, I called it Remastered Edition to emphasize that the whole implementation has been renewed and it was convenient to use this buzzword that is seen for several video games in recent years. To be honest, this is one of my best programming projects I've so far! If you're a visitor of this repo, hopefully you'll like this applet.

First of all, I meticulously designed and programmed everything to simulate k Nearest Neighbors algorithm in the best way. As seen in the screenshots above, there are several data objects (shown as black dots), the query object (shown as red dot), and more importantly, the nearest data objects selected by the query up to k value (shown as blue dots). In addition, a blue circle is drawn, which is centered at the query object, to indicate how large the area is scanned in order to find these k nearest objects (with blue straight lines as the furthest one determines the radius). As expected, this area and the related k nearest objects are updated immediately when the query object is moved anywhere in the applet screen.

Here are the complete features that can be carried out by the user without closing and re-opening the applet:

• Create new data objects and the query object together, at fully randomized positions
• Move the query object with four directions (left, right, up & down) to get different kNN output
• Mouse support, so the query object can be moved directly anywhere by just a click on the applet
• Display the ID numbers of all data objects on the applet
• Display the (x, y) coordinates of all data objects and the query object on the applet
• Display the shortest distances of k nearest data objects in the console
• Adjust the k value, total number of data objects, and the movement speed of the query object via keyboard
• Observe the general kNN connectivity generated by all data objects
• Observe the convex hull in the plain space
• Support switching between light & dark modes

1. When the appearance of kNN connectivity between all data objects is activated, you may see lots of green straight lines between all available data objects. This feature was added as an experimental purpose to figure out whether or not all data objects can be connected by constructing one whole network with the knowldge of their kNNs; this is where a graph theory might be built from there accordingly. The chance is increased significantly for higher number of k and data objects.

2. If the outputting of shortest distances is turned on, the information shown in the console contains the IDs of selected data objects and their Euclidean distances (by pixels) to the query object up to the number of k, starting with this subtitle SHORTEST DISTANCES TO QUERY.

3. Upon launch, new creation of data objects and the query object, changing the k value or the number of data objects, every time the console output reports the kNN of each data object against all other objects, as a two-dimensional list, with this subtitle DATA OBJECTS KNN. Each element belongs to individual data objects where the number on the left is its ID number and the list on the right is the IDs of selected k nearest data objects.

4. When the visualization of the convex hull polygon is activated, the thick purple straight lines are drawn through each of the query objects in order. Certainly, the hull is always change when the whole new set of data objects and the query object is generated or the total number of visible data objects is changed. In the cosnole, the (x, y) coordinates of each data object forming the convex hull is reported in the console, with the subtitle CONVEX HULL POINTS.

The convex hull algorithm is based on Jarvis's Algorithm, which can be found here.

5. The support of swtiching between light & dark modes has been brought in order to continue working with the applet in dark conditions and to help relax your eyes! As noticeable, the query objects and all relevant texts are shown in white color while in dark mode; plus the whole plain space is in dark gray while the other elements' colors remain unchanged.

The remastered version of k nearest neighbors applet was compiled and run smoothly in IntelliJ IDEA and all the related files uploaded here (except the hidden ones) came from the folder structure of that IDE. However, the actual source code should run with other popular IDEs such as Apache NetBeans and Eclipse.

To make that simply, I advise you to create a new project with appropriate name and copy KNNRemastered.java file in src folder to the empty folder of newly created project, and after the compilation (by hitting Run or the equivalent button, for instance), it must run as seen in the screenshots above very similarly.

Lastly, ensure you have at least Java 8 JDK installed on your computer, but this should work with other versions as well (e.g. 11, 17, 21).

When the applet is started, you'll notice that the data objects and the query object is randomly placed immediately and the k nearest neighbor objects selected by the query object is already determined. Moreover, the bottom bar informs the availability of the actions the user is able to perform with the press of an appropriate key, and on the bottom left corner, the current values of k, query movement speed and the number of data objects are shown.

Below is the list of actions that can be performed with key strokes inside the applet:

• Space = Create new data objects and the query objects randomly from the beginning
• Left, Right, Up, Down Arrow = Move the query object to the left, right, up and down repsectively, by the current movement speed
• Z / X = Decrease / increase the k value by 1 (min = 1, max = 10, default = 3)
• C / V = Decrease / increase the query speed by 1 (min = 1, max = 20, default = 8)
• B / N = Decrease / increase the number of query objects appeared on the applet by 5 (min = 10, max = 100, default = 40)
• A = Show / hide the ID number of each data object
• S = Show / hide the (x, y) coordinates of each data object and the query object
• D = Show / hide the distances of selected k neaerest neighbors in the console
• F = Show / hide the connectivity of all data objects to each other with regards to the current value of k
• G = Show / hide the convex hull drawn in the applet
• Q = Switch between light and dark mode (deafult mode = light)

Besides moveing the query object via keyboard, you can also use your mouse and (left/middle/right)-click anywhere on the applet to instantly move the query object to the specified (x, y) coordinate where it is pointed at.

Inside the source code, you may want to change these values to be different than the default ones (still obeying the min-max limits): Hsize, Vsize, k, dataObject, qSpeed.

Certainly, there are several Boolean variables which are set to false initially: showCoords, showNumbers, showDistance, showConnection, showConvexHull, darkMode.

However, I highly recommend to leave them as they are for the general operability of the applet. Otherwise, if you know what to do, please make sure no weird cases occurred while running!

If you're using Windows operating system (especially the latest versions of 10 or 11) with high DPI scaling enabled, keep in mind that Java applets do not get scaled pretty well, as the whole applet gets uglier pixel by pixel and there is no anti-aliasing or edge softening!

To overcome this issue and get the applet back to the original scaling, these web pages can be helpful for you: Link 1, Link 2

Note: I didn't test it for other OSes like Mac or Linux. You may have to explore the solutions over the internet and find the proper settings.