Skip to content

7. Clustering of Submissions

Jump to bottom
Timur Sağlam edited this page Jan 17, 2023 · 4 revisions

Clustering Usage

By default, JPlag is configured to perform a clustering of the submissions. The clustering partitions the set of submissions into groups of similar submissions. The found clusters can be used candidates for potentially colluding groups. Each cluster has a strength score, that measures how suspicious the cluster is compared to other clusters.

Disabling Clustering

Clustering can take a long when there is a large number of submissions. Users who are not interested in clustering can safely disable it with the --cluster-skip option.

Clustering Configuration

Clustering can either be configured using the CLI options or programmatically using the ClusteringOptions class. Both options work analogously and share the same default values.

The clustering is designed to work out-of-the-box for running within the magnitude of about 50-500 submissions, but it can be tweaked when problems occur. For more submissions it might be necessary to increase Max-Runs or Bandwidth, so that an appropriate number of clusters can be determined.

Group Option Description Default
General Enable Controls whether the clustering is run at all. true
General Algorithm Which clustering algorithm to use.
Agglomerative Clustering
Agglomerative Clustering iteratively merges similar submissions bottom up. It usually requires manual tuning for its parameters to yield helpful clusters.
Spectral Clustering
Spectral Clustering is combined with Bayesian Optimization to execute the k-Means clustering algorithm multiple times, hopefully finding a "good" clustering automatically. Its default parameters should work O.K. in most cases.
 Agglomerative Clustering
General Metric The similarity score between submissions to use during clustering. Each score is expressed in terms of the size of the submissions A and B and the size of their matched intersection A ∩ B.
AVG (aka. Dice's coefficient)
AVG = 2 * (A ∩ B) / (A + B)
MAX (aka. overlap coefficient)
MAX = (A ∩ B) / min(A, B) Compared to MAX, this prevents obfuscation when a collaborator bloats his submission with unrelated code.
MIN (deprecated)
MIN = (A ∩ B) / max(A, B)
INTERSECTION (experimental)
INTERSECTION = A ∩ B
 AVG
Spectral Bandwidth For Spectral Clustering, Baysian Optimization is used to determine a fitting number of clusters. If a good clustering result is found during the search, numbers of clusters that differ by something in range of the bandwidth are also expected to good. Low values result in more exploration of the search space, high values in more exploitation of known results. 20.0
Spectral Noise The result of each k-Means run in the search for good clusterings is random. The noise level models the variance in the "worth" of these results. It also acts as a regularization constant. 0.0025
Spectral Min-Runs Minimum number of k-Means executions for spectral clustering. With these initial runs clustering sizes are explored. 5
Spectral Max-Runs Maximum number of k-Means executions during spectral clustering. Any execution after the initial (min-) runs tries to balance between exploration of unknown clustering sizes and exploitation of clustering sizes known as good. 50
Spectral K-Means Iterations Maximum number of iterations during each execution of the k-Means algorithm. 200
Agglomerative Threshold Only clusters with an inter-cluster-similarity greater than this threshold are merged during agglomerative clustering. 0.2
Agglomerative inter-cluster-similarity How to measure the similarity of two clusters during agglomerative clustering.
MIN (aka. complete-linkage)
Clusters are merged if all their submissions are similar.
MAX (aka. single-linkage)
Clusters are merged if there is a similar submission in both.
AVERAGE (aka. average-linkage)
Clusters are merged if their submissions are similar on average.
 AVERAGE
Preprocessing Pre-Processor How the similarities are preprocessed prior to clustering. Spectral Clustering will probably not have good results without it.
None
No preprocessing.
Cumulative Distribution Function (CDF)
Before clustering, the value of the cumulative distribution function of all similarities is estimated. The similarities are multiplied with these estimates. This has the effect of suppressing similarities that are low compared to other similarities.
Percentile
Any similarity smaller than the given percentile will be suppressed during clustering.
Threshold
Any similarity smaller than the given threshold will be suppressed during clustering.
 CDF

Clustering Architecture

All clustering related classes are contained within the de.jplag.clustering(.*) packages in the core project.

The central idea behind the structure of clustering is the ease of use: To use the clustering calling code should only ever interact with the ClusteringOptions, ClusteringFactory, and ClusteringResult classes:

classDiagram
    ClusteringFactory <.. CallingCode
    ClusteringOptions <.. CallingCode : creates
    ClusteringAdapter <.. ClusteringFactory
    ClusteringAlgorithm <.. ClusteringAdapter : runs
    ClusteringAlgorithm <.. ClusteringFactory : creates instances
    ClusteringPreprocessor <.. ClusteringFactory : creates instances
    PreprocessedClusteringAlgorithm <.. ClusteringFactory : creates
    ClusteringOptions <-- ClusteringFactory
    ClusteringAlgorithm <|-- PreprocessedClusteringAlgorithm
    ClusteringAlgorithm <-- PreprocessedClusteringAlgorithm : delegates to
    ClusteringPreprocessor ..o PreprocessedClusteringAlgorithm
    class ClusteringFactory{
        getClusterings(List~JPlagComparison~ comparisons, ClusteringOptions options)$ ClusteringResult~Submission~
    }
    class ClusteringOptions{
    }
    class ClusteringAlgorithm {
        <<interface>>
        cluster(Matrix similarities) ClusteringResult~Integer~
    }
    class ClusteringPreprocessor {
        <<interface>>
        preprocess(Matrix similarities) Matrix
    }
    class ClusteringAdapter{
        ClusteringAdapter(List~JplagComparison~ comparisons)
        doClustering(ClusteringAlgorithm algorithm) ClusteringResult~Submission~
    }
    class PreprocessedClusteringAlgorithm{
        cluster(Matrix similarities) ClusteringResult~Integer~
    }
    class CallingCode{

    }
Loading

New clustering algorithms and preprocessors can be implemented using the GenericClusteringAlgorithm and ClusteringPreprocessor interfaces which operate on similarity matrices only. ClusteringAdapter handles the conversion between de.jplag classes and matrices. PreprocessedClusteringAlgorithm adds a preprocessor onto another ClusteringAlgorithm.

Remarks on Spectral Clustering

Integration Tests

There are integration tests for the Spectral Clustering to verify, that a least in the case of two known sets of similarities the groups known to be colluders are found. However, these are considered to be sensitive data. The datasets are not available to the public and these tests can only be run by maintainers with access.

To run these tests the contents of the PseudonymizedReports repository must added in the folder jplag/src/test/resources/de/jplag/PseudonymizedReports.

Clone this wiki locally