Good morning! I recently implemented a KD tree in JAVA for faster
kernel density estimation (part of the code follows). It went well. To
hook it with R, however, has proved more difficult. My question is: is
it possible to implement the algorithm in R? My impression seems to
indicate no as the code requires a complete class-object framework that
R does not support. But is there an R package or something that may
make it possible? Thanks in advance for your help.
Java implementation of KD tree:
public class Kdnode {
private double[] center; //center of the bounding box
private double diameter; //maximum distance from center to
anywhere within the bounding box
private int numOfPoints; //number of source data points in the
bounding box
private Kdnode left, right;
public Kdnode(double[][] points, int split_dim, int [][]
sortedIndices, double[][] bBox) {
//bBox: the bounding box, 1st row the lower bound, 2nd row
the upper bound
numOfPoints = points.length;
int d = points[0].length;
center = new double[d];
for(int j=0; j<d; j++) center[j] =
(bBox[0][j]+bBox[1][j])/2.;
diameter = get_diameter(bBox);
if(numOfPoints==1) {
diameter = 0.;
for(int j=0; j<d; j++) center[j] = points[0][j];
left = null;
right = null;
}
else {
int middlePoint =
sortedIndices[split_dim][numOfPoints/2];
double splitValue = points[middlePoint][split_dim];
middlePoint =
sortedIndices[split_dim][numOfPoints/2-1];
double splitValue_small =
points[middlePoint][split_dim];
int left_size = numOfPoints/2;
int right_size = numOfPoints - left_size;
double[][] leftPoints = new double[left_size][d];
double[][] rightPoints = new double[right_size][d];
int[][] leftSortedIndices = new int[d][left_size];
int[][] rightSortedIndices = new int[d][right_size];
int left_counter = 0, right_counter = 0;
int[] splitInfo = new int [numOfPoints];
for(int i = 0; i < numOfPoints; i++) {
if(points[i][split_dim] < splitValue) {
for(int j=0; j<d; j++) leftPoints[left_counter][j] =
points[i][j];
splitInfo[i] = right_counter;
left_counter++;
}
else {
for(int j=0; j<d; j++) rightPoints[right_counter][j] =
points[i][j];
splitInfo[i] = left_counter;
right_counter++;
}
}
// modify appropriately the indices to correspond to the new
lists
for(int i = 0; i < d; i++) {
int left_index = 0, right_index = 0;
for(int j = 0; j < numOfPoints; j++) {
if(points[sortedIndices[i][j]][split_dim] <
splitValue)
leftSortedIndices[i][left_index++] =
sortedIndices[i][j] -
splitInfo[sortedIndices[i][j]];
else rightSortedIndices[i][right_index++] =
sortedIndices[i][j]
- splitInfo[sortedIndices[i][j]];
}
}
// Recursively compute the kdnodes for the points in the two
splitted spaces
double[][] leftBBox = new double[2][];
double[][] rightBBox = new double[2][];
for(int i=0; i<2; i++) {
leftBBox[i] =
(double[])bBox[i].clone();
rightBBox[i] =
(double[])bBox[i].clone();
}
leftBBox[1][split_dim] = splitValue_small;
rightBBox[0][split_dim] = splitValue;
int next_dim = (split_dim + 1) % (d);
left = new Kdnode(leftPoints, next_dim, leftSortedIndices,
leftBBox);
right = new Kdnode(rightPoints, next_dim, rightSortedIndices,
rightBBox);
}
}
public double evaluate(double[] target, double delta, double
bandwidth) throws Exception
{
double dis_2_center = Common.distance(target,
center)/bandwidth;
double dm = diameter/bandwidth;
if(dis_2_center >= 1+dm) return 0.;
if(numOfPoints==1) return Common.K(dis_2_center);
/*if(dis_2_center<1)
{
double temp2 = dm*Common.KDeriv(dis_2_center);
if(temp2<delta) return
Common.K(dis_2_center)*numOfPoints;
} */
return left.evaluate(target,delta, bandwidth) +
right.evaluate(target,delta, bandwidth);
}
public double get_diameter(double[][] bBox)
{
double value = 0., diff;
for (int i=0; i<bBox[0].length;i++)
{
diff = (bBox[1][i] - bBox[0][i])/2.;
value += diff*diff;
}
return Math.sqrt(value);
}
}
=====
Jason Liao, http://www.geocities.com/jg_liao
Dept. of Biostatistics, http://www2.umdnj.edu/bmtrxweb
University of Medicine and Dentistry of New Jersey
phone 732-235-5429, School of Public Health office
phone 732-235-8611, Cancer Institute of New Jersey office
moble phone 908-720-4205
______________________________________________
[EMAIL PROTECTED] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
