classification
Title: Add a general selection function to statistics
Type: enhancement Stage: patch review
Components: Library (Lib) Versions: Python 3.8
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: mark.dickinson, remi.lapeyre, rhettinger, steven.daprano
Priority: normal Keywords: patch, patch

Created on 2019-01-18 14:04 by remi.lapeyre, last changed 2019-01-19 23:27 by steven.daprano.

Pull Requests
URL Status Linked Edit
PR 11609 open remi.lapeyre, 2019-01-18 14:05
PR 11609 open remi.lapeyre, 2019-01-18 14:05
Messages (6)
msg333964 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2019-01-18 14:04
Like discussed in #30999, the attached PR adds a general selection function to the statistics module. This allows to simply get the element at a given quantile of a collection.

https://www.cs.rochester.edu/~gildea/csc282/slides/C09-median.pdf
msg334019 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-01-18 22:34
I'm very interested in adding quartiles and general quantiles/fractiles, but I'm not so sure that this select(data, index) function would be useful. Can you explain how you would use this?
msg334022 - (view) Author: Rémi Lapeyre (remi.lapeyre) * Date: 2019-01-18 23:13
Wouldn't be the 5-th percentile be select(data, round(len(data)/20)?
msg334027 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-01-19 03:22
On Fri, Jan 18, 2019 at 11:13:41PM +0000, Rémi Lapeyre wrote:

> Wouldn't be the 5-th percentile be select(data, round(len(data)/20)?

Oh if only it were that simple!

Using the method you suggest, the 50th percentile is not the same as the 
median unless the length of the list is three more than a multiple of 
four. It also runs into problems for small lists where the index rounds 
down to zero.

Langford (2006) does a literature review and finds fifteen methods for 
calculating the quartiles (Q1, Q2, Q3), of which twelve are distinct and 
incompatible; Hyndman & Fan (1996) did similar for general quantiles and 
came up with nine, of which seven match Langford's.

I know of at least six other methods, which gives a total of 20 distinct 
ways of calculating quartiles or quantiles.

http://jse.amstat.org/v14n3/langford.html

https://robjhyndman.com/publications/quantiles/

I stress that these are not merely different algorithms which give the 
same answer, but different methods which sometimes disagree on their 
answers. So whichever method you use, some people are going to be 
annoyed or confused or both.

http://mathforum.org/library/drmath/view/60969.html

Other statistics libraries provide a choice, e.g.:

- R and Octave provide the same 9 as H&F.
- Maple provides 6 of those, plus 2 others.
- Wessa provides 5 that match H&F, plus another 3.
- SAS provides 5.
- even Excel provides 2 different ways.

Statisticians don't even agree on which is the "best" method. H&F 
recommend their method number 8. Langford recommends his method 4. I 
think that your suggestion matches Langford's method 14, which is H&F's 
method 3.

Selecting the i-th item from a list is the easy part. Turning that into 
meaningful quantiles, percentiles etc is where it gets really hairy. My 
favourite quote on this comes from J Nash on the Gnumeric mailing list:

    Ultimately, this question boils down to where to cut to
    divide 4 candies among 5 children. No matter what you do,
    things get ugly.
msg334036 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-01-19 06:01
> I'm very interested in adding quartiles and 
> general quantiles/fractiles, but I'm not 
> so sure that this select(data, index) function would be useful. 

I concur with Steven.
msg334075 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-01-19 23:27
Rémi. I've read over your patch and have some comments:

(1) You call sorted() to produce a list, but then instead of retrieving the item using ``data[i-1]`` you use ``itertools.islice``. That seems unnecessary to me. Do you have a reason for using ``islice``?

(2) select is not very useful on its own, we actually want it so we can calculate quantiles, e.g. percentiles, deciles, quartiles. If we want the k-quantile (e.g. k=100 for percentiles) then there are k+1 k-quantiles in total, including the minimum and maximum. E.g quartiles divide the data set into four equal sections, so there are five boundary values including the min and max.

So the caller is likely to be calling select repeatedly on the same data set, and hence making a copy of that data and sorting it repeatedly. If the data set is small, repeatedly making sorted copies is still cheap enough, but for large data sets, that will be expensive.

Do you have any thoughts on how to deal with that?
History
Date User Action Args
2019-01-19 23:27:32steven.dapranosetkeywords: patch, patch

messages: + msg334075
2019-01-19 06:01:30rhettingersetkeywords: patch, patch

messages: + msg334036
2019-01-19 03:22:05steven.dapranosetmessages: + msg334027
2019-01-18 23:13:35remi.lapeyresetmessages: + msg334022
2019-01-18 22:34:06steven.dapranosetkeywords: patch, patch

messages: + msg334019
2019-01-18 16:23:43mark.dickinsonsetkeywords: patch, patch
nosy: + mark.dickinson
2019-01-18 14:05:38remi.lapeyresetnosy: + rhettinger, steven.daprano
2019-01-18 14:05:10remi.lapeyresetkeywords: + patch
stage: patch review
pull_requests: + pull_request11338
2019-01-18 14:05:07remi.lapeyresetkeywords: + patch
stage: (no value)
pull_requests: + pull_request11337
2019-01-18 14:04:49remi.lapeyrecreate