Package 'mstclustering'

Title: "MST-Based Clustering"
Description: Implements a minimum-spanning-tree-based heuristic for k-means clustering using a union-find disjoint set and the algorithm in Kruskal (1956) <doi:10.1090/S0002-9939-1956-0078686-7>.
Authors: Kevin Michael Frick <[email protected]>
Maintainer: Kevin Michael Frick <[email protected]>
License: AGPL (>= 3)
Version: 1.0.0.0
Built: 2025-02-17 05:15:34 UTC
Source: https://github.com/cran/mstclustering

Help Index


find.set

Description

Find the set an element belongs to.

Usage

find.set(i, ufds)

Arguments

i

The element to check.

ufds

A data.table representing a UFDS.

Value

An integer: the root node of the set the element belongs to.


gen.child.list.mst

Description

Generate an adjacency list

Usage

gen.child.list.mst(clust.edge.list, m)

Arguments

clust.edge.list

The return value of the kruskal() function.

m

Number of nodes.

Value

An adjacency list in the form of a list of vectors.


gen.edge.list

Description

Generate edge list from a distance matrix Duplicates are not deleted, because they will not be counted by Kruskal's algorithm If a check is O(1), this only adds an O(E) overhead, which is negligible

Usage

gen.edge.list(mat)

Arguments

mat

The distance matrix.

Value

A data frame with three columns: 'from', 'to', 'dist'.


is.same.set

Description

Check if two elements are in the same set

Usage

is.same.set(i, j, ufds)

Arguments

i

The first element in the tuple.

j

The second element in the tuple.

ufds

A data.table representing a UFDS.

Value

TRUE if the elements are in the same set, FALSE otherwise.


kruskal

Description

Kruskal's algorithm for MST computation.

Usage

kruskal(edge.list, m)

Arguments

edge.list

A data frame with columnns 'from', 'to', 'dist'.

m

Number of nodes.

Value

A list of edges in the MST, in the same format as the input argument edge.list.


mst.cluster

Description

Run clustering using MST. Before calling this function, remove some edges from the MST, for example the k-1 heaviest.

Usage

mst.cluster(child.list.mst, m, k)

Arguments

child.list.mst

The return value of the gen.child.list.mst() function with k-1 edges removed.

m

Number of nodes.

k

The number of clusters.

Value

A vector whose k-th element is the cluster the k-th point belongs to.

Examples

iris.clean <- iris[,-5]
iris.dist <- as.matrix(dist(iris.clean))
iris.edge.list <- gen.edge.list(iris.dist)
m <- nrow(iris.dist)
iris.mst.edge.list <- kruskal(iris.edge.list, m)
k <- 3
n.edges <- nrow(iris.mst.edge.list)
iris.mst.edge.list <- iris.mst.edge.list[1:(n.edges - (k - 1)),]
iris.child.list.mst <- gen.child.list.mst(iris.mst.edge.list, m)
iris.clust.mst <- mst.cluster(iris.child.list.mst, m, k)

reset.ufds

Description

Initialize UFDS

Usage

reset.ufds(m)

Arguments

m

Number of elements.

Value

A data table containing a 'rank' column and a 'parent' column.


union.set

Description

Join the sets the two elements passed as arguments belong to.

Usage

union.set(i, j, ufds)

Arguments

i

The first element in the tuple.

j

The second element in the tuple.

ufds

A data.table representing a UFDS.

Value

No return value, called for side effects on rank and p.