标签归档:数据挖掘

COS每周精选:数据挖掘中的十大算法

本期投稿:谢益辉 施涛 朱雪宁 王小

编辑:王小宁

国际权威的学术组织 The IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法:C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, 和 CART.,相关的论文在这里。最近有人把这些算法用R实现了

继续阅读COS每周精选:数据挖掘中的十大算法

[朝花夕拾] 迎接信息时代的统计挑战

本文略有修改,原文请点击此处

本文作者为俄亥俄州立大学的施涛。他把自己读郁彬老师的综述性文章:Embracing Statistical Challenges in the Information Technology Age的读后感和大家分享。

世事变迁,最近居然忽然有时间坐下来读些东西,重新审视一下这几年统计领域的发展了。粗略回想了一下,惭愧地发现我好像连博士导师的文章也没有系统地读过几篇,只是和自己研究有关的才详细夜读过。于是把她的一些老文章翻出来认真读读,了解一下她对统计研究和学科发展的观点。

木然回首,那文已在灯火阑珊处。2007年时她写过一篇综述性文章:Embracing Statistical Challenges in the Information Technology Age, Bin Yu (2007) Technometrics, 49(3), 237-248。摘要如下: 继续阅读[朝花夕拾] 迎接信息时代的统计挑战

COS每周精选:Simply Statistics为你解释GMM

本期投稿  冷静 肖楠 魏太云 谢益辉

  • 统计学家在其他领域大放异彩已经不是什么新鲜事,最近公布的三位诺贝尔经济学奖获得者之一,Lars Hansen,就是其中一员。有趣的是,因为Hansen 的理论过于复杂以致于众多新闻报道乃至经济学评论都对他的成果支支吾吾,一带而过。以至于Chicago Magazine 称之为the forgotten Nobel Prize winner。甚至在是诺贝尔奖委员会(Nobel Prize Committee)对三人研究的介绍中,对GMM究竟是什么也是暧昧不清。其实这一点早就有人担忧过了,Tyler Cowen就说了:“For years now journalists have asked me if Hansen might win, and if so, how they might explain his work to the general reading public.  Good luck with that one.”读到这里,学统计的优越感出来了有没有!要解释统计学家的研究还是得由统计学家来。Wikipedia上的GMM词条被认为太过难懂,正在召唤有志之士把它解释得简单点。Alex Peter 尝试着用基本的统计符号解释GMM ,不过门槛还是有点高。Simply Statistics 决心为普罗大众(general audience)写一篇科普文,如果你看懂了,恭喜你,你已经超越了一般的普罗大众,而成为一个统计学家眼中的普罗大众了。
    当然这一切高深晦涩都不影响Hansen 的GMM模型在资产定价、行为经济学中的广泛应用,因为它的普适性,以后还会应用得更广。这或许就是统计学朴实而深刻的终极目标——有用。与众位共勉。
  • R 的生物信息学小书: 之所以说是小书源于作者将其称为 a simple introduction to bioinformatics,但麻雀虽小,五脏俱全,该有的从头到尾一点不少。本书专注于与热带疾病有关的基因组分析,当然,也少不了我们的主人公R~
  • Julia的福利:Julia 的主要开发者之一在 Strata 站点上撰文阐释了 Julia 在数据科学中的定位: 文章娓娓道来,解释了 Julia 语言的设计、与 R 和  Python 的关系,综述了生态系统的现状,以及对未来的展望~
  • Python:    Troll Detection with Scikit-Learn 漂亮的简单模型 + 模型集成。话不多说,同道中人请点赞~这里附上scikit-learn的网站。
  • 微博速递:刚刚过去的kdd2013上有大牛wright做了一个“Optimization in Learning and Data Analysis“的keynote , slides里面对这方面的新旧内容做了一个很好的review, 实在是一份极好的导引。@晓风_机器学习
  • Xi’an给Beta分布手写了一个计算最高概率密度区间的函数(看看人家教授整天还在捣鼓R代码),下面有读者回复了一个更通用的函数,可是都是假设概率密度函数是单峰的,小编几年前对这个问题也有些兴趣,不过这次小编放狗搜了一下,发现Rob Hyndman十几年前(R诞生的前一年)就有一篇小文章来解决这个问题了:Computing and Graphing Highest Density Regions

分类器评价、混淆矩阵与ROC曲线

[box type=”info”]本文转载自阿稳的博客,原文链接请点击此处。本文主要介绍了数据挖掘中分类器的评价指标,以及混淆矩阵、ROC曲线等内容。

作者简介:阿稳,豆瓣,算法工程师。感兴趣的领域:推荐系统,数据挖掘,算法架构及实现的可扩展性,R环境编程。博客http://www.wentrue.net/blog/[/box]

假定你基于贝叶斯理论、神经网络或其他技术建立了自己的分类器。你如何得知自己是否干了一项漂亮的工作呢?你如何得知是否可以把自己的智能模块应用 于生产环境中,并获得同行的景仰以及老板的赞赏呢?评估分类器和创建它同样重要,如同在销售会议上,你会听到大量的夸大之词,但没有评估这就是一堆废话。 本节的目的在于帮助你评估自己的分类器,如果你是一个开发者或产品经理,这会帮助你理解第三方产品的合理与否。

“没有人知道所有的事情”、“人都会犯错”。这些箴言在计算机领域也有其对应的版本:没有一个分类器可以解决所有的问题,也没有一个分类器在所有的 数据集中都能良好地工作。在分类范畴中的学习技术属于有监督学习,“有监督”意味着分类器会利用已知的分类结果历经一个训练的过程,通过这种监督,它会尝 试着学习蕴含在训练数据集中的信息。你可以想象得到,训练数据集与你部署环境中实际数据的相关性会是分类是否成功的关键。

以上两段文字摘自我和陈钢同学翻译、即将出版的《智能web算法》中讲述分类器的一章。

作者试图说明一个问题:分类器的评估与分类器本身同样重要。评估分类器可信度的一个基本工具是混淆矩阵(confusion matrix)。以一个二分类问题作为研究对象,图1的混淆矩阵显示了一个分类器可能会遭遇的所有情况,其中列(positive/negative)对应于实例实际所属的类别,行(true/false)表示分类的正确与否(注,这里的混淆矩阵的结构跟[2]中的定义并不一样,但实际说明的问题是一致的)。

图1 混淆矩阵

其中FP和FN就是我们常说的第一类错误与第二类错误,以这四个基本指标可以衍生出多个分类器评价指标,如图2。还有下文将会用到的TPR=TP/P=TP/(TP+FN)。

图2 指标定义

我们常用的就是分类器的精确度(accuracy),在某些如推荐或信息获取领域还会组合使用precision-recall作为评价指标。因为你用于训练分类器的样本本身就是总体的一个抽样,所以这些指标的数值也仅仅是一种统计上的反映,如果你做多次抽样训练,跟别的随机变量一样,它一样会有期望、方差、置信区间这些概念。理论上说,训练样本量越大,你得到的这些指标的可信度就越高(即它们以某个概率落在的置信区间越窄)。不幸的是,实际中你未必会有那么多的样本,所以机器学习工作者设计出很多种方法来应对数据量不足情况下分类器的训练与评估,如k步交叉检验、留1法、boostrap等等。

以上这些都属于静态的指标,当正负样本不平衡时它会存在着严重的问题。极端情况下比如正负样本比例为1:99(这在有些领域并不少见),那么一个基准分类器只要把所有样本都判为负,它就拥有了99%的精确度,但这时的评价指标是不具有参考价值的。另外就是,现代分类器很多都不是简单地给出一个0或1的分类判定,而是给出一个分类的倾向程度,比如贝叶斯分类器输出的分类概率。对于这些分类器,当你取不同阈值,就可以得到不同的分类结果及分类器评价指标,依此人们又发明出来ROC曲线以及AUC(曲线包围面积)指标来衡量分类器的总体可信度。

ROC曲线最初源于20世纪70年代的信号检测理论,描述的是分类混淆矩阵中FPR-TPR两个量之间的相对变化情况。如果二元分类器输出的是对正样本的一个分类概率值,当取不同阈值时会得到不同的混淆矩阵,对应于ROC曲线上的一个点。那么ROC曲线就反映了FPR与TPR之间权衡的情况,通俗地来说,即在TPR随着FPR递增的情况下,谁增长得更快,快多少的问题。TPR增长得越快,曲线越往上屈,AUC就越大,反映了模型的分类性能就越好。当正负样本不平衡时,这种模型评价方式比起一般的精确度评价方式的好处尤其显著。一个典型的ROC曲线如图3所示(来自[2])。

图3 ROC曲线

[1] 《智能web算法》
[2] http://en.wikipedia.org/wiki/Receiver_operating_characteristic

首届全国大学生数据挖掘邀请赛圆满结束

 

2011年5月8日,来自浙江大学、厦门大学、复旦大学、浙江大学、北京大学、东南大学、中山大学、北京航空航天大学大学等多所高校的获奖队伍聚集于中国科学技术大学进行比赛的最终答辩环节,确定了最终的名次和奖项,标志着经过一个多月的群雄逐鹿,首届全国大学生数据挖掘邀请赛终于圆满结束。首届全国大学生数据挖掘邀请赛是由中国科技大学管理学院、中国人民大学统计学院和统计之都发起并主办,由上海花千树信息科技有限公司提供资金赞助和服务器支持。在一个多月的比赛时间中,共有来自大陆、香港及海外多所高校的1115支队伍注册参赛,期间有303支队伍成功提交预测结果,最终有240只队伍全程参与比赛。

赛题背景

以某大型婚恋网站交友数据为依托的推荐系统

队伍信息

总注册队伍1115支,其中本科生队伍794支,研究生队伍321支,分别来自以下一百多所高校及研究所:

安徽大学、安徽理工大学、安徽农业大学、北方工业大学、北方民族大学、北京大学、北京工商大学、北京航空航天大学、北京理工大学、北京林业大学、北京信息科技大学、北京邮电大学、北京语言大学、大连理工大学、大连民族学院、电子科技大学、电子科学技术大学、东北大学、东北师范大学、东华大学、东南大学、多伦多大学、福州大学、复旦大学、广东工业大学、广东省中山大学、广东外语外贸大学、广西大学、广州大学、桂林理工大学、国防科学技术大学、哈尔滨工业大学、哈尔滨工业大学深圳研究生院、杭州电子科技大学、合肥工业大学、河南工业大学、河南科技大学、湖北大学、湖南大学、华东理工大学、华东师范大学、华南理工大学、华南农业大学、华中科技大学、华中农业大学、华中师范大学、暨南大学、江西财经大学、兰州大学、洛阳理工学院、南昌大学、南方医科大学、南京财经大学、南京大学、南京航空航天大学、南京理工大学、南京农业大学、南京医科大学、南开大学、清华大学、人民大学、厦门大学、山东大学、山东科技大学、汕头大学、上海财经大学、上海大学、上海交通大学、上海师范大学、深圳大学、首都经济贸易大学、四川大学、苏州大学、太原理工大学、天津大学、天津工业大学、同济大学、乌普萨拉大学、武汉大学、武汉理工大学、西安财经学院、西安电子科技大学、西安交通大学、西安交通大学、西南财经大学、西南科技大学、香港科技大学、新加坡国立大学、新疆大学、云南财经大学、浙江财经学院、浙江大学、浙江大学城市学院、浙江工业大学、浙江理工大学、浙江师范、浙江师范大学、郑州大学、中国地质大学、中国地质大学(北京)、中国地质大学(武汉)、中国计量学院、中国科学技术大学、中国矿业大学、中国人民大学、中科院合肥研究院、中科院计算所、中科院声学所、中科院研究生院、中南财经政法大学、中南大学、中山大学、中央财经大学、重庆邮电大学、周口师范学院

 

获奖信息

本科生组:

名次 团队 队员 学校 院系
1 FooBar 仝子飞、刘佳硉 浙江大学 计算机科学与技术学院-计算机科学与工程学系
2 OldCubic 彭兵月、 刘宇辰 北京航空航天大学、清华大学 软件学院-软件工程系、经济管理学院-管理科学与工程系
3 LightSpeed 解浚源、陈宇澄 中国科学技术大学 计算机学院-计算机系
4 SiNZeRo 田文涛、洪诗保、胡亚光、叶挺 厦门大学 信息科学与技术学院-计算机科学与技术系
5 FDM 王超、张俊、董家为、王玥 复旦大学 计算机科学技术学院
6 forever 杨洋、陈章麒、姜涛、竺紫威 中国科学技术大学 少年班学院
7 兰州烧饼 蓝润荣 中国科学技术大学 管理学院-统计与金融系
8 zaq1xsw2tktk 唐坤、徐东昊 北京大学 数学科学学院-信息科学系、数学科学学院-科学与工程计算系

 

研究生组:

名次 团队 队员 学校 院系
1 RecSys1 宝腾飞、刘淇、程文华、聂鹏宇 中国科学技术大学 计算机学院
2 ForeverDream 张驰原、 李成 浙江大学 计算机学院-计算机应用技术系
3 数据掘金 徐童、曾广翔、季波、陈永环 中国科学技术大学 计算机学院-计算机系(1、2)、信息学院-自动化系(3、4)
4 totoro 杜龙志 北京大学 信息科学技术学院-计算机软件与理论
5 DataAnts 谢妍、刁瑞、来斯惟 中国科学院 数学与系统科学研究院(1、2)、自动化研究所(3)
6 icebergs 黄凯明、陆建、蒋玖川、章平 东南大学 信息科学与工程学院
7 Crystal 杨飞雕 中山大学 信息科学与技术学院-计算机科学与技术
8 napoloen 黄浩 浙江大学 计算机学院-计算机科学与工程学系

其中,第1名为一等奖(奖金10000¥),第2名为二等奖(奖金5000¥),第3~8名为三等奖(3~5名奖金2000¥,6~8名奖金500¥)。

附:首届全国大学生数据挖掘邀请赛结果排名(前100名)

竞赛相关数据展示

每天注册的队伍数:

上图为3月16日~4月15日每天注册的队伍数(注:竞赛于3月19日全面公开注册,在此之前在对中科大学生提前公布了注册网站以测试系统)。

每日有效提交次数:

上图为3月23日~4月27日每天成功提交的符合规范的预测结果数目,总共提交的次数为11162次。

提交次数频数:

上图为提交次数的频数图,从上图可以看出,大部分队伍提交次数很少。提交次数超过10的队伍有217个,超过50的有70个,超过100的有29个。最终获奖的队伍的提交总次数都很高。

赛后相关博文及帖子

旁门左道:第一届全国大学生数据挖掘邀请赛-数据集分析篇

JiangFeng:第一届数据挖掘邀请赛 – 缘来如此

ruikoeln:数据挖掘邀请赛-一个酱油党的感言

rainywh269:数据挖掘邀请赛 赛后感

cloud_wei:中科大之行及数据挖掘竞赛小总结

Mantous: 第一届全国大学生数据挖掘邀请赛-总结