KNN

Classification problems are quite common in many areas. One common example is in diagnosing diseases where the symptoms of some illness must be classified as a particular disease so that it can be treated properly. Other examples abound, but the one thing that they have in common is that there are a number of known variables, and the goal is to learn some function from the known variables to the classifications.

A common way to deal with this problem is to start with some relatively large set of cases for the problem, whose classifications have already been determined by some independent method. Then, when a new case arises, whose classification is unknown, one can look for similar cases with known classifications, and assume that if the values of the variables are similar, then the final classification will be too. One relatively simple algorithm that often does well at this problem is called K-Nearest Neighbor (KNN). In this algorithm a distance metric is established for evaluating the distance between two cases in the problem. When a new case comes up, the distances from that case to all of the cases with known classifications are calculated. Then, the K cases with the lowest distances are chosen, and the classification that is most common among those cases is deemed to be the classification for the new case.

In order to make this method most effective, the distance metric must be well suited for the problem. Often, some of the variables are much more important that others, and should be treated as such by the distance metric. For this problem, we will be using the following formula to calculate the distance from case i to case j:

Here w_k represents the weight of the k^th variable and signifies how important it is - higher weights mean greater importance. v_ik represents the value of the k^th variable in case i and v_jk represents the value of the k^th variable in case j.
For example, if weights = {1,3,2}, case 1 = {3,4,3}, and case 2 = {4,3,3}, then there are three variables, which have weights of 1, 3 and 2. In the first case, the variables take values of 3, 4 and 3, while in the second case, the variables take values of 4, 3 and 3. Thus, the distance between these cases would be:

You will be given a String[], known, each of whose elements represents a single case whose classification is known. It will be formatted as "<var 0> <var 1> ... <var n-1> <classification>", where n is the number of variables in the problem. Each <var i> will be an integer, and <classification> will be a string of uppercase letters. You will also be given a int[], unknown, with n elements, representing the case whose classification is to be determined. Element i of unknown will represent the i^th variable of the case. You will be given a int[], weights, representing the weights of all the variables. Element i of weights will represent the weight of the i^th variable. Lastly, you will be given an int, K, representing the K mentioned above. The input will be such that there is one classification which is most common, so there will be no ties.