1
$\begingroup$

I'm having a final exam on Data Warehouses and Data Mining (Computer Science bachelor), and the professor recommends some extra exercises on his web-page, as extra material for studying before the exam.

In them, lies the following exercise, among others:

In the following image, we can see three well-defined clusters and two outliers. Describe the application of a technique which will detect the outlier points without performing clustering, however knowing that all [non-outlier] points form clusters of size $>10$.

Yes, I drew this because the book image was awful

Now, I don't know of any techniques that detect outliers without actually performing clustering, and I looked up the relevant chapters in the teaching book to see if any algorithms or techniques are described. I found a total of one (1!) pages, that briefly states:

To remove outliers, we calculate the sum of distances of a point towards all others. To calculate the distances, we can use Mahalanobis Distance.

After which, the writer of the book (also my class professor) casually lists the following result plot, with no explanation on how it was produced (note that the data in this plot are irrelevant from the exercise above, and are from an earlier book example):

enter image description here

And that's it. It doesn't even list a formula or objective function to calculate Mahalanobis distance, which I had to look up on Wikipedia.

Apart from that, the exercise does not mention standard deviation, so the two prominent results I got from stats.stackexchange are of no use (this question and also this one).

I'm frustrated because this is supposed to be Exercise 2, which should mean "easy" and "introductionary", and should require a minimal description and effort to solve, but here I stand stumped.

Does anyone know of any algorithms that do this, relevant to us knowing in-advance that the points form clusters of $size>10$? Any help or pointers towards the right direction would be greatly appreciated. My first thoughts was to describe applying k-means or DBSCAN, but these are actual clustering techniques, and the exercise calls for just outlier detection without clustering.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Hint: What does the distribution of the nearest-neighbor distance look like? $\endgroup$
    – whuber ♦
    Jun 9, 2018 at 21:17
  • $\begingroup$ @whuber For every object, I could 1) Calculate the distance of it from all others 2) Find the 10 Minimums 3) Store them as outlier_scores. Yes, the two "real" outliers in the graph are going to have huge outlier_scores when compared to every other object, but how can I correctly generalize and say "Yeah their outlier_scores is x times bigger, therefore they're outliers" ? $\endgroup$
    – Dimitris S.
    Jun 9, 2018 at 22:38
  • 1
    $\begingroup$ For each object, compute the distance to its nearest neighbor. Draw a picture of the distribution of these numbers: the presence of the outliers will be abundantly clear--and no "clustering" is involved in this process. $\endgroup$
    – whuber ♦
    Jun 10, 2018 at 16:33
  • $\begingroup$ @whuber Thank you. Would I also be correct in thinking that a better pointer of being an outlier or not would be a sum/average of the distances to the 10 closest neighbors, not just one? $\endgroup$
    – Dimitris S.
    Jun 10, 2018 at 20:37
  • 1
    $\begingroup$ The problem with that characterization is that "10" was derived from your visual assessment of clustering. The distribution of nearest-neighbor distances identifies outliers regardless of what value you take as the threshold. $\endgroup$
    – whuber ♦
    Jun 10, 2018 at 23:36

1 Answer 1

Reset to default
2
$\begingroup$

Outliers in that data set can easily be found with

  • nearest neighbor outlier detection (KNN)
  • local outlier factor (LOF)
  • local outlier probabilities (LOOP)

And many more. Choose a small k value, less than 10. For example k=1 for the first, or k=5 for the others.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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