机器学习预测机动车摇号:神秘的第七位

  1. 云栖社区>
  2. 博客>
  3. 正文

机器学习预测机动车摇号:神秘的第七位

长征6号 2016-11-28 10:58:00 浏览836
展开阅读全文

沙漠君按

上一篇帝都摇号文章在发布之后,总阅读量高达百万,不少读者觉得意犹未尽。当时成文过于仓促,很多细节没有理清。

两月磨一剑,看看我们能否解决下面的问题:

  • 13位用户编码真的是随机的吗?
  • 摇号池中有哪些未曾发现的规律和模式?
  • 我们能否用机器学习的方式预测摇号结果?

本篇文章用到了不少计算机和统计相关的背景知识,建议可以先看之前《沙漠之鹰》的那篇文章《绝对公平,破解北京机动车摇号的秘密》,从而对问题背景有更好的了解。

有关摇号资格和中签倍率

能够拥有摇号资格是比较幸运的:

  • 北京户口
  • 工作居住证
  • 社保满五年
  • 现役在京军人和武警部队

其中社保满五年的判定和买房不一样。摇号时,社保允许断月,不能断年。但买房则一个月都不能断。所以摇号的门槛还是低了很多。

当你摇号的次数每多六次,中签比率就增加一倍。但是三次摇号后如果没有按时上官网重新申请,则之后不会自动摇号,忘记重新申请的人非常多,好在中签比率得以保留。一旦摇中却没有购买,中签倍率清零。

摇号池是如何生成的?

当你注册之后,系统会为你提供13位的唯一ID,与身份证绑定,不论注销或是重新登记,ID都是确定的。通过审查之后,即可进入摇号池。

摇号池是按照ID的数值,从小到大升序排列的。当用户的中签概率不相等时,会稍微复杂一些::

image_1asocgiqt1n7d16gfcfl1qa0qn8m.png-136.9kB

所以,当参与摇号的ID确定后,摇号池也是唯一确定的。

随机数如何产生

随机数产生的方法,在上一篇文章中已经解释过了。大概如下图: image_1asou9vll1ebv7vp1jpt10f8aqc62.png-347.4kB

不过,这个产生随机数种子的【随机数算法】,并没有公开。我们无法验证其到底是随机产生的,还是事先定义好的。

如何根据随机种子摇号?

计算机生成的随机数,就是一连串看似随机生成,但背后有规律的数字序列。 但是,生成随机数需要“种子”(一个数字),如果不特别指定,种子是当前的操作系统时间,所以每次程序运行结果都不一样。但当指定了确认的种子号码,生成的序列就是确定的

image_1asoddhking81dvd1f86o931krq1g.png-98.9kB

之后,我们就能根据生成的序列从摇号池里挑选幸运儿了,以上面的图为例,依次挑选第1个,第8个,第32个...已经被选中的元素会被跳过。 (在附录提供了摇号程序的伪代码)

能否用机器学习来预测中签?

人为发现规律有些困难,因此我们尝试用最简单的线性模型,来看看对整个数据集上,是否能发现某些号码高中签概率的特征,系统框图如下: image_1asoenifd1mvtkao15e32tfqjs2a.png-81.8kB

十进制数可以被打散,比如7,可以打散为 0,0,0,0,0,0,0,1,0,0, 正好第七个数为1,其他为0。这样,用户的13位注册ID可以表示为130维的布尔特征(feature),而将是否摇中,作为要预测的结果(label)。 从所有472万用户中,随机抽取20万用户作为训练集,另外20万用户作为测试集,使用logistic回归模型,最终绘出了ROC曲线如下:

image_1asoevph9rqmd3t1ai819pk12fc34.png-123.2kB (有关ROC曲线的介绍可以参考附录)

这样的曲线,证明预测效果是相当好的!AUC值接近0.8。说人话,这个模型能够有很高的几率预测出一个特定号码是否中签

我当时就惊呆了!赶紧把模型在130维特征上的权重分布绘制出来(线性模型具备很好的解释性)

下面的曲线更是让人诧异!

image_1asof5hkm4anto2qoi1g6u1dkd3h.png-169.7kB 从这个曲线上表明,13位数字的第七位,极大地影响了是否被抽中!

我们对全局数据集进行分析:当ID第七位为0时,你有53%的可能性抽到,抽中的概率比没抽中还高。随着第七位数字逐渐变大,中签率也越来越低,当第七位为5时,中签率接近两千分之一了!(图表和说明参考附录3)

那是不是只要给我分配一个第七位为0的号码,就像投硬币投出正面,我就能在两到三次摇号摇中?

我曾经和现在的你一样,激动而诧异。后来发现,这个规律对于全局数据集有效,但对某一期摇号,线性模型没有任何预测能力。 这到底是怎么回事呢?

ID编码到底是如何确定的

从上一节的内容看出,13位编码并不是随机的,否则就不会产生如此明显的偏差。之前猜测,ID可能与用户的生日,身份证,性别或某些特定属性有关系。我们把13位编码,每一位都做了分析,并研究了其规律,下面的图是沙漠君的部分推理:

image_1asogrcgd1i8c1enra741krpdlc4o.png-384.5kB

前四位,看样子确实随机。但5和6,所有的号码都是10。基本能根据7,8位的数值推断出号码注册的期号。

后来经过反复分析,第7位到第13位,总共7位,是数据库的自增主键(附录4)!每个新用户注册,这个7位的数字就会加1,这七位,代表您是系统中的第几位用户。

所以到2016年第3期为止,系统注册的人数高达572万,但总共参与摇号的仅有467万,有105万人虽注册,却没有参与,可能原因是没有通过审核。(记不记得那些苛刻的条件?)

如何让特定的号码摇中?

了解了上面的原理,我们如何让特定的号码摇中?提前声明,本文仅为思想实验,没有任何真实性和指代性。 image_1asodtlje14denss4t2ojp1fok1t.png-317.1kB

对于方法1,假设我们想让第8个和第40个中签,就可以找到某个种子,让它生成的序列正好覆盖8和40。当然如果需要中签的号码特别多,则不一定能覆盖全面,于是就有方法2和方法3。

方法2参考图中示例,假设原先E中签,现在为了C中签,在C之前插入C0和C1(这都是两个无效号码,不代表任何人),即可将C挤到原来E的位置,从而C中签。

方法3和2类似,但是是清除了一些号码。空号码是否参与此次摇号无人关心,而一般人也难以验证自己是否参与了本次摇号。三次摇号后没有重新申请,就会自动暂停摇号,有关部门推出这样的举措真是贴心。

全国五大城市如何摇号

全国范围内,北京,杭州,天津,深圳和广州都是需要摇号的。只有上海和杭州拍牌。所有城市的摇号系统,都是同一家公司开发的,用户编码都是13位数字,网站和设计都非常相似,只是换了配色

北京不少自住房摇号系统,也是这家神秘公司开发的。不得不对这家地处北四环西路的神秘公司产生浓浓的敬佩之情。

我们对比了不同城市的信息公开程度,整理表格如下: image_1asob7r0o1dlsfti1rhs13qe1grh9.png-111.4kB 任何城市都不会同时提供以上五种全部信息。2013年以前,北京是提供中签者姓名的,可是因为一些特定姓名(如‘刘雪梅’)重复中签太多,导致舆论怀疑,后来就取消掉了。即使如此,北京依然是信息最为公开的。

对于一些城市(比如广州),只提供了中签者,其他人是否参与抽签和随机数种子都不知道,摇号视频也不公开。怪不得不少网民反响强烈呢,贵司要不考虑一下?

摇号数据中发现的有趣模式

假设能通过用户ID能知道其注册顺序和大概的注册时间,那么我们在所有参与摇号的数据中,发现了一些有趣的模式:

模式1

用户ID按照注册时间依次递增,但ID并不连续,可能因为未通过审核,但有的不连续区间高达20以上,也就是连续20个用户注册了,难道他们一个都没有通过审核!这样的情况还非常多。 image_1asout1pu1u9gm2f1v4r1g9p19lo6s.png-50.1kB

模式2

每年都有几千个老号码首次参与摇号,即使到了2016年,也会有上千个本应该在2011年就首次参与摇号的号码(这些号码非常小)。也许是这些人交够了五年社保,通过了资格审查吧。

image_1asov3u571fsvhen19sa12p2lmv79.png-25.5kB

模式3

210万用户曾经中断了摇号!中断时间有长有短,有的中断了1期,有的只摇了第一期。这个比例居然占了总人数的接近一半。

笔者之前忘了重新登记,导致曾有接近一年时间没有参与摇号,悲剧的是每个月百度都会给我发送未中签的短信。我一直以为自己参与了摇号呢。

为什么这家神秘的公司,不能稍微提醒一下那些忘了重新登记的用户呢?要知道大家基本都是通过手机号来注册登陆的呀。

还有没注意到的吗?

记不记得每个用户前面的1-4位的四位随机数?因为摇号池是按照总体13位数字来排序的,因此只要控制1-4位随机数,就能控制一个新产生的号码,插入到任何想插入的位置。

如果一个用户没有参与某一期的摇号,他自己都是非常难以发现的。

嗯.....

如果信息更透明一些就好了

我们要感谢北京的摇号系统,在几个城市中的公开程度是最为先进的。但是,如果下面的内容能公开,那真是一大幸事:

  • 六位随机数种子的【随机数生成算法】
  • 摇号池用户的姓名和摇中用户的姓名

也许有人会提到信息隐私的问题,难道摇中用户的隐私和没摇中的用户的隐私不一样么,要知道现在很多城市依然在公开摇中用户的姓名呢。搜索引擎依然能找到早些年的中签用户名单呢。

有关摇号的碎碎念

其实限牌看似合理,却彻底杜绝了资源的按需流动:早期不限购时期的车友,拥有好几辆车;而2011年以后的市民,不论多么着急用车,都难以指望摇号,只能通过一些地下手段,来支付高昂的租车牌费用。二手房都可以买卖,但为什么二手车车牌不行呢?

也许是因为,一旦车牌能交易,摇号便失去了其所谓的【纯洁性】,想想摇中了就相当于中了几十万的大奖,这一点也许是管理部门更不愿意看到的。而彻底封死现在车牌的总数量也不可行,车企一定不干,河北车牌又要爆发了。

现在电动车摇号毫无压力,只要申请就能中,沙漠君也查了很多电动车的信息,很不幸,满足“质量还可以,基本能开”标准的电动车几乎没有,即使来自纳税人的高昂的补贴也不能改变这一局面。至于电动车,以后有时间我们可以单独撰文讨论一下。

当然有人说了,没有车可以打车啊,现在滴滴和租车软件多么方便,还比买车省钱,不用考虑停车啊。

我们先不论经济账,也不论成为有车一族的【自由】,想想某一天下大雨,老婆很晚才到家,回来第一句话就是,【打不到车,我老板开车把我送回来的】,这个时候你看着窗外远去的车影,依稀还能看到那男人的嘴脸,一切吐槽都变得苍白,心里只剩下三个字:

【要有车】

附录

1. 摇号程序的伪代码(Python,仅作为演示,可能有纰漏)

slot_size=9  #摇号池大小
seed= 954732  #种子
quota= 3
array= ['A','B','C',...]
random= Random(seed);
selected=[]
while len(selected)<quota:
	index=random.next(slot_size)
	select= array[index]
	if select in selected:
        #选择的已被摇中,则跳过
		continue
print selected

2. ROC曲线

ROC全称为受试者工作特征曲线 (receiver operating characteristic curve), 以假阳性概率(False positive rate)为横轴,击中概率为纵轴所组成的坐标图,绘制特定刺激条件下由于采用不同的判断标准得出的不同结果画出的曲线。 ROC曲线围成的面积,就是AUC值。如果模型具备超强性能,那么曲线会尽可能靠近左上角,AUC值接近1; 若模型不具备任何预测能力,则ROC退化为一条对角线,AUC为1/2,和瞎猜没什么区别。ROC相比于精确度和召回率,更能描述一个模型的整体特征。对任意一次特定摇号的数据绘制ROC,得到的就是对角线。

3. 神秘的第七位

image_1asoffkmnu961asjh04152d9rq4b.png-113.2kB

计算机从0开始,第六位也就是我们所说的第7位,横轴二元组的(4,1)代表第七位为4且摇中,(4,2)代表为4且未摇中。

估计很多人又会因此传谣了,【通过你的号码预测吉凶,是否能够摇中】然后刷爆朋友圈,这规律全局来看,确实是对的。但仅仅是越小的号码越早注册,摇号的次数越多,摇中的概率就会越大,仅此而已,哎。


作者:热情的沙漠
出处:http://www.cnblogs.com/buptzym/
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。


本文转自FerventDesert博客园博客,原文链接:http://www.cnblogs.com/buptzym/p/5911129.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
长征6号
+ 关注