Sorting A 2D ArrayList Based On Columns

[John Carmicahel]

I am in the process of implementing a decision tree for a machine learning course. I am given a 2D ArrayList where each row describes an instance (set of attributes with a given classification) for training my decision tree. Each column is a particular attribute, all attributes are real-valued doubles, and the last column is a binary classification (either a 0 or a 1). What I need help with is sorting my 2D ArrayList by 1 attribute at a time. I want the entire row to be moved along with the attribute it's being sorted by.

For example:

[ 9, 8, ... , 0]
[ 3, 2, ... , 1]
[ 4, 1, ... , 1]
[ 5, 6, ... , 0]

first time it's sorted (i.e sort by the first attribute):

[ 3, 2, ... , 1]
[ 4, 1, ... , 1]
[ 5, 6, ... , 0]
[ 9, 8, ... , 0]

after sorting on the first attribute (column) I will perform a set of operations with this data. Then I need to sort it by the second attribute, third attribute, ... nth attribute. I do not want to sort by the final column because this stores classifications, not attributes.

If anyone could lead me in the correct direction for the sorting behavior it would be greatly appreciated! Please let me know if you need any further clarifications.

[Norman Radder]

Defining a Comparator for the Arrays class's sort method should work.

[John Carmicahel]

Could you point me towards a source that could potentially help me implement that? Or could you possibly outline the steps. The method in question looks like this:

public void rootInfoGain(ArrayList<ArrayList<Double>> dataSet, ArrayList<String> trainAttributeNames, int minLeafNumber) {
this.mTrainAttributes = trainAttributeNames;
this.mTrainDataSet = dataSet;
this.minLeafNumber = minLeafNumber;

}

I'm trying to sort this.mTrainDataSet.

[John Carmicahel]

int numAttributes = this.mTrainAttributes.size();
for(int i = 0; i < numAttributes; i++){
	Collections.sort(dataSet, new Comparator<ArrayList<Double>>(){
		@Override
		public int compare(ArrayList<Double> o1, ArrayList<Double> o2){
			return o1.get(0).compareTo(o2.get(0));
		}
	});
}

This is the solution that I am working towards. The problem here is that I can't seem to figure out how to replace the .get(0) with .get(i) without running into errors. Some further direction would be greatly appreciated.

[Norman Radder]

The Comparator class's compare method would take two rows to compare and return a value indicating which is greater.
Then use something like:  Arrays.sort(arrayName, yourComparator...

[Norman Radder]

without running into errors.

Can you copy the full text of the error messages and paste it here.

The posted code looks like it always sorts on the first column (index == 0).
That needs to be parametized to allow the setting of the column to sort on.

[Norman Radder]

Can you explain why there is a loop in the code at line 2?

[John Carmicahel]

int numAttributes = this.mTrainAttributes.size();
	Collections.sort(dataSet, new Comparator<ArrayList<Double>>(){
		@Override
		public int compare(ArrayList<Double> o1, ArrayList<Double> o2){
			return o1.get(0).compareTo(o2.get(0));
		}
	});

I want that loop so that I can iterate through the different attributes (colums) to sort by. So I want ot sort by the first column, then I need to find the split threshold that will give me the optimal information gain for my decision tree based off of the sorted list. After I find that information, I need repeat this proces for the second attribute, which requires me to sort by the second column/attribute. I need to repeat this process for every attribute/column to find the optimal split threshold for each attribute/column. Most of that information is kind of irrelevant to you. I just need to know how to sort by a column, perform my operations, then move to the next column for sorting, etc.

[Norman Radder]

What happens when you compile and execute the code?

Note: Instead of hardcoding a 0 in the get methods, the value used should be a variable that can change for the column you want sorted.

[John Carmicahel]

for(int i = 0; i < numAttributes; i++){
	Collections.sort(dataSet, new Comparator<ArrayList<Double>>(){
		@Override
		public int compare(ArrayList<Double> o1, ArrayList<Double> o2){
			return o1.get(i).compareTo(o2.get(i));
		}
	});
}

NOTE: I change the values in the get() to i. The problem with this is I am not passing i to the compare method. So if I go one step further:

for(int i = 0; i < numAttributes; i++){
	Collections.sort(dataSet, new Comparator<ArrayList<Double>>(){
		@Override
		public int compare(ArrayList<Double> o1, ArrayList<Double> o2, int i){
			return o1.get(0).compareTo(o2.get(0));
		}
	});
}

Now I have passed i to my overriden compare function; however, my IDE is giving me this error:

The method compare(ArrayList<Double>, ArrayList<Double>, int) of type new Comparator<ArrayList<Double>>(){} must override or implement a supertype method

[John Carmicahel]

I apologize, there is an error in the second piece of code I linked to use, the get() calls should still contain (i) not (0).

[John Carmicahel]

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Fill in the implementation details of the class DecisionTree using this file. Any methods or
 * secondary classes that you want are fine but we will only interact with those methods in the
 * DecisionTree framework.
 * 
 * You must add code for the 1 member and 4 methods specified below.
 * 
 * See DecisionTree for a description of default methods.
 */
public class DecisionTreeImpl{
	private DecTreeNode root;
	//ordered list of attributes
	private List<String> mTrainAttributes; 
	//
	private ArrayList<ArrayList<Double>> mTrainDataSet;
	//Min number of instances per leaf.
	private int minLeafNumber = 10;

	/**
	 * Answers static questions about decision trees.
	 */
	DecisionTreeImpl() {
		// no code necessary this is void purposefully
	}

	/**
	 * Build a decision tree given a training set then prune it using a tuning set.
	 * 
	 * @param train: the training set
	 * @param tune: the tuning set
	 */
	DecisionTreeImpl(ArrayList<ArrayList<Double>> trainDataSet, ArrayList<String> trainAttributeNames, int minLeafNumber) {
		this.mTrainAttributes = trainAttributeNames;
		this.mTrainDataSet = trainDataSet;
		this.minLeafNumber = minLeafNumber;
		this.root = buildTree(this.mTrainDataSet);
	}

	private DecTreeNode buildTree(ArrayList<ArrayList<Double>> dataSet){
		// TODO: add code here
	}

	public int classify(List<Double> instance) {
		// TODO: add code here

	}

	public void rootInfoGain(ArrayList<ArrayList<Double>> dataSet, ArrayList<String> trainAttributeNames, int minLeafNumber) {
		this.mTrainAttributes = trainAttributeNames;
		this.mTrainDataSet = dataSet;
		this.minLeafNumber = minLeafNumber;
		// TODO: add code here
		int numAttributes = this.mTrainAttributes.size();
		for(int i = 0; i < numAttributes; i++){
			Collections.sort(dataSet, new Comparator<ArrayList<Double>>(){
				@Override
				public int compare(ArrayList<Double> o1, ArrayList<Double> o2, int i){
					return o1.get(i).compareTo(o2.get(i));
				}
			});
		}
		
		ArrayList<Double> thresholds;
		for(int i = 0; i < thresholds.size(); i++){
			double threshold = thresholds.get(i);
		}

		//TODO: modify this example print statement to work with your code to output attribute names and info gain. Note the %.6f output format.
		for(int i = 0; i<bestSplitPointList.length; i++){
			System.out.println(this.mTrainAttributes.get(i) + " " + String.format("%.6f", bestSplitPointList[i][0]));
		}	
	}

	private static double log2(double n){
		return (Math.log(n) / Math.log(2));
	}

	private double entropy(double numClassZero, double numClassOne){
		double entropy = -numClassZero * log2(numClassZero) - numClassOne * log2(numClassOne);
	}

	private double gain(){

	}

	/**
	 * Print the decision tree in the specified format
	 */
	public void print() {
		printTreeNode("", this.root);
	}

	/**
	 * Recursively prints the tree structure, left subtree first, then right subtree.
	 */
	public void printTreeNode(String prefixStr, DecTreeNode node) {
		String printStr = prefixStr + node.attribute;

		System.out.print(printStr + " <= " + String.format("%.6f", node.threshold));
		if(node.left.isLeaf()){
			System.out.println(": " + String.valueOf(node.left.classLabel));
		}else{
			System.out.println();
			printTreeNode(prefixStr + "|\t", node.left);
		}
		System.out.print(printStr + " > " + String.format("%.6f", node.threshold));
		if(node.right.isLeaf()){
			System.out.println(": " + String.valueOf(node.right.classLabel));
		}else{
			System.out.println();
			printTreeNode(prefixStr + "|\t", node.right);
		}


	}

	public double printAccuracy(int numEqual, int numTotal){
		double accuracy = numEqual/(double)numTotal;
		System.out.println(accuracy);
		return accuracy;
	}

	/**
	 * Private class to facilitate instance sorting by argument position since java doesn't like passing variables to comparators through
	 * nested variable scopes.
	 * */
	private class DataBinder{

		public ArrayList<Double> mData;
		public int i;
		public DataBinder(int i, ArrayList<Double> mData){
			this.mData = mData;
			this.i = i;
		}
		public double getArgItem(){
			return mData.get(i);
		}
		public ArrayList<Double> getData(){
			return mData;
		}

	}

}

This is the entire class that I am implementing currently. The stuff we are focusing on is inside rootInfoGain

[Norman Radder]

Does the sort work for you?

[Norman Radder]

You can not change the parameters for the compare method.  They must match what is defined in the interface.

[Norman Radder]

It is easier to work on a small program that tests only the problem you are working on.  For this problem about 25 lines of  code should be enough.

[John Carmicahel]

I can't even run that code, mostly because there are compiler errors from what I have included. In the entire class that I included, I believe I can utilize the private class DataBinder to help with my problem here, but I'm not exactly sure how to do so.

[John Carmicahel]

private class DataBinder{

	public ArrayList<Double> mData;
	public int i;
	public DataBinder(int i, ArrayList<Double> mData){
		this.mData = mData;
		this.i = i;
	}
	public double getArgItem(){
		return mData.get(i);
	}
	public ArrayList<Double> getData(){
		return mData;
	}
}

coupled with some form of

int numAttributes = this.mTrainAttributes.size();
for(int i = 0; i < numAttributes; i++){
	Collections.sort(dataSet, new Comparator<ArrayList<Double>>(){
		@Override
		public int compare(ArrayList<Double> o1, ArrayList<Double> o2){
			return o1.get(i).compareTo(o2.get(i));
		}
	});
}

is where my answer is I believe, I'm just not entirely sure how to use the DataBinder

[Norman Radder]

I prefer working on one problem at a time.  I thought the current problem was sorting a 2 dim ArrayList of doubles.  Have you tried creating a small program of 20-30 lines that defines a 2 dim ArrayList and sorts it on different columns?  Get that to work, then merge the code into the larger program and move to the next problem.

[Norman Radder]

there are compiler errors  

You need to post the code and its errors if you want help.

[John Carmicahel]

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;


public class ArrayListSorter {
	public static void main(String[] args){
		ArrayList<ArrayList<Double>> myArrayList = new ArrayList<>();
		int numInstances = 10;
		int numAttributes = 10;
		for(int i = 0; i< numInstances; i++){
			myArrayList.add(new ArrayList<Double>());
			for(int j = 0; j < numAttributes; j++){
				Random r = new Random();
				double val = r.nextDouble();
				myArrayList.get(i).add(val);
			}
		}
		
		Collections.sort(myArrayList, new Comparator<ArrayList<Double>>() {    
	        @Override
	        public int compare(ArrayList<Double> o1, ArrayList<Double> o2) {
	            return o1.get(0).compareTo(o2.get(0));
	        }               
		});
		for(int i = 0; i < numInstances; i++){
			System.out.println(myArrayList.get(i));
		}
	}
}

Alright I have isolated the problem we are looking at. This code properly sorts by the first column. I need to figure out how to implement the behavior I described above.

[Carey Brown]

You need to define a Comparator class whose constructor takes a column number. Something along these lines...

	class ColumnComparator
	implements Comparator<List<Double>>
	{
		private int column;
		
		public ColumnComparator( int column )
		{
			this.column = column;
		}

		@Override
		public int compare( List<Double> o1, List<Double> o2 )
		{
			return o1.get( column ).compareTo( o2.get( column ) );
		}
	}

[John Carmicahel]

You're a life saver! With some tweaking that worked perfectly. Much appreciated!

[Carey Brown]

John Carmicahel wrote:You're a life saver! With some tweaking that worked perfectly. Much appreciated!

Glad I could be of  help.

[Piet Souris]

That is indeed an elegant comparator.

Another way would be to use the Comparator.comparing method from the Comparator interface, something like:

public static <T> Comparator<List<T>> colComp(final int n, Comparator<T> comp) {
    return Comparator.comparing(t -> t.get(n), comp);
}

public static Comparator<Integer[]> colComp(final int n) {
    return Comparator.comparing(t -> t[n]);
}

and t could be used as in:

class Testertje {
    public static void main(String... args) {
        List<Integer> l1 = Arrays.asList(1, 2, 3);
        List<Integer> l2 = Arrays.asList(3, 2, 1);
        List<List<Integer>> mm = Arrays.asList(l1, l2);
        Collections.sort(mm, colComp(0, Comparator.<Integer>reverseOrder()));
        System.out.println(mm);
        Collections.sort(mm, colComp(0, Comparator.<Integer>naturalOrder()));
        System.out.println(mm);
        Integer[][] array = { {1,2,3}, {3,2,1}, {2,1,3} };
        Arrays.sort(array, colComp(1));
        Arrays.stream(array).forEach(a -> System.out.println(Arrays.toString(a)));
    }
}