追爱的数学模型课件.ppt

1、数学建模素养数学建模素养意识篇之意识篇之追爱的数学模型追爱的数学模型主讲教师主讲教师 高全胜教授高全胜教授1.1.数模女汉子选择追求者问题数模女汉子选择追求者问题 虽然是数模女汉子，但对找到自己心中的白马王子，渴望和普虽然是数模女汉子，但对找到自己心中的白马王子，渴望和普通女生一样的浪漫，找到自己一生的幸福是每个人的追求。通女生一样的浪漫，找到自己一生的幸福是每个人的追求。但是面对追求者们，女生应该是选择还是拒绝，她的策略是社但是面对追求者们，女生应该是选择还是拒绝，她的策略是社么？么？怎样才能以最大的可能找到自己的怎样才能以最大的可能找到自己的“理想的他理想的他” 呢？呢？1.1.1.1.问

2、题简化问题简化v 假设一个女生想在一段时间中和一位男生开始一段感情，假设一个女生想在一段时间中和一位男生开始一段感情，并且在这段时间中有并且在这段时间中有N 个男生追求这位女生。个男生追求这位女生。v 这这N 个男生是以不同的先后顺序来追求这位女生。个男生是以不同的先后顺序来追求这位女生。v 在适合这个女生的意义上，假设追求者中任何两个男生都在适合这个女生的意义上，假设追求者中任何两个男生都是可以比较的，而且没有相等的情况。是可以比较的，而且没有相等的情况。v 这样我们对这这样我们对这N 个男生从个男生从1 到到N 进行编号，其中数字越进行编号，其中数字越大表示越适合这个女生。这样在这段时间中

3、，女生的大表示越适合这个女生。这样在这段时间中，女生的Mr. Right 就是男生就是男生N 了。了。v 现在问题变成现在问题变成面对这面对这N 个追求者，应该以怎样的策略才个追求者，应该以怎样的策略才能使得在第一次选择接受的男生就是能使得在第一次选择接受的男生就是N 的可能性最大。的可能性最大。1.2.1.2.模型假设模型假设 v 1、N 个男生以不同的先后顺序向女生表白，即在任一时个男生以不同的先后顺序向女生表白，即在任一时刻不存在两个或两个以上的男生向这位女生表白的情况的刻不存在两个或两个以上的男生向这位女生表白的情况的发生，而且任何一种顺序都是完全等概率的。发生，而且任何一种顺序都是完

4、全等概率的。v 2、面对表白后的男生，女生只能做出接受和拒绝两种选、面对表白后的男生，女生只能做出接受和拒绝两种选择，不存在暧昧或者其它选择。择，不存在暧昧或者其它选择。v 3、任一时刻，女生最多只能和一位男生谈恋爱，不存在、任一时刻，女生最多只能和一位男生谈恋爱，不存在脚踏多船的情况。脚踏多船的情况。v 4、已经被拒绝的男生不会再次追求这位女生。、已经被拒绝的男生不会再次追求这位女生。 1.3.1.3.问题分析问题分析v 简单策略：如果一旦有男生向女生表白，女生就选择接受。这种策略简单策略：如果一旦有男生向女生表白，女生就选择接受。这种策略下显然女生以下显然女生以1/N 的概率找到自己的的概

5、率找到自己的Mr. Right 。当。当N 比较大的比较大的时候，这个概率就很小了，显然这种策略不是最优的。时候，这个概率就很小了，显然这种策略不是最优的。 v 复杂策略：对于最先表白的复杂策略：对于最先表白的M 个人，无论女生感觉如何都选择拒绝个人，无论女生感觉如何都选择拒绝；以后遇到男生向女生表白的情况，只要这个男生的编号比前面；以后遇到男生向女生表白的情况，只要这个男生的编号比前面M 个男生的编号都大，即这个男生比前面个男生的编号都大，即这个男生比前面M 个男生更适合女生，那么个男生更适合女生，那么女生选择接受，否则选择拒绝。女生选择接受，否则选择拒绝。 以以N=3 N=3 为例为例 v

6、三个男生追求女生，共有六种排列方式：三个男生追求女生，共有六种排列方式：1 2 3；1 3 2；2 1 3；2 3 1；3 1 2；3 2 1。如果女生采用上述最简单的策略，那么只有最后两种排列方式选择到。如果女生采用上述最简单的策略，那么只有最后两种排列方式选择到Mr. Right ，概率为，概率为2/3!=1/3 。v如果女生采用上面我们提出的策略，这里我们取如果女生采用上面我们提出的策略，这里我们取M=1 ，即无论第一个人是否优秀，即无论第一个人是否优秀，女生都选择拒绝。然后对于之后的追求者，只要他比第一个男生更适合女生就选择接女生都选择拒绝。然后对于之后的追求者，只要他比第一个男生更适

7、合女生就选择接受，否则拒绝。受，否则拒绝。 基于这种策略，基于这种策略，“1 3 2 ”、“2 1 3 ”、“ 2 3 1 ”这三种排列顺这三种排列顺序下女生都会在第一次做出接受的选择时遇到序下女生都会在第一次做出接受的选择时遇到“3 ”，这样我们就把这种概率增大到，这样我们就把这种概率增大到3/3!=1/2 。v 现在我们的问题就归结为，现在我们的问题就归结为，对于一般的对于一般的N ，什么样的，什么样的M 才会使这种概率达到最大值呢才会使这种概率达到最大值呢？（在这种模型中，前面？（在这种模型中，前面M 个男生就被称为个男生就被称为“炮灰垫背炮灰垫背”，无论他们有多么优秀都要，无论他们有多

8、么优秀都要被拒绝）被拒绝） 1.4.1.4.模型建立模型建立v 在这一部分中，根据上面的模型假设，我们先找到对于给定的在这一部分中，根据上面的模型假设，我们先找到对于给定的M 和和N(1MN) ，女生选择到，女生选择到Mr. Right 的概率的表达式。的概率的表达式。v 1 到到N 个数字进行排列共有个数字进行排列共有N! 种种 可能。当数字可能。当数字N 出现在第出现在第P 位置（位置（MP0, In(1+x)0时时, In(1+x) x 。v所以由左不等式所以由左不等式v v所以：所以： v 当当N 比较大时，同理由右不等式可得比较大时，同理由右不等式可得M N/e ， 以上以上e 为自

9、然对为自然对数。若记数。若记x 为不大于为不大于x 的最大整数，由以上推导我们可猜测当的最大整数，由以上推导我们可猜测当M 取取N/e 或或N/e+1 时，该表达式取得最大值。时，该表达式取得最大值。1.6.1.6.结果分析结果分析 v 由上述分析可以得到如下结论：为了使一个女生以最大的概率在第一次选择由上述分析可以得到如下结论：为了使一个女生以最大的概率在第一次选择接受男生时遇到的正是接受男生时遇到的正是Mr. Right ，女生应该采用以下的策略：，女生应该采用以下的策略：v 拒绝前M=N/e 或者N/e+1 个追求者，当其后的追求者比前M 个追求者更适合则接受，否则拒绝。 v 假设你一共

10、会遇到大概假设你一共会遇到大概 30 个，就应该拒绝掉前个，就应该拒绝掉前 30/e 30/2.718 11 个求爱者，然后从第个求爱者，然后从第 12 个求爱者开始，一旦个求爱者开始，一旦发现比前面发现比前面 11 个求爱者都好的人，就果断接受他。由于个求爱者都好的人，就果断接受他。由于 1/e 大约等于大约等于 37%，因此这条爱情大法也叫做，因此这条爱情大法也叫做 37% 法则。法则。v 不过，不过，37% 法则有一个小问题：如果最佳人选本来就在这法则有一个小问题：如果最佳人选本来就在这 37% 的人里面的人里面，错过这，错过这 37% 的人之后，她就再也碰不上更好的了。的人之后，她就再

11、也碰不上更好的了。v 但在游戏过程中，她并不知道最佳人选已经被拒，因此她会一直痴痴地等待但在游戏过程中，她并不知道最佳人选已经被拒，因此她会一直痴痴地等待。也就是说，。也就是说，MM将会有将会有 37% 的概率的概率“失败退场失败退场”，或者以被迫选择最后，或者以被迫选择最后一名求爱者的结局而告终一名求爱者的结局而告终 37%37% 法则法则“实测实测”！v37% 法则的效果究竟如何呢？我们在计算机上编写程序模拟了当法则的效果究竟如何呢？我们在计算机上编写程序模拟了当 n = 30 时利用时利用 37% 法则法则进行选择的过程（如果进行选择的过程（如果 MM 始终未接受求爱者，则自动选择最后一

12、名求爱者）。编号越小的男生始终未接受求爱者，则自动选择最后一名求爱者）。编号越小的男生越次，编号为越次，编号为 30 的男生则表示最佳选择。程序运行的男生则表示最佳选择。程序运行 10000 次之后，竟然有大约次之后，竟然有大约 4000 次选次选中最佳男生，可见中最佳男生，可见 37% 法则确实有效啊。法则确实有效啊。v不知道了解此问题的女生，会不会多了一种分手的理由：不好意思，你是那不知道了解此问题的女生，会不会多了一种分手的理由：不好意思，你是那 37% 的人的人 对于对于男生，该模型残酷的，指出了炮灰存在的现实意义，正如伟大哲学家萨特所说男生，该模型残酷的，指出了炮灰存在的现实意义，正

13、如伟大哲学家萨特所说“存在即是合理存在即是合理”，炮灰的不可避免性也许是对已经和即将成为炮灰的男生的宽慰。，炮灰的不可避免性也许是对已经和即将成为炮灰的男生的宽慰。But,However，Whats more(*_*) ，v该模型的量化指标都是采自女生主观臆断，各个指标的合理性希望广大该模型的量化指标都是采自女生主观臆断，各个指标的合理性希望广大MM慎思之。慎思之。题外话题外话v “打仗的时候，很多士兵身先士卒，跑到前线勇往直前。通常来说，走在最打仗的时候，很多士兵身先士卒，跑到前线勇往直前。通常来说，走在最前面的，都会给大炮打中（古代的大炮像象个球一样滚过来的）成为灰烬。前面的，都会给大炮打

14、中（古代的大炮像象个球一样滚过来的）成为灰烬。而后来的士兵，就踏着炮灰走到胜利，所以成为别人利益的牺牲品的人就叫而后来的士兵，就踏着炮灰走到胜利，所以成为别人利益的牺牲品的人就叫炮灰炮灰.。”- 百度上关于炮灰的解释百度上关于炮灰的解释v 在本篇文章中介绍的在本篇文章中介绍的“炮灰模型炮灰模型”中，前中，前M个男生就成了炮灰的角色，无论个男生就成了炮灰的角色，无论其有多么优秀，都会被拒绝。其有多么优秀，都会被拒绝。v v 朋友，如果你追求一个女生而遭到拒绝，看完这篇文章后你会突然发现，也朋友，如果你追求一个女生而遭到拒绝，看完这篇文章后你会突然发现，也许这不是你的的错，也许你真的很优秀，只是很

15、不幸，你成了许这不是你的的错，也许你真的很优秀，只是很不幸，你成了“炮灰炮灰”。v v 希望上面这些看似复杂的推导和模型对你能有所启发。不要因为一次的拒绝希望上面这些看似复杂的推导和模型对你能有所启发。不要因为一次的拒绝而伤心、失落，振作起来，你的而伤心、失落，振作起来，你的Miss Right is waiting for you somewhere!进一步的解释进一步的解释v再由前面的理论小推论一下：再由前面的理论小推论一下： 设女性最为灿烂的设女性最为灿烂的青春为青春为18-28岁，在这段时间中将会遇到一生中岁，在这段时间中将会遇到一生中几乎全部的追求者（之前之后的忽略不计），且几乎全部

16、的追求者（之前之后的忽略不计），且追求者均匀分布追求者均匀分布(每年一个），则女性从每年一个），则女性从18+10/e=21.7即即22岁左右开始接受追求岁左右开始接受追求v这告诉我们，想谈恋爱找大四的（不现实，但可这告诉我们，想谈恋爱找大四的（不现实，但可能会符合婚姻法）能会符合婚姻法） 1.7.1.7.模型的扩展模型的扩展v微软钻石面试题：一楼到十楼的每层电梯门口都放着一颗钻石，钻石微软钻石面试题：一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到

17、最大的一颗？只能拿一次钻石，问怎样才能拿到最大的一颗？ v我们可以把每个钻石看做是前来表白的男生，我们可以把每个钻石看做是前来表白的男生，MM坐电梯上楼对其进行选择，这样该问题就可坐电梯上楼对其进行选择，这样该问题就可以化为以化为MM选择最佳追求者的问题了。即有选择最佳追求者的问题了。即有10个个追求者，要求追求者，要求MM拒掉的男生的人数拒掉的男生的人数M为多少时为多少时，才可以以最大概率找到，才可以以最大概率找到Mr. Right？ 1.7.1 1.7.1 微软钻石面试题微软钻石面试题仿真结果仿真结果v 将将N=10代入前面的结论的表达式，由于是离散化的且代入前面的结论的表达式，由于是离散

18、化的且N不是很大，我们可不是很大，我们可以用遍历搜素进行求值，当然本问题用手工计算或计算器计算下就好了。经以用遍历搜素进行求值，当然本问题用手工计算或计算器计算下就好了。经过计算可知过计算可知M=3。v 那么对于较大的那么对于较大的N，我们给出，我们给出MATLAB的结果：仿真后可得随着的结果：仿真后可得随着N的增长，的增长，按此方案选择最优值在按此方案选择最优值在1/e附近。附近。v 结论：因此对于微软钻石选择问题的策略是：前3层都不拿钻石，并记录下最大的钻石的大小，然后从第四层开始，只要遇到比前三层都大的钻石就拿。1.7.2 1.7.2 非诚勿扰问题非诚勿扰问题v 在每期在每期非诚勿扰非诚

19、勿扰节目上，面对一位位男嘉宾，节目上，面对一位位男嘉宾，24 位单身女生要位单身女生要做出不止一次做出不止一次“艰难的决定艰难的决定”：到底要不要继续亮灯？把灯灭掉意味：到底要不要继续亮灯？把灯灭掉意味着放弃了这一次机会，继续亮灯则有可能结束节目之旅，放弃了未来着放弃了这一次机会，继续亮灯则有可能结束节目之旅，放弃了未来更多的选择。更多的选择。v 怎么办？去向怎么办？去向非诚勿扰非诚勿扰的黄菡老师和乐嘉老师请教一下？其实你的黄菡老师和乐嘉老师请教一下？其实你还可以向欧拉老师请教一下。你没听错。大数学家欧拉对一个神秘的还可以向欧拉老师请教一下。你没听错。大数学家欧拉对一个神秘的数学常数数学常数

20、e 2.718 深有研究，这个数字和深有研究，这个数字和“拒人问题拒人问题”竟然有着竟然有着直接的联系。直接的联系。v 为了便于我们分析，让我们把生活中各种复杂纠纷的恋爱故事抽象成为了便于我们分析，让我们把生活中各种复杂纠纷的恋爱故事抽象成一个简单的数学过程。假设根据过去的经验，一个简单的数学过程。假设根据过去的经验，MM 可以确定出今后可以确定出今后将会遇到的男生个数，比如说将会遇到的男生个数，比如说 15 个、个、30 个或者个或者 50 个。不妨把男个。不妨把男生的总人数设为生的总人数设为 n。这。这 n 个男生将会以一个随机的顺序排着队依次个男生将会以一个随机的顺序排着队依次前来表白。

21、每次被表白后，前来表白。每次被表白后，MM 都只有两种选择：接受这个男生，都只有两种选择：接受这个男生，结束这场结束这场“征婚游戏征婚游戏”，和他永远幸福地生活在一起；或者拒绝这个，和他永远幸福地生活在一起；或者拒绝这个男生，继续考虑下一个表白者。我们不考虑男生，继续考虑下一个表白者。我们不考虑 MM 脚踏两只船的情况脚踏两只船的情况，也不考虑和被拒男生破镜重圆的可能。最后，男人有好有坏，我们，也不考虑和被拒男生破镜重圆的可能。最后，男人有好有坏，我们不妨假设不妨假设 MM 心里会给男生们的优劣排出个名次来。心里会给男生们的优劣排出个名次来。v 聪明的聪明的 MM 会想到一个好办法：先和前面几

22、个男生玩玩会想到一个好办法：先和前面几个男生玩玩，试试水深；大致摸清了男生们的底细后，再开始认真考，试试水深；大致摸清了男生们的底细后，再开始认真考虑，和第一个比之前所有人都要好的男生发展关系。虑，和第一个比之前所有人都要好的男生发展关系。v 从数学模型上说，就是先拒掉前面从数学模型上说，就是先拒掉前面 k 个人，不管这些人个人，不管这些人有多好；然后从第有多好；然后从第 k+1 个人开始，一旦看到比之前所有个人开始，一旦看到比之前所有人都要好的人，就毫不犹豫地选择他。不难看出，人都要好的人，就毫不犹豫地选择他。不难看出，k 的取的取值很讲究，太小了达不到试的效果，太大了又会导致真正值很讲究，

23、太小了达不到试的效果，太大了又会导致真正可选的余地不多了。这就变成了一个纯数学问题：在男生可选的余地不多了。这就变成了一个纯数学问题：在男生总数总数 n 已知的情况下，当已知的情况下，当 k 等于何值时，按上述策略选等于何值时，按上述策略选中最佳男生的概率最大？中最佳男生的概率最大？v 如果你预计求爱者有如果你预计求爱者有 n 个人，你应该先拒绝掉前个人，你应该先拒绝掉前 n/e 个个人，静候下一个比这些人都好的人。人，静候下一个比这些人都好的人。2.2.数学博士的交友战略数学博士的交友战略v 克里斯克里斯麦金利（麦金利（Chris McKinlay） 最近两件事：最近两件事：v （1）忙博士

24、论文忙博士论文大规模数大规模数据处理和并行数值方法据处理和并行数值方法；v （2）自从九个月前跟前女友）自从九个月前跟前女友分手之后，他就一直都在寻分手之后，他就一直都在寻找新恋情，但迄今为止都是找新恋情，但迄今为止都是徒劳无果。徒劳无果。v 世纪佳缘，人人网世纪佳缘，人人网 2.1.2.1.婚恋网站婚恋网站 v OkCupid是哈佛大学数学专业的学生在是哈佛大学数学专业的学生在2004年年创建的，它最初吸引用户的地方是可以使用算法来创建的，它最初吸引用户的地方是可以使用算法来匹配会员。匹配会员。v 流程：流程：会员需要做大量的多项选择题会员需要做大量的多项选择题，这些问题涵，这些问题涵盖了包

25、括政治、宗教、家庭、爱、性、智能手机在盖了包括政治、宗教、家庭、爱、性、智能手机在内的方方面面。比如：内的方方面面。比如：“以下哪项最有可能吸引你以下哪项最有可能吸引你去看一部电影？去看一部电影？” （爱情片、战争片、间谍片。（爱情片、战争片、间谍片。）。）“宗教或神对你的宗教或神对你的生命生命有多重要？有多重要？”（宗教冲（宗教冲突）突）v 问题总共有数千个之多。平均而言，一个用户会挑问题总共有数千个之多。平均而言，一个用户会挑选其中选其中350个问题来回答，并用打分的方式说明这个问题来回答，并用打分的方式说明这个问题对自己有多么重要：个问题对自己有多么重要：0代表代表“不重要不重要”，5代

26、表代表“必不可少必不可少”。 v 然后然后OkCupid的匹配引擎就会使用这些数据来的匹配引擎就会使用这些数据来计计算两个人的匹配度算两个人的匹配度。百分比越接近。百分比越接近100%就越匹就越匹配。配。100%表示你们是灵魂伴侣。表示你们是灵魂伴侣。 婚恋网站的问题婚恋网站的问题v 问题：问题：OkCupid号称可以用算法找到跟你匹配的约会对象，麦金利已经向号称可以用算法找到跟你匹配的约会对象，麦金利已经向数十位匹配度不低的女性发送了私信，但大多石沉大海。只有数十位匹配度不低的女性发送了私信，但大多石沉大海。只有6个人跟他见个人跟他见过面。过面。v 原因（原因（眉毛胡子一把抓眉毛胡子一把抓）

27、：麦金利跟洛杉矶女性的匹配度简直糟糕透顶。因麦金利跟洛杉矶女性的匹配度简直糟糕透顶。因为为OkCupid算法所使用的问卷问题，仅仅是双方都选择回答了的问题，而算法所使用的问卷问题，仅仅是双方都选择回答了的问题，而麦金利在选择回答哪些问题时比较随性。事实证明，他选择回答的这些问题麦金利在选择回答哪些问题时比较随性。事实证明，他选择回答的这些问题很多人都不会选。很多人都不会选。v 洛杉矶大约拥有洛杉矶大约拥有200万女性，其中约有万女性，其中约有8万人使用万人使用OkCupid交友服务。但是交友服务。但是查看一下麦金利的匹配列表，只有不到查看一下麦金利的匹配列表，只有不到100名女性跟他的匹配度达

28、到名女性跟他的匹配度达到90 %以上。在交友网站上，匹配度就相当于可见度，麦金利的可见度如此之低，以上。在交友网站上，匹配度就相当于可见度，麦金利的可见度如此之低，跟鬼魂也差不多少。跟鬼魂也差不多少。v 办法：办法：麦金利意识到，他觉得自己应该像一个真正的数学专家那样去寻找约麦金利意识到，他觉得自己应该像一个真正的数学专家那样去寻找约会对象。他必须增加跟他匹配度在会对象。他必须增加跟他匹配度在90 %以上的女性人数。（数学感觉，恋以上的女性人数。（数学感觉，恋爱不行，数学行）爱不行，数学行）v 如果可以用统计抽样来确定哪些问题对他喜欢的那类女性来说很重要，他就如果可以用统计抽样来确定哪些问题对

29、他喜欢的那类女性来说很重要，他就可以修改自己的个人账户资料，老老实实地回答这些问题，不再去操心其他可以修改自己的个人账户资料，老老实实地回答这些问题，不再去操心其他问题了。这样一来，可能适合他的每个同城女性都会出现在匹配列表里，而问题了。这样一来，可能适合他的每个同城女性都会出现在匹配列表里，而不适合他的女性一个都不会出现。不适合他的女性一个都不会出现。 用假账户搜集数据用假账户搜集数据v 首先，麦金利需要数据。他首先，麦金利需要数据。他设置了设置了12个个OkCupid假账户假账户，并编写了一个，并编写了一个Python脚本来管理它们。这个脚本会搜索麦金利的目标人群（脚本来管理它们。这个脚本

30、会搜索麦金利的目标人群（25至至45岁岁之间的异性恋和双性恋女性），访问她们的网页，并在她们的个人资料里搜之间的异性恋和双性恋女性），访问她们的网页，并在她们的个人资料里搜集所有可用信息：种族、身高、是否吸烟、星座，所有一切。集所有可用信息：种族、身高、是否吸烟、星座，所有一切。v 为了获取问卷数据，他必须做更多的侦查活动。在为了获取问卷数据，他必须做更多的侦查活动。在OkCupid上，只有当你上，只有当你自己回答过某个问题时，你才可以看到别人对这个问题的回答。于是麦金利自己回答过某个问题时，你才可以看到别人对这个问题的回答。于是麦金利编写了编写了bot机器人来随机回答每一个问题机器人来随机回

31、答每一个问题（假账户的目的不是用来吸引约会（假账户的目的不是用来吸引约会对象，所以它们是怎么回答问题的并不重要），然后把目标人群的回答搜集对象，所以它们是怎么回答问题的并不重要），然后把目标人群的回答搜集到自己数据库中。到自己数据库中。v 麦金利满意地看着机器人忙忙碌碌。但是，在搜集了约麦金利满意地看着机器人忙忙碌碌。但是，在搜集了约1000份个人资料之份个人资料之后，他遇到了第一个障碍。后，他遇到了第一个障碍。 OkCupid采用了一个系统来防止这种数据收集采用了一个系统来防止这种数据收集活动：它可以轻而易举地发现这种连续、快速的活动。麦金利的机器人一个活动：它可以轻而易举地发现这种连续、快

32、速的活动。麦金利的机器人一个接一个地被禁了。接一个地被禁了。 克服第一个障碍v 他必须训练这些机器人，让它们的活动显得有人味。他必须训练这些机器人，让它们的活动显得有人味。v 麦金利找到了他的朋友山姆麦金利找到了他的朋友山姆托里西（托里西（Sam Torrisi）。托里西是个神经学）。托里西是个神经学家，最近跟麦金利进行了家，最近跟麦金利进行了“技能交换技能交换”：他教麦金利音乐理论，麦金利教他：他教麦金利音乐理论，麦金利教他高等数学。高等数学。v 托里西也是托里西也是OkCupid的用户，他同意让麦金利在自己的计算机上安装间谍的用户，他同意让麦金利在自己的计算机上安装间谍软件，跟踪自己使用这

33、个网站的方式。有了这种数据，麦金利就可以模仿托软件，跟踪自己使用这个网站的方式。有了这种数据，麦金利就可以模仿托里西的点击和打字速度给机器人编程了。里西的点击和打字速度给机器人编程了。v 麦金利从家里搬来了第二台计算机，把它接到数学系的宽带上，让机器人每麦金利从家里搬来了第二台计算机，把它接到数学系的宽带上，让机器人每天天24小时不间断地运行。三周后他就从全美各地小时不间断地运行。三周后他就从全美各地2万名女性用户那里搜集了万名女性用户那里搜集了600万条问题和回答万条问题和回答。v 麦金利现在一头扎进了这些数据，完全把博士论文当成了副业。本来他就已麦金利现在一头扎进了这些数据，完全把博士论文

34、当成了副业。本来他就已经常常在小隔间里过夜，现在他几乎不回公寓了，完全搬进了这个小隔间。经常常在小隔间里过夜，现在他几乎不回公寓了，完全搬进了这个小隔间。到了睡觉的时候，只要在办公桌上铺上薄薄的床垫，就可以躺上去了。到了睡觉的时候，只要在办公桌上铺上薄薄的床垫，就可以躺上去了。 女性用户的七种类型v 麦金利的计划要想奏效，就必须麦金利的计划要想奏效，就必须找出问卷数据中的规律找出问卷数据中的规律根据数据的相似根据数据的相似性，把女性分为大致几个类型。性，把女性分为大致几个类型。v 贝尔实验室（贝尔实验室（Bell Labs）有个名叫有个名叫K-Modes的算法的算法，最早是在，最早是在1998

35、年年投入使用，用来分析病变的大豆作物，它可以把具有相似性的数据凝结在一投入使用，用来分析病变的大豆作物，它可以把具有相似性的数据凝结在一起。麦金利对它做了一些微调，以便调整结果的粘度。然后他用这个修改后起。麦金利对它做了一些微调，以便调整结果的粘度。然后他用这个修改后的算法来处理搜集到的问卷数据。的算法来处理搜集到的问卷数据。v 他调整刻度盘，发现了一个点，可以根据他调整刻度盘，发现了一个点，可以根据2万名女性的问题和答案，把她们万名女性的问题和答案，把她们分成七个在统计学上具有明显区别的类型。分成七个在统计学上具有明显区别的类型。“当时我欣喜若狂。当时我欣喜若狂。”他说。他说。v 他给机器人

36、重新分派了任务，以便搜集另一个样本：他给机器人重新分派了任务，以便搜集另一个样本： 5000名在过去一个月名在过去一个月内登陆过内登陆过OkCupid的洛杉矶和旧金山女性。然后他再用修改过的的洛杉矶和旧金山女性。然后他再用修改过的 K-Modes算法处理她们的问卷数据。结果这些女性用户也以同样的方式被划算法处理她们的问卷数据。结果这些女性用户也以同样的方式被划分成七个类型，证实他的统计抽样方法确实有效。分成七个类型，证实他的统计抽样方法确实有效。v 他的做法体现了一种数学建模思想。（他的做法体现了一种数学建模思想。（模型检验模型检验） v k-means聚类算法简单易行，时间复杂度低，聚类算法

37、简单易行，时间复杂度低，v 它主要用于以数值为单位的数据集合，也可以适用于大规模的数据集它主要用于以数值为单位的数据集合，也可以适用于大规模的数据集，但同时只能处理数值的属性限制了它的应用范围。，但同时只能处理数值的属性限制了它的应用范围。v 它的具体算法步骤如下：它的具体算法步骤如下：v 1.确立最终聚类处理得到类的个数，如果有先验知识，如实现知道一确立最终聚类处理得到类的个数，如果有先验知识，如实现知道一个数据集为有个数据集为有3类，则可设类，则可设k=3；如果不清楚，有一些指导性方法可；如果不清楚，有一些指导性方法可确定估计值。确定估计值。v 2.选取选取k条初始记录作为质心，这条初始记

38、录作为质心，这k条记录要求彼此之间的相关性条记录要求彼此之间的相关性D尽量大，而由于记录的属性使用数值表示，故我们可以使用欧式距离尽量大，而由于记录的属性使用数值表示，故我们可以使用欧式距离（Euclidean distance）来计算相关性）来计算相关性D，这样可以保证记录的，这样可以保证记录的相关性低，提高聚类效果。相关性低，提高聚类效果。v 3.从数据集读取一条记录，计算它与从数据集读取一条记录，计算它与k个质心的欧式距离，并归并到个质心的欧式距离，并归并到距离最短的一个类内；同时，更新该类的质心。重复第三步直至将数距离最短的一个类内；同时，更新该类的质心。重复第三步直至将数据集读取完。

39、据集读取完。v 4.重新调整记录所属的类，分配后更新所有类的质心，不断重复第四重新调整记录所属的类，分配后更新所有类的质心，不断重复第四步直到没有记录需要重新分配。步直到没有记录需要重新分配。v K-means算法有算法有2个核心问题：个核心问题：1.度量记录之间的相关性的计算公度量记录之间的相关性的计算公式，此处采用欧式距离。式，此处采用欧式距离。2.更新类内质心的方法，此处采用平均值法更新类内质心的方法，此处采用平均值法，即，即means。v K-modes算法可以看做是算法可以看做是k-means算法在非数值属性集合上的版本。它算法在非数值属性集合上的版本。它的具体算法步骤如下：的具体算

40、法步骤如下：v 1.度量记录之间的相关性度量记录之间的相关性D的计算公式是比较两记录之间所有属性，如属性的计算公式是比较两记录之间所有属性，如属性不同则给不同则给D加加1，如相同则不加，所以，如相同则不加，所以D越大，记录间的不相关程度越强（与越大，记录间的不相关程度越强（与欧式距离代表的意义是一样的）；欧式距离代表的意义是一样的）；v 2.更新更新modes，使用一个类的每个属性出现频率最大的那个属性值作为代，使用一个类的每个属性出现频率最大的那个属性值作为代表类的属性值表类的属性值(如如a,1 a,2 b,1 a,1 c,3)代表模式为代表模式为a,1;v 3.类似类似k-means的第四

41、步，对次调整每条记录所属的类。的第四步，对次调整每条记录所属的类。v K-Prototype算法是结合算法是结合K-Means与与K-modes算法，针对混合属性的，算法，针对混合属性的，解决解决2个核心问题如下：个核心问题如下：v 1.度量具有混合属性的方法是，数值属性采用度量具有混合属性的方法是，数值属性采用K-means方法得到方法得到P1，分类，分类属性采用属性采用K-modes方法方法P2，那么，那么D=P1+a*P2，a是权重。如果觉得分是权重。如果觉得分类属性重要，则增加类属性重要，则增加a，否则减少，否则减少a，a=0时即只有数值属性时即只有数值属性v 2.更新一个簇的中心的方

42、法，方法是结合更新一个簇的中心的方法，方法是结合K-Means与与K-modes的更新。的更新。v 方法总结：这三种方法将只针对数值属性的方法总结：这三种方法将只针对数值属性的k-means算法扩展到可以解决算法扩展到可以解决分类属性与混合属性，实验结果表明分类属性与混合属性，实验结果表明k-modes的算法时间复杂度比其余两的算法时间复杂度比其余两者低。三者时间复杂度成线性增长。但在使用时，还存在问题如下：者低。三者时间复杂度成线性增长。但在使用时，还存在问题如下：1.K值值的确立的确立2.k-prototype中权重中权重a的确立的确立3.k条初始记录的选取。条初始记录的选取。目标锁定两种

43、类型v 在这一步，麦金利的任务是在这一步，麦金利的任务是选择最适合自己的类型选择最适合自己的类型。他从每个类型中。他从每个类型中抽取了一些个人资料来查看。有一个类型太年轻，有两个类型太年长抽取了一些个人资料来查看。有一个类型太年轻，有两个类型太年长，还有一个属于基督教徒类型。，还有一个属于基督教徒类型。v 有一个类型让他很感兴趣：她们大多二十多岁，看上去特立独行，参有一个类型让他很感兴趣：她们大多二十多岁，看上去特立独行，参与音乐和艺术活动。麦金利希望在这个类型中大海捞针，找到他的真与音乐和艺术活动。麦金利希望在这个类型中大海捞针，找到他的真爱。爱。v 实际上，还有一个类型看起来也很酷实际上，

44、还有一个类型看起来也很酷年龄稍大的女性，是创造性年龄稍大的女性，是创造性工作专业人士，比如编辑、设计师。他决定两个类型都试试。于是他工作专业人士，比如编辑、设计师。他决定两个类型都试试。于是他创建了两份个人资料，分别为两个类型做了优化。创建了两份个人资料，分别为两个类型做了优化。v 他对这两个类型女用户的文字信息进行了挖掘，以便了解她们对什么他对这两个类型女用户的文字信息进行了挖掘，以便了解她们对什么东西感兴趣。他发现东西感兴趣。他发现数学是一个热门话题数学是一个热门话题，于是他写了一篇自我介绍，于是他写了一篇自我介绍，强调自己是一名数学老师。，强调自己是一名数学老师。 精准营销精准营销v 但

45、是，最重要的是问卷问题。他挑选出在这两种类型中最但是，最重要的是问卷问题。他挑选出在这两种类型中最流行的流行的500个问题，诚实地填写了答案个问题，诚实地填写了答案他不想把自己他不想把自己未来的关系建立在计算机生成的谎言上，但是他会让计算未来的关系建立在计算机生成的谎言上，但是他会让计算机算出应该如何给每个问题的重要性打分。他使用一种名机算出应该如何给每个问题的重要性打分。他使用一种名为为“自适应提升自适应提升”（adaptive boosting）的机器学习）的机器学习算法来计算最佳分数。算法来计算最佳分数。v 就这样，他创建了两份个人资料。一份上传了他攀岩的照就这样，他创建了两份个人资料。

46、一份上传了他攀岩的照片，另一份上传了他在一次演出中弹吉他的照片。片，另一份上传了他在一次演出中弹吉他的照片。 v 当回答完最后一个问题并给它打分之后，麦金利在当回答完最后一个问题并给它打分之后，麦金利在OkCupid上进行了搜索，上进行了搜索，按照跟自己的匹配度来排列洛按照跟自己的匹配度来排列洛杉矶女性用户杉矶女性用户。第一页的女性跟他的匹配度高达。第一页的女性跟他的匹配度高达99%。他继续向下滚动页面，直到一万名洛杉矶女性之后，他仍他继续向下滚动页面，直到一万名洛杉矶女性之后，他仍然跟她们有然跟她们有90%以上的匹配度。以上的匹配度。 私信滚滚而来v 要引起这些女性的注意，麦金利还需要做另一

47、件事。要引起这些女性的注意，麦金利还需要做另一件事。 在在OkCupid上，每当上，每当有人浏览你的个人资料时，你就会收到提醒。所以有人浏览你的个人资料时，你就会收到提醒。所以麦金利写了一个新程序，麦金利写了一个新程序，专门去查看跟他的匹配率最高的女性用户的页面专门去查看跟他的匹配率最高的女性用户的页面。v 这个程序按照年龄顺序进行浏览：周一浏览这个程序按照年龄顺序进行浏览：周一浏览1000名名41岁女性的页面，周二岁女性的页面，周二浏览浏览1000名名40岁女性的页面，以此类推，一直到两个星期后，浏览岁女性的页面，以此类推，一直到两个星期后，浏览1000名名27岁女性的页面。岁女性的页面。v

48、 在这些用户中，有大约在这些用户中，有大约400名女性也反过来查看了麦金利的个人资料。结果名女性也反过来查看了麦金利的个人资料。结果私信滚滚而来。私信滚滚而来。v “我到现在为止还没有遇到过算牌很厉害的人，我觉得你的个人资料很有意我到现在为止还没有遇到过算牌很厉害的人，我觉得你的个人资料很有意思。思。”一位女性用户写道。一位女性用户写道。“我想跟你打个招呼。我想跟你打个招呼。”v “嗨，你的个人资料确实打动了我，我想跟你打个招呼。嗨，你的个人资料确实打动了我，我想跟你打个招呼。”另一位写道。另一位写道。“我认为我们之间有相当多的共同点，也许不是数学，但肯定有很多其他方面我认为我们之间有相当多的

49、共同点，也许不是数学，但肯定有很多其他方面！”v “你真的能翻译中文吗？你真的能翻译中文吗？”还有一位问道。还有一位问道。“我参加过一个中文培训班，但我参加过一个中文培训班，但效果并不好。效果并不好。” 前三次约会前三次约会v 到了现在，需要用到数学的部分已经完成，只剩下一件事要做了：到了现在，需要用到数学的部分已经完成，只剩下一件事要做了：麦金利必麦金利必须离开他的小隔间，去跟她们约会须离开他的小隔间，去跟她们约会。v 6月月30日，麦金利在加州大学洛杉矶分校的健身房洗了澡，开着他的破旧日日，麦金利在加州大学洛杉矶分校的健身房洗了澡，开着他的破旧日产车，去赴第一个约会。产车，去赴第一个约会。

50、v 希拉（希拉（Sheila）是一位网页设计师，来自）是一位网页设计师，来自A组，即较年轻的艺术类型。他们组，即较年轻的艺术类型。他们在回音公园的咖啡馆共进午餐。在回音公园的咖啡馆共进午餐。 “这真是可怕，这真是可怕，”麦金利说。麦金利说。“直到那一刻直到那一刻之前，这件事几乎都是一个学术活动。之前，这件事几乎都是一个学术活动。”这次约会结束时，状况已经很明显这次约会结束时，状况已经很明显：两个人不来电两个人不来电。v 第二天，麦金利继续赶赴第二个约会，这次是一个富有魅力的博客编辑，来第二天，麦金利继续赶赴第二个约会，这次是一个富有魅力的博客编辑，来自自B组。麦金利本打算跟她沿着回音公园的湖浪