3
\$\begingroup\$

I am trying to implement an algorithm for detecting outliers in R and I am pretty new to the language. The outlier algorithm is described in this paper in detail on page 10-11, but to summarize it works like this:

Algorithm – Outlier Detection using K-Nearest Neighbor Data Distributions

  1. Find the set S(K) of K nearest neighbors to the test data point O.
  2. Calculate the K distances between O and the members of S(K). These distances define fK(d,O).
  3. Calculate the K(K-1)/2 distances among the points within S(K). These distances define fK(d,K).
  4. Compute the cumulative distribution functions CK(d,O) and CK(d,K), respectively, for fK(d,O) and fK(d,K).
  5. Perform the K-S Test on CK(d,O) and CK(d,K). Estimate the p-value of the test.
  6. Calculate the Outlier Index = 1-p. If Outlier Index > 0.95, then mark O as an “Outlier”. The Null Hypothesis is rejected. If 0.90 < Outlier Index < 0.95, then mark O as a “Potential Outlier”. If p > 0.10, then the Null Hypothesis is accepted: the two distance distributions are drawn from the same population. Data point O is not marked as an outlier.

I implemented this in the following code but I am unsure if this code is appropriate for R in terms of structure and style (compared with Python). Also, I don't know if there is a more efficient way than the simple step by step way I have done. I added code comments to delineate each step of the algorithm.

outlier_test <- function(data , neighbors){
  #Find the set S(K) of K nearest neighbors to the test data point O.
  sk <- nn2(data, k=neighbors)$nn.idx #matrix of indices of neighbors

  #Calculate the K distances between O and the members of S(K). These distances define fK(d,O).
  outlier_distances <- nn2(data, k=neighbors)$nn.dist #distances between value and its neighbors

  #Calculate the K(K-1)/2 distances among the points within S(K). These distances define fK(d,K).
  plyr::adply(sk, .margins = 1, function(row) { data[row, ] })

  df1<- plyr::alply(sk, .margins=1, function(row){data[row,]})
  df1 = plyr::ldply(df1, rbind)
  neighbor_distances <- plyr::alply(df1, 1, function(row) c(dist(unlist(row))))

  neighbor_distances <- df1 %>% 
    dplyr::group_by(X1) %>% 
    do({
      row_data <- .
      my_dist <- dist(row_data[ ,c(colnames(data)[1],colnames(data)[2])])
      as.data.frame(t(as.vector(my_dist)))
      }) %>% 
    dplyr::ungroup() %>% 
    dplyr::select(-X1) %>% 
    as.matrix()

  #daply(test, .(X1), function(x) as.vector(dist(x))) This  is an alternative way to do the above piping

  #Compute the cumulative distribution functions CK(d,O) and CK(d,K), respectively, for fK(d,O)
  #and fK(d,K).
  # Since ks.test function in R can take vectors of values, we don't need to explicitly find the ECDF of our samples

  #Perform the K-S Test on CK(d,O) and CK(d,K). Estimate the p-value of the test.
  all_pvalues = sapply(1:nrow(outlier_distances), function(i) ks.test(as.vector(outlier_distances[i,]), as.vector(neighbor_distances[i,]))$p.value)

  #Calculate the Outlier Index = 1-p.
  outlier_index = 1-all_pvalues
  #If Outlier Index > 0.95, then mark O as an Outlier. The Null Hypothesis is rejected.
  #If 0.90 < Outlier Index < 0.95, then mark O as a Potential Outlier.
  #If p > 0.10, then the Null Hypothesis is accepted: the two distance distributions are drawn from
  #the same population. Data point O is not marked as an outlier
  return(outlier_index)
}
\$\endgroup\$
1
\$\begingroup\$

In my opinion there are only few aspects:

  • Consistent use of assignment operator (either = or <-, mind that in special cases they aren't equivalent)
  • I like that you use package-references (::), you forgot about RANN:: though
  • You could use the purrr-package to replace sapply-type commands, which gives you more control over the output
  • When you refer to columns in a fixed position way such as colnames(data)[1] you should make sure that the data structure you give to the function is as expected
\$\endgroup\$
  • \$\begingroup\$ Thanks I will make these changes, especially the one regarding your final point, which seems critical to me. \$\endgroup\$ – guy Sep 20 '17 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.