0
\$\begingroup\$

Problem definition

Given \$X = (x_1, \dots, x_n)\$ such that \$x_1 \leq x_2 \leq \dots \leq x_n \$. Let \$x_{\min} = \min X = x_1\$, \$x_{\max} = \max X = x_n\$ and \$r = x_{\max} - x_{\min}\$. Also, let \$m = n - 1\$. Finally, $$ \ell = \frac{r}{m} $$ is the average gap length. The clusterness measure CM of \$X\$ is given by $$ 1 - \frac{1}{r} \sum_{i = 1}^m \min(\vert \ell - \Delta_i \vert, \ell), $$ where \$\Delta_i = x_{i + 1} - x_i\$ is the length of the \$i\$th gap. Assuming \$r > 0\$, CM returns a value in range \$[0, 1)\$ that represents how well the points in \$X\$ are close to each other, the value of 0 denoting the situation where all the gaps are equal in length. If we define \$CM = 1\$ in case \$r = 0\$ (all \$x_i\$ are equal), the range of CM extends to \$[0, 1]\$.

Solution

package net.coderodde.datascience.measures;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * This class implements a method for computing clusterness measure (CM). CM
 * asks for a set of points <code>x1, x2, ..., xn</code>, and it returns a 
 * number within <code>[0, 1]</code>. The 
 * idea behind CM is that it returns 0 when all the data points are equal and 1
 * whenever all adjacent points are equidistant.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 21, 2019)
 */
public class ClusternessMeasure {

    public double computeClusternessMeasure(Collection<Double> points) {
        List<Double> pointList = new ArrayList<>(points);
        Collections.sort(pointList);

        double minimumPoint = pointList.get(0);
        double maximumPoint = pointList.get(pointList.size() - 1);
        double range = maximumPoint - minimumPoint;

        if (range == 0.0) {
            // Once here, all data points are equal and so CM must be 1.0.
            return 1.0;
        }

        double expectedDifference = range / (points.size() - 1);
        double sum = 0.0;

        for (int i = 0; i < points.size() - 1; i++) {
            double currentDifference = pointList.get(i + 1) - pointList.get(i);
            sum += Math.min(Math.abs(expectedDifference - currentDifference),
                                     expectedDifference);
        }

        return sum / range;
    }

    public static void main(String[] args) {
        ClusternessMeasure cm = new ClusternessMeasure();

        // CM = 0.0
        System.out.println(
                cm.computeClusternessMeasure(
                        Arrays.asList(1.0, 2.0, 3.0, 4.0, 5.0)));

        // CM = 1.0
        System.out.println(
                cm.computeClusternessMeasure(
                        Arrays.asList(2.0, 2.0, 2.0)));

        System.out.println(
                cm.computeClusternessMeasure(
                        Arrays.asList(1.0, 2.0, 3.0, 5.0, 4.0, 6.0, 7.1)));
    }    
}

Critique request

Please tell me anything that comes to mind. I am most interested in coding conventions and naming style. Also, would like to hear comments from machine learning perspective.

\$\endgroup\$
  • \$\begingroup\$ Do you have more context: 1. Does the algorithm come from somewhere else, or is this implementation canonical? 2. is the test code only expected usage? if not what is the expected input size? 3. Is it possible that it will be compared to other similar measures? \$\endgroup\$ – abuzittin gillifirca Feb 21 at 14:39
1
\$\begingroup\$

In my opinion your code is perfectly fine! I just found some fussy thinks.


HTML Comments

In Robert C. Martin's book Clean Code under HTML Comments you can read

HTML in source code comments is an abomination [...]. It makes the comments hard to read in the one place where they should be easy to read — the editor/IDE. If comments are going to be extracted by some tool (like Javadoc) to appear in a Web page, then it should be the responsibility of that tool, and not the programmer, to adorn the comments with appropriate HTML.

In to places you uses the <code>-tag. Which can be replaced by javadocs {@code}

For example from

<code>x1, x2, ..., xn</code> 

to

{@code x1, x2, ..., xn}

Duplicated Statement

The statement points.size() - 1 occurs three times inside the method computeClusternessMeasure. Even it is only a \$O(1)\$-statement it makes it easier to read the variable indexOfLastEntry instead of points.size() - 1


An Other Argument

Currently computeClusternessMeasure takes a Collection but instead you need a List. This "transformation" has nothing to do with the algorithm and a a collection makes additional to that no sense..

Furthermore you need to sort it..

Take a First-Class-Collection as Argument

If you want to keep the flexibility you could create a First-Class-Collection.

Any class that contains a collection should contain no other member variables. Each collection gets wrapped in its own class, so now behaviors related to the collection have a home.

The method signature I want to create is double computeClusternessMeasure(SortedMessurementPoints points)

public class SortedMessurementPoints {

      private List<Double> points;

      public SortedMessurementPoints(Collection<Double> points) {
          List<Double> asList = new ArrayList(points);
          Collection.sort(asList )
          this.points = asList;
      }

      public double get(int index) {
          return points.get(index);
      }

      public int indexOfLastEntry() {
            return points.size - 1;
      }
}
public double computeClusternessMeasure(SortedMessurementPoints points) {
    double minimumPoint = points.get(0);
    double maximumPoint = points.get(points.indexOfLastEntry());
    double range = maximumPoint - minimumPoint;

    if (range == 0.0) {
        // Once here, all data points are equal and so CM must be 1.0.
        return 1.0;
    }

    double expectedDifference = range / points.indexOfLastEntry();
    double sum = 0.0;

    for (int i = 0; i < points.indexOfLastEntry(); i++) {
        double currentDifference = points.get(i + 1) - points.get(i);
        sum += Math.min(Math.abs(expectedDifference - currentDifference),
                                     expectedDifference);
    }

    return sum / range;
}
\$\endgroup\$
  • \$\begingroup\$ In my 20+ year career I have never heard the term "zero based size". It is quite confusing because the type of indexing doesn't change the size. Might be clearer to use "indexOfLastEntry". \$\endgroup\$ – TorbenPutkonen Feb 21 at 18:13
  • \$\begingroup\$ @TorbenPutkonen renamed it! Good hint.. \$\endgroup\$ – Roman Feb 21 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.