title: detecting outliers in a sparse distribution?
body: <p>i would like to find what the best way to detect outliers is. here is the problem and some things which probably will not work. let's say we want to fish out some quasi-uniform data from a dirty varchar(50) column in mysql. let's start by doing an analysis by string length.</p>
  
  <pre><code>| strlen |  freq  | 
  |      0 |   2312 |
  |      3 |     45 |
  |      9 |     75 |
  |     10 |  15420 |
  |     11 |    395 |
  |     12 |    114 |
  |     19 |     27 |
  |     20 |   1170 |
  |     21 |     33 |
  |     35 |     9  |
  </code></pre>
  
  <p>what i would like to do is devise an algorithm to determine which string length has a high probability of being purposefully unique rather than being typeo's or random garbage. this field has the possibility of being an "enum" type, so there can be several frequency spikes for valid values. clearly 10 and 20 are valid, 0 is just omitted data. 35 and 3 might be some random trash despite both being very different in frequency. 19 and 21 might be type-os around the 20 format. 11 might be type-os for 10, but what about 12?</p>
  
  <p>it seems simply using occurrence frequency % is not enough. there need to hotspots of higher "just an error" probability around the obvious outliers.</p>
  
  <p>also, having a fixed threshold fails when there are 15 unique lengths which can vary by between 5-20 chars, each with between 7% - 20% occurrence.</p>
  
  <p>standard deviation will not work because it relies on the mean. median absolute deviation probably wont work because you can have a high frequency outlier that cannot be discarded.</p>
  
  <p>yes there will be other params for cleaning the data in the code, but length seems to very quickly pre-filter and classify fields with any amount of structure.</p>
  
  <p>are there any known methods which would work efficiently? i'm not very familiar with Bayesian filters or machine learning but maybe they can help?</p>
  
  <p>thanks!
  leon</p>