Danny, Here's another approach that doesn't use sorting. Instead, after calculating distances it considers a threshold on distance and counts how many cases are within the threshold. Then a search over thresholds is conducted to find a threshold yielding the desired number of cases. Then case numbers satisfying the found threshold are returned.
Why go to this bother to avoid sorting? Since the computation required to sort N distances grows more quickly than the computation required to make a pass through a vector of distances and count values less than a threshold, for some N this approach ought to be more efficient than one based on sorting. Well, maybe, if the number of iterations grows slowly enough with N. Call it a conjecture. On the other hand, the N for which this occurs depends on the efficiency of the sort algorithm (pretty darned efficient and using compiled code, I imagine) and the efficiency of the search algorithm. Here I use uniroot, which isn't really designed with step functions in mind, so perhaps there are possible improvements. So I couldn't say whether this will work faster than the other suggestions you've gotten with your data, or even for data one is likely to ever see. If there are ties for the 6th-nearest case (counting the point itself), this routine should either include or exclude all the ties, whichever comes closest to yielding 5 points. Here's the code: ## Args: ## CaseNo: Row number of case for which to find nearest neighbors. ## x: A numeric matrix. ## k: The desired number of neighbors, not counting the point of interest. ## TempIndex: Index of row numbers. If you use this function many many times you ## might gain an iota of efficiency by creating this vector once and ## passing it in as an argument with each call. Probably not worth the ## trouble, I couldn't help myself.... ## verbose: Tells you how many iterations uniroot used, if you're curious. ## Value: ## A vector of (hopefully) k row numbers indicating the k nearest neighbors. nearestKNeighbors <- function(CaseNo, x, k, TempIndex = 1:nrow(x), verbose = F) { ## make sure x is a matrix if(!is.matrix(x)) stop("x must be a matrix.") TempVect <- x[CaseNo, ] SquaredDistances <- apply(x, 1, function(s) sum((s - TempVect)^2) ) tempFun <- function(h) sum(SquaredDistances < h^2) - (k + 1) TempSolution <- uniroot(tempFun, interval = range(SquaredDistances)) if(verbose) cat("Required", TempSolution$iter, "iterations.\n") sort(setdiff(TempIndex[SquaredDistances < TempSolution$root^2], CaseNo)) } You would apply this to each row of your dataset using some variety of "apply" or a loop. I don't know if memory usage would differ. In the event of ties, you may not have 5 neighbors, so I might put the results in a list, which can accommodate different lengths in each component (indeed, it can accommodate completely different data structures): ## data in matrix temp.matrix ListOutput <- lapply(as.list(1:nrow(temp.matrix)), function(s) nearestKNeighbors(s, temp.matrix, 5)) or ListOutput <- vector(nrow(temp.matrix), mode = "list") for(i in 1:nrow(temp.matrix)) ListOutput[[i]] <- nearestKNeighbors(i, temp.matrix, 5) and then you can manipulate the list however you like. For instance, to see if all components have length 5, all(unlist(lapply(ListOutput, length)) == 5) or, if there are such components, find out which one(s): (1:length(ListOutput))[unlist(lapply(ListOutput, length)) != 5] Welcome to R! Best, -Jim Garrett *** > I've only begun investigating R as a substitute for SPSS. > I have a need to identify for each CASE the closest (or most similar) 5 > other CASES (not including itself as it is automatically the closest). I > have a fairly large matrix (50000 cases by 50 vars). In SPSS, I can use > Correlate > Distances to generate a matrix of similarity, but only on a small > sample. The entire matrix can not be processed at once due to memory limitations. > The data are all percents, so they are easy comparable. > Is there any way to do this in R? > Below is a small sample of the data (from SPSS) and the desired output. > Thanks, > Danny ********************************************************************** This message is intended only for the designated recipient(s...{{dropped}} ______________________________________________ [EMAIL PROTECTED] mailing list https://www.stat.math.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html