Package 'mstclustering'

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.

---