Skip to content

May 9, 2012

29

获取人群漂亮程度数据的一个方法

作者: physixfan

这个想法最初的动机是这样的:我想做一些社会学的调查,研究一下一些统计规律。而在我想做的社会调查里面,涉及到一个很难处理的自变量:被调查对象的漂亮程度,也就是大家通常说的7分女啊1分男啊之类的对人的相貌的评分。如果有了人群的漂亮程度的数据,我就可以把它作为自变量定量地研究很多问题,诸如:漂亮程度和幸福感的相关性;漂亮程度和智商的相关性;漂亮程度和收入的相关性;配偶双方的漂亮程度的差别有多大……如果得到的结果是相关性很强的,那就算是一个对人类现况的客观认识吧,如果相关性很弱,那就可以给广大不是很漂亮的人们一个很好的心理安慰了。

但现在主要问题就是漂亮程度这个量很难获取。总不能是发问卷的人给被调查的人直接打分吧,这肯定不科学。于是我想到了一个也许可行的办法:利用社交网络人人网,做一个应用,从这个应用当中获取需要的信息。

这个应用的设计如下:

进入应用之后,你可以看到随机抽出来的两位你的好友(这二人必须性别一致)(也可以不随机而是由确定的算法抽出两个好友),然后你需要做的事情就是选择这两个人谁更漂亮。因为人人网是个真实的社交网络,这个选择可以是基于你对他们的整体印象,而不只是头像照片。每次选择完毕,你都可以获得1个积分。积分多了可以做如下几件事情:10分可以看自己的漂亮程度打分;20分可以查看自己的好友里面谁最漂亮;30分可以查看某个特定好友的漂亮程度打分;诸如此类。设置这些功能只是为了保证大家有打分的热情,由人类的虚荣心和窥探欲所驱动,以前有成功的例子,如那个蛋疼的应用“好友真相”。

通过这个应用,我们可以获得一个很大很复杂的有向图:每个节点代表一个人,两个节点之间的带方向的边就代表谁比谁更漂亮,边是带着权重的,权重就表示有多少人认为A比B更漂亮。对这张图进行处理就可以得到一个排序,通过这个排序最终就可以得到每个人的漂亮程度打分,比如排名前10%的算作10分,排名10%~20%的人算作9分,当然这个比例也可以按照正态分布来调整,总之有了排序就一定可以得到一个打分。因为我不是CS专业的,所以对这张图到底该怎么处理还没有特别清楚的想法,貌似有点复杂的样子,但是可以想见应该存在着某个算法可以得到一个比较合理的排序。求CS大牛指导。

一旦有了这个数据,那以后做调查问卷的时候就可以通过让被试填一下人人id就可以获取漂亮程度的数据了。

其实这个想法以前也有人提出来过啊,著名电影《社交网络》里面马克·扎克伯格不就搞了这么个系统嘛。不过在facebook和人人上都没有真正看到这个应用。

可以想见,如果这个应用真的写出来了的话,作者一定会被广大女生骂死。。。而且我没技术我是肯定不会去写的。。。不知道有没有懂技术又想实现这个算法的人,如果有的话尽管写吧!只要最后有了数据之后给我一份就行。。。

Read more from Ideas
29 Comments Post a comment
  1. May 9 2012

    你说的那个图,叫directed graph, 你所说的处理排序可以通过topological sort来实现。但是这样的一个graph来toposort有一个问题就是, 假如你现有数据有一个arc是A->B,就是有人认为A比B美,但也有条B->A的arc,这样整个graph就形成了一个cycle,就无法做toposort了。但是呢,就像你所说的,edge可以是weight的,所以假如有100个人认为A美于B,那么A->B的weight就是100, 27个人认为B美于A,B->A的weight就是27,或者A->B:-27,这样total A->B的weight就是100-27=73.这样以上问题就解决了。
    还有一个问题,就是你这个graph里很有可能有很多vertice,也就是很多人没有被指向的arc,也就是说这些人是绝对美的,他们只有outgoing edge没有incoming edge,那么这些人之间的美丑比较你就无法做到了。总结下,你的想法第一很好,第二算法实现上不难,而且toposort所需的时间复杂度是linear, O(n), 再详细点n是edge数加上vertice数,不慢。同学你加油吧,至于开发校内app本人就不了解了。

    Reply
    • May 9 2012

      做拓扑的必要条件是所处理的图是有向无环图,你上面那么处理根本无法保证整个图是无环的吧....

      Reply
      • May 9 2012

        我第一段就解决了cycle的问题啊。但是貌似确实会有A->B->C->A的情况,这就要看怎么设计了。解决的这个,其他就很好办了啊。

      • May 9 2012

        但其实仔细想想,也可以用weight相加减来解决cycle啊。

      • May 9 2012

        那要是A->B->C->A这种情况呢?

      • May 9 2012

        好像是个问题,你怎么想呢?

      • May 9 2012

        reverse一个cycle中的某一个edge,然后重新计算他的weight,比如拿这个cycle中的其他edge的weight总和然后减去这个edge的weight。可行不?

      • 隐忧
        May 9 2012

        感觉page rank就可以了...

      • Hearfish
        May 14 2012

        PR做不了吧……

      • 隐忧
        May 14 2012

        改造一下,逆向pr,以有向边的权重,和终点的值向始点传递。

      • any
        May 10 2012

        假设1、2、3三个人评价A、B、C三个人的漂亮程度
        1认为 A>B>C
        2认为 B>C>A
        3认为 C>A>B

        三个人中有两个人认为A比B漂亮
        同时三个人中也有两个人认为B比C漂亮
        同时三个人中也有两个人认为C比A漂亮
        那到底谁最漂亮?
        这个其实就是阿罗不可能定理的一个例子

        以下摘自wikipedia
        有 N 种选择,有 m 个决策者,他们每个人都对这 N 个选择有一个从优至劣的排序。我们要设计一种选举法则,使得将这 m 个排序的信息汇总成一个新的排序,称为投票结果。我们希望这种法则满足以下条件:

        一致性,或称为帕累托效率。即如果所有的 m 个决策者都认为选择 a 优于 b,那么在投票结果中,a 也优于 b。
        非独裁。不存在一个决策者 X,使得投票结果总是等同于 X 的排序。
        独立于无关选项。如果现在一些决策者改了主意,但是在每个决策者的排序中,a 和 b 的相对位置不变,那么在投票结果中 a 和 b 的相对位置也不变。
        那么,如果 N 大于 3,我们不可能设计出这种制度。

    • INNOCENT
      May 9 2012

      建议去搞半年ACM再来发表和图有关看法.

      Reply
  2. INNOCENT
    May 9 2012

    观察节点A, 令其入度集为In[A]. 我们要得到的是一个漂亮程度函数P[A]. 为了简化问题, 我们不妨认为P[A]由且仅由P[for all elements in In[A]]决定. 比如B有边指向A, 那么认为P[B]参与P[A]的计算, 而且直观地发现, P[B]越大, 其对P[A]的负面影响越小(说明B很漂亮嘛, 被B比下去没啥稀奇的); P[A]越大, P[B]对P[A]的负面影响越大(很漂亮的人居然被比下去了). 另外, P[B]可能又受到别的点的影响(甚至被A影响, 即环), 一个常用的手段是迭代至收敛. 我们希望对整个图做适当顺序的迭代, 使得最后P集趋于稳定. 好像和搜索引擎评分有点像= =
    另外一个值得考虑的问题是从众心理. 当人们意识到一个人公认漂亮后, 大多会失去对此人的判断力.
    再另外, 阮一峰的日志貌似有讲到一点排名算法, 但是我也没有细看.
    希望能给你点帮助:)

    Reply
    • May 9 2012

      入度集
      是什么意思?
      In[A]
      为何ln?是log base e的那个ln么?
      P[B]越大, 其对P[A]的负面影响越小(说明B很漂亮嘛, 被B比下去没啥稀奇的)
      这个想法很赞同
      一个常用的手段是迭代至收敛
      这个能具体讲下么?针对什么的手段?迭代是iteration吧?

      Reply
      • INNOCENT
        May 9 2012

        上面已经有人说了, 这个用page rank就可以了. 入度就是"in-degree", 事实上我这说的"A入度集"是"{对于所有点X若存在边(X, A)}". 你需要区别下'l'和'I'. 迭代(iteration)的话, 自然是针对环(cycle)的了, 否则拓扑排序(topological sort)就可以搞定. 一个简单而有效的例子是用"基于队列优化的Bellman-Ford算法"(其实我们都叫SPFA, "基于啥啥啥"只有论文才这么叫)来解单源最短路径问题(SSSP, 别和我提Dijkstra). 就本题来说, 是用P[B]更新完P[A]之后, P[B]还会再变, 届时再用P[B]更新一次P[A], 反复更新直到收敛. 所以我们要找到一个合适的更新函数使得P收敛, 而不是发散. 话说我不是很习惯在中文讨论中夹很多英文term, 特别是对于一个成熟的, 拥有相应中文term的知识体系而言, 抱歉= =

      • May 9 2012

        Bellman-Ford!当时看你上条的时候就在想这个,就是没回忆起名字来。我学的全是英文的。 谢了。

  3. any
    May 9 2012

    个人认为这个问题很有可能遇到阿罗悖论

    Reply
  4. 水成文
    May 9 2012

    elo等级分制度 http://zh.wikipedia.org/wiki/%E7%AD%89%E7%BA%A7%E5%88%86
    《社交网络》里用的好像就是这个

    Reply
  5. May 9 2012

    //本文为EagleFantasy原创。如果转载请不要注明出处,就说是你写的。

    …………………………………………………………

    Reply
  6. Alan
    May 12 2012

    我也是对这句很感兴趣://本文为EagleFantasy原创。如果转载请不要注明出处,就说是你写的。

    Reply
  7. LenenTom
    May 12 2012

    //本文为EagleFantasy原创。如果转载请不要注明出处,就说是你写的。

    意思是不是文章的作者另有其人?!

    Reply
    • Mat
      May 14 2012

      作者怕自己被别人拍

      Reply
  8. SillySnail
    May 15 2012

    考虑图必然会导致难以处理的环,所以不用搞那么复杂,用pairwise ranking算法搞一搞就行了,简单的说就是用一个评价函数引导搜索,这个评价函数计算某个序与多少个已标注的pair的吻合

    Reply
  9. May 21 2012

    我正想说《社交网络》里面就这个模型。。。

    Reply
  10. Jun 3 2012

    出现环的时候视为漂亮程度相当,并用强连通分量算法缩环,然后topsort

    Reply
  11. Sep 1 2012

    可以使用pagerank。另外还有比较小众的fair bet value,出发点不一样,但从计算上看是pr除以出度,在这个case里面有其意义。在sns中,人的popularity不一样,如果大家都是严格随机从好友中选两个,有的人被选的次数多,自然入度就大,在PR的传递模型中是占优的。出度刚好表征了一个人的popular的程度,

    Reply
  12. Sep 1 2012

    用出度来做一个post-processing也可以认为是一个归一。用博客的友情链接来举个例子。通过交换链接,传递权值,两个人可能PR一样。但是其中一个人可能是通过向外发出了很多链接,以吸引到足够的回链;另一个人可能是很少向外发,但是自己质量很高,所有大家都指过去。用fair bet的话,就能够区分。ref:H. Daniels. Round-robin tournament scores.Biometrika, 56(2):295–299, 1969.

    Reply

Share your thoughts, post a comment.

(required)
(required)

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments