12
$\begingroup$

As an example application, consider following two properties of Stack Overflow users: reputation and profile view counts.

It is expected that for most users those two values will be proportional: high rep users attract more attention and therefore get more profile views.

Therefore, it is interesting to search for users who have a lot of profile views compared to their total reputation.

This could indicate that that user has an external source of fame. Or maybe just that they have interesting quirky profile pictures and names.

More mathematically, each bi-dimensional sample point is an user, and each user has two integral values ranging from 0 to +infinity:

  • reputation
  • number of profile views

Those two parameters are expected to be linearly dependent, and we'd like to find sample points which are the largest outliers to that assumption.

The naive solution would be of course to just take profile views, divide by reputation, and sort.

However, this would give results which are not statistically meaningful. For example, if an user answered on question, got 1 upvote, and for some reason had 10 profile views, which easy to fake, then that user would appear in front of a much more interesting candidate that has has 1000 upvotes and 5000 profile views.

In a more "real world" use case, we could try to answer for example "which startups are the most meaningful unicorns?". E.g. If you invest 1 dollar with tiny equity, you create an unicorn: https://www.linkedin.com/feed/update/urn:li:activity:6362648516858310656

Concrete clean easy-to-use real world data

To test your solution to this problem, you can just use this small (75M compressed, ~10M users) preprocessed file extracted from the 2019-03 Stack Overflow data dump:

wget https://github.com/cirosantilli/media/raw/master/stack-overflow-data-dump/2019-03/users_rep_view.dat.7z
7z x users_rep_view.dat.7z

which produces the UTF-8 encoded file users_rep_view.dat which has a very simple plain text space separated format:

Id Reputation Views DisplayName
-1 1 649 Community
1 45742 454747 Jeff_Atwood
2 3582 24787 Geoff_Dalgas
3 13591 24985 Jarrod_Dixon
4 29230 75102 Joel_Spolsky
5 39973 12147 Jon_Galloway
8 942 6661 Eggs_McLaren
9 15163 5215 Kevin_Dente
10 101 3862 Sneakers_O'Toole

This is how the data looks like on a log scale:

enter image description here

gnuplot script.

It would then be interesting to see if your solution actually helps us discover new unknown quirky users!

The initial data was obtained from the 2019-03 data dump as follows:

wget https://archive.org/download/stackexchange/stackoverflow.com-Users.7z

# Produces Users.xml
7z x stackoverflow.com-Users.7z

# Preprocess data to minimize it.
./users_xml_to_rep_view_dat.py Users.xml > users_rep_view.dat
7z a users_rep_view.dat.7z users_rep_view.dat

sha256sum stackoverflow.com-Users.7z users_rep_view.dat.7z > checksums

Source for users_xml_to_rep_view_dat.py.

After selecting your outliers by reordering users_rep_view.dat, you can get an HTML list with hyperlinks to quickly view the top picks with:

./users_rep_view_dat_to_html.py users_rep_view.dat | head -n 1000 > users_rep_view.html
xdg-open users_rep_view.html

Source for users_rep_view_dat_to_html.py.

This script can also serve as a quick reference of how to read the data into Python.

Manual data analysis

Immediately by looking at the gnuplot graph we see that as expected:

  • the data is a approximately proportional, with greater variances for low rep or low view count users
  • low rep or low view count users are clearer, which means that they have higher account IDs, which means that their accounts are newer

In order to get some intuition about the data, I wanted to drill down some far up points in some interactive plotting software.

Gnuplot and Matplotlib could not handle such a large dataset, so I gave VisIt a shot for the first time and it worked. Here is a detailed overview of all plotting software I've tried: https://stackoverflow.com/questions/5854515/large-plot-20-million-samples-gigabytes-of-data/55967461#55967461

OMG that was hard to get running. I had to:

  • download the executable manually, there is no Ubuntu package
  • convert the data to CSV by hacking up users_xml_to_rep_view_dat.py quickly because I could not easily find how to feed it space separated files (lesson learnt, next time I'll go straight for CSV)
  • fight for 3 hours with the UI
    • default point size is a pixel, which gets confused with the dust on my screen. Move to 10 pixel spheres
    • there was an user with 0 profile views, and VisIt it correctly refused to do the logarithm plot, so I used data limits to get rid of that point. This reminded me that gnuplot is very permissive, and will happily plot anything you throw at it.
    • add axis titles, remove username, and other things under "Controls" > "Annotations"

Here's how my VisIt window looked like after I got tired of this manual work:

enter image description here

The Letters are points that I selected manually with the awesome Picks feature:

  • you can see the exact Id for each point by increasing the floating point precision in the Picks window > "Float Format" to %.10g
  • you can then dump all hand picked points to a txt file with "Save Picks as". This allows us to produce a clickable list of interesting profile URLs with some basic text processing

TODOs, learn how to:

  • see the profile name strings, they get converted to 0 by default. I just pasted profile Ids into the browser
  • pick all points in a rectangle in one go

And so finally, here are a few users which should likely show high up on your ordering:

Possible solutions

I've heard about the Wilson score confidence interval from https://www.evanmiller.org/how-not-to-sort-by-average-rating.html which "balance[s] the proportion of positive ratings with the uncertainty of a small number of observations", but I'm not sure how to map that to this problem.

In that blog post, the author recommends that algorithm to find items that have a lot more upvotes than downvotes, but I'm not sure if the same idea applies to the upvote / profile view problem. I was thinking of taking:

  • profile views == upvotes there
  • upvotes here == downvotes there (both "bad")

but I'm not sure if it makes sense because on the up/downvote problem, each item being sorted has N 0 / 1 vote events. But on my problem, each item has two events associated to it: getting the upvote, and getting the profile view.

Is there a well known algorithm that gives good results for this kind of problem? Even knowing the precise problem name would help me find existing literature.

Bibliography

Tested in Ubuntu 18.10, VisIt 2.13.3.

$\endgroup$
  • 1
    $\begingroup$ I'm new to this, so please feel free to edit the title / question to make the terminology more correct. Thanks. $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 Nov 10 '18 at 20:46
  • $\begingroup$ this looks like you are searching for outliers. I would use a technique in this space $\endgroup$ – probabilityislogic Apr 26 at 2:00
  • 1
    $\begingroup$ @probabilityislogic btw, I've updated the question with some concrete easy to use data. $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 Apr 28 at 11:21
  • 1
    $\begingroup$ I'd just like to say this is not only an interesting question, but also very concrete and well formatted. An example to look up to. Good job @Ciro! $\endgroup$ – Julio Cezar Silva May 3 at 12:14
  • 1
    $\begingroup$ @JulioCezarSilva thanks!! I wasn't expecting to learn about high perf interactive plotting this time, but I did. Classic. $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 May 3 at 12:19
4
+100
$\begingroup$

I think the Wilson score confidence interval can be applied directly to your problem. The score used in the blog was a lower bound of the confidence interval instead of an expected value.

Another method for such problem is to correct (bias) our estimation towards some prior knowledge we have, for example the overall view/rep ratio.

Say the number of views per reputation follows a normal distribution $v \sim N(\mu,\sigma) $, then the view/rep ratio can be interpreted as the maximum likelihood estimation (MLE) of the distribution mean $\mu$.

The problem is, as you mentioned, when there is insufficient data, the MLE result is of high variance (overfitting). A simple solution for this is to introduce a prior distribution of $\mu$ and do maximum a posteriori estimation (MAP). The prior distribution $p(\mu)$ can be another normal distribution estimated from all the samples we have.

In practice, this is essentially a weighted average of the overall view/rep ratio and the user view/rep ratio, $$μ_{MAP}=\frac{n\mu_{MLE}+c\mu_0}{n+c}$$ where $n$ is the number of reps a user have, $c$ is a constant, $\mu_{MLE}$ is the view/rep ratio of the user and $\mu_0$ the overall view/rep ratio.


To compare the two methods (Wilson score confidence interval lower bound and MAP), they both give an accurate estimation when there are sufficient data (reps), when the number of reps is small, Wilson lower bound method will bias towards zero and MAP will bias towards the mean.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your reply! I've updated the question with some concrete and easy to use data, let's see if someone manages to make some fun findings. $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 Apr 28 at 11:21
  • 1
    $\begingroup$ @CiroSantilli新疆改造中心996ICU六四事件 good job! $\endgroup$ – dontloo Apr 28 at 11:27

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.