开发者

Calculate estimated mathematical expectation of ranking data?

开发者 https://www.devze.com 2023-03-31 03:33 出处:网络
I have to sort a \"most popular apps RSS\" by app download 开发者_开发知识库count. Here is the problem:

I have to sort a "most popular apps RSS" by app download 开发者_开发知识库count. Here is the problem:

Suppose there are 1,000 apps.

The RSS data lists top 100 apps for each app category.

The RSS data also provides top 100 app list regardless of category.

RSS is sorted by each app's download count, but exact download count number is unknown.

Each app has two known properties: category, and its position on the RSS ranking.

Now I want to sort all of the 1,000 apps by its estimated download count.

The sorting do not need to be very accurate, just statistically speaking most possible would be OK.

How could I implement this sorting algorithm? TIA.


you can process this way : (I assume each app belongs to only one category)

Let say you have the following ranking for each category C1 ..C10

C1             C2    ...             C10

app1-1       app2-1

app1-2       &pp2-2

..           ...

app1-100     app2-100              app10-100

and

the overall 100 top apps classment (for example):

C  app1-1  app1-2  app2 -1  ... app2-10  

Now using these 2 tables, first you need to order C1 to C10 in the same order as app1-1 to app10-1 appear in list C, so you "know" (it's more like a guess) what Category is the more important in term of ranking.

Then use this information to sort the rest .


Now I'm gona use a simpler example to show how to order the rest of the elements.

let's take 3 categories and 12 apps .

C1      C2      C3

app1    app21   app31   

app2    app22   app32

app3    app23   app33

app4    app24   app34

and C = app1 app2 app21 app31

1.first mark all elemnt in C in the table :

app1    app21 ->app31   
 |   /
app2    app22   app32

app3    app23   app33

app4    app24   app34

2.second, sort the remaining elements

Since you don't have more information, a good approximation would be to look at each line from left to right (from larger ranked top list to smaller ranked top list) which gives :

app3 app22 app32 app4 app23 app33 app24 app34

then the overall classement would be :

app1 app2 app21 app31 app3 app22 app32 app4 app23 app33 app24 app34

I hope this example makes my ideas clear and that it helps.

I think this approach uses all the information you have in C1 ...C10 and C.


A simple way is to use the overall top-100 to determine which category to get the next app from.

In pesudo-code:

While (not finished) 
  i++
  category = Overall_list(i).getCategory()
  Overall_list.add(get next app from list for category)
end while

Any category(s) that have no entry in the overall top-100 will be added last.


Build a directed graph as follows:

  1. Each app is a node.
  2. If app X ranks above app Y on any of the lists, put an edge pointing from X to Y. Note: you really only need to add an edge if X is one rank higher than Y on any list.
  3. It might be possible that some of the #1-ranked items on the category lists don't appear on the total ranking list. In this case, I would add edges pointing from the lowest-ranked item on the total list to each of these items to make the graph connected.

Then, do a topological sort on the constructed graph. The resulting ordering will be guaranteed to be compatible with each individual top 100 list.

This approach will work even if an app appears in more than one category list -- assuming that the category lists are mutually consistent (e.g.: ranked according to total downloads and not, say, category downloads). For example, if you ever have a case where X is ranked above Y on one list but Y is ranked above X on another list, then this won't really work (and I'm not sure what would).

Without more information (e.g.: some kind of probability model), I can't really interpret what "statistically speaking most possible" really means.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号