mstknnclust (version 0.3.1)

generate.knn: Generates a kNN graph

Description

This function generates the k-Nearest Neighbors (kNN) graph which is a subgraph contains edges between nodes if, and only if, they are one of the k nearest neighbors considering the edges costs (distances). Each node represents an object of the complete graph.

Usage

generate.knn(edges.complete.graph, suggested.k)

Value

A list with the elements

edges.knn.graph

A object of class "data.frame" with three columns (object_i, object_j, d_ij) representing the d_ij between object_i and object_j that are part of the kNN graph.

knn.graph

A object of class "igraph" which is the k-Nearest Neighbors (kNN) graph generated.

k

The k value determined by the definition.

Arguments

edges.complete.graph

A object of class "data.frame" with three columns (object_i, object_j, d_ij) representing the distance d_ij between object_i and object_j.

suggested.k

It is an optional argument. A numeric value representing the suggested number of k-nearest neighbors to consider to generate the kNN graph.

Author

Mario Inostroza-Ponta, Jorge Parraga-Alava, Pablo Moscato

Details

During its generation, the k value is automatically determined by the definition: $$k = min{\lfloor \ln(|nodes.list|) \rfloor; min k | kNN is connected; suggested.k }$$ If suggested.k parameter is not provided, it is not considered by the definition.

Examples

set.seed(1987)

##Generates a data matrix of dimension 50X13
n=50; m=13
x <- matrix(runif(n*m, min = -5, max = 10), nrow=n, ncol=m)

##Computes a distance matrix of x.

library("stats")
d <- base::as.matrix(stats::dist(x, method="euclidean"))

##Generates complete graph (CG) without suggested.k parameter

cg <- generate.complete.graph(1:nrow(x),d)

##Generates kNN graph
knn <- generate.knn(cg)

##Visualizing kNN graph
plot(knn$knn.graph,
main=paste("kNN \n k=", knn$k, sep=""))



##Generates complete graph (CG) with suggested.k parameter

cg <- generate.complete.graph(1:nrow(x),d)

##Generates kNN graph
knn <- generate.knn(cg, suggested.k=4)

##Visualizing kNN graph
plot(knn$knn.graph,
main=paste("kNN \n k=", knn$k, sep=""))