获取人群漂亮程度数据的一个方法
这个想法最初的动机是这样的:我想做一些社会学的调查,研究一下一些统计规律。而在我想做的社会调查里面,涉及到一个很难处理的自变量:被调查对象的漂亮程度,也就是大家通常说的7分女啊1分男啊之类的对人的相貌的评分。如果有了人群的漂亮程度的数据,我就可以把它作为自变量定量地研究很多问题,诸如:漂亮程度和幸福感的相关性;漂亮程度和智商的相关性;漂亮程度和收入的相关性;配偶双方的漂亮程度的差别有多大……如果得到的结果是相关性很强的,那就算是一个对人类现况的客观认识吧,如果相关性很弱,那就可以给广大不是很漂亮的人们一个很好的心理安慰了。
但现在主要问题就是漂亮程度这个量很难获取。总不能是发问卷的人给被调查的人直接打分吧,这肯定不科学。于是我想到了一个也许可行的办法:利用社交网络人人网,做一个应用,从这个应用当中获取需要的信息。
这个应用的设计如下:
进入应用之后,你可以看到随机抽出来的两位你的好友(这二人必须性别一致)(也可以不随机而是由确定的算法抽出两个好友),然后你需要做的事情就是选择这两个人谁更漂亮。因为人人网是个真实的社交网络,这个选择可以是基于你对他们的整体印象,而不只是头像照片。每次选择完毕,你都可以获得1个积分。积分多了可以做如下几件事情:10分可以看自己的漂亮程度打分;20分可以查看自己的好友里面谁最漂亮;30分可以查看某个特定好友的漂亮程度打分;诸如此类。设置这些功能只是为了保证大家有打分的热情,由人类的虚荣心和窥探欲所驱动,以前有成功的例子,如那个蛋疼的应用“好友真相”。
通过这个应用,我们可以获得一个很大很复杂的有向图:每个节点代表一个人,两个节点之间的带方向的边就代表谁比谁更漂亮,边是带着权重的,权重就表示有多少人认为A比B更漂亮。对这张图进行处理就可以得到一个排序,通过这个排序最终就可以得到每个人的漂亮程度打分,比如排名前10%的算作10分,排名10%~20%的人算作9分,当然这个比例也可以按照正态分布来调整,总之有了排序就一定可以得到一个打分。因为我不是CS专业的,所以对这张图到底该怎么处理还没有特别清楚的想法,貌似有点复杂的样子,但是可以想见应该存在着某个算法可以得到一个比较合理的排序。求CS大牛指导。
一旦有了这个数据,那以后做调查问卷的时候就可以通过让被试填一下人人id就可以获取漂亮程度的数据了。
其实这个想法以前也有人提出来过啊,著名电影《社交网络》里面马克·扎克伯格不就搞了这么个系统嘛。不过在facebook和人人上都没有真正看到这个应用。
可以想见,如果这个应用真的写出来了的话,作者一定会被广大女生骂死。。。而且我没技术我是肯定不会去写的。。。不知道有没有懂技术又想实现这个算法的人,如果有的话尽管写吧!只要最后有了数据之后给我一份就行。。。
你说的那个图,叫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本人就不了解了。
做拓扑的必要条件是所处理的图是有向无环图,你上面那么处理根本无法保证整个图是无环的吧….
我第一段就解决了cycle的问题啊。但是貌似确实会有A->B->C->A的情况,这就要看怎么设计了。解决的这个,其他就很好办了啊。
但其实仔细想想,也可以用weight相加减来解决cycle啊。
那要是A->B->C->A这种情况呢?
好像是个问题,你怎么想呢?
reverse一个cycle中的某一个edge,然后重新计算他的weight,比如拿这个cycle中的其他edge的weight总和然后减去这个edge的weight。可行不?
感觉page rank就可以了…
PR做不了吧……
改造一下,逆向pr,以有向边的权重,和终点的值向始点传递。
假设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,我们不可能设计出这种制度。
建议去搞半年ACM再来发表和图有关看法.
有个直接一点的办法。汽车之家有个叫”媳妇当车模“的专题,http://club.autohome.com.cn/jingxuan/1/1,估计漂亮程度和车的价格有关系。我之前想搞个投票,人车分离,请网友判断一下漂亮程度,验证一下与车的价格是否是正相关。后来没做了。
虽然直接但结果不一定科学准确啊。
观察节点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集趋于稳定. 好像和搜索引擎评分有点像= =
另外一个值得考虑的问题是从众心理. 当人们意识到一个人公认漂亮后, 大多会失去对此人的判断力.
再另外, 阮一峰的日志貌似有讲到一点排名算法, 但是我也没有细看.
希望能给你点帮助:)
入度集
是什么意思?
In[A]
为何ln?是log base e的那个ln么?
P[B]越大, 其对P[A]的负面影响越小(说明B很漂亮嘛, 被B比下去没啥稀奇的)
这个想法很赞同
一个常用的手段是迭代至收敛
这个能具体讲下么?针对什么的手段?迭代是iteration吧?
上面已经有人说了, 这个用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的知识体系而言, 抱歉= =
Bellman-Ford!当时看你上条的时候就在想这个,就是没回忆起名字来。我学的全是英文的。 谢了。
个人认为这个问题很有可能遇到阿罗悖论
elo等级分制度 http://zh.wikipedia.org/wiki/%E7%AD%89%E7%BA%A7%E5%88%86
《社交网络》里用的好像就是这个
//本文为EagleFantasy原创。如果转载请不要注明出处,就说是你写的。
…………………………………………………………
我也是对这句很感兴趣://本文为EagleFantasy原创。如果转载请不要注明出处,就说是你写的。
//本文为EagleFantasy原创。如果转载请不要注明出处,就说是你写的。
意思是不是文章的作者另有其人?!
作者怕自己被别人拍
考虑图必然会导致难以处理的环,所以不用搞那么复杂,用pairwise ranking算法搞一搞就行了,简单的说就是用一个评价函数引导搜索,这个评价函数计算某个序与多少个已标注的pair的吻合
我正想说《社交网络》里面就这个模型。。。
出现环的时候视为漂亮程度相当,并用强连通分量算法缩环,然后topsort
可以使用pagerank。另外还有比较小众的fair bet value,出发点不一样,但从计算上看是pr除以出度,在这个case里面有其意义。在sns中,人的popularity不一样,如果大家都是严格随机从好友中选两个,有的人被选的次数多,自然入度就大,在PR的传递模型中是占优的。出度刚好表征了一个人的popular的程度,
用出度来做一个post-processing也可以认为是一个归一。用博客的友情链接来举个例子。通过交换链接,传递权值,两个人可能PR一样。但是其中一个人可能是通过向外发出了很多链接,以吸引到足够的回链;另一个人可能是很少向外发,但是自己质量很高,所有大家都指过去。用fair bet的话,就能够区分。ref:H. Daniels. Round-robin tournament scores.Biometrika, 56(2):295–299, 1969.