November 16, 2011

[乱读书] 数据挖掘导论的导论

Book:Pang-Ning Tan, Michael Steinbach, Vipin Kumar. 数据挖掘导论(Introduction to Data Mining). 机械工业出版社,2010年9月第1版.


这种训练程序一跑就是2个小时的时候最适合乱读书了。最近买了本「数据挖掘导论」和一本「模式识别」,混着读。读「数据挖掘导论」是因为不知道那是什么,读「模式识别」是因为做了很久这方面的东西最近感觉有些混沌想要重读基础知识。所以两边的「乱读书」也会混着更新,懒的看书的就看我瞎侃好了。

数据挖掘是最近挺热的一个方向,业内做的比较好的典型有Google的广告推送、Amazon的推荐服务等等等,都是和数据挖掘相关的。有一个流传甚广的描述DM重要性的案例模板,或者是“可乐和尿不湿摆在一起为什么能提高销量”的故事,或者是“口香糖和电池”的版本,大体的意思都是“数据挖掘可以帮助零售企业,自动地从其大规模的零售数据中,发现一些有用的信息”。这也是本书中对「数据挖掘」所下的定义,关键词是“自动”、“大规模”和“有用”。

数据中的知识发现过程包括:数据→预处理→数据挖掘→后处理→有效信息。预处理包括特征选择、降维、归一化等等,后处理则是为了保证信息的有效性,包括可视化、模式解释和过滤等。数据挖掘在其中最大的作用是自动总结和筛选知识(我认为)。这是一个交叉性和应用性很强的领域,以数据库、分布式技术为基础,涉及统计学、人工智能、机器学习和模式识别等多领域。

其主要难点在于:

可扩展性Scalability。指其处理大规模数据的能力,不单是时间复杂度上的高效,还有对存储空间上的要求,比如海量数据往往意味着无法将其一次性读入主存中。并行或分布式算法往往具有较高的可扩展性;
高维度High Dimensionality。通常会有成百或者上千的属性来修饰数据,可能是时域上的,也可能是空间域上的,这意味着我们需要应付高维向量,这对于某些对维度敏感的传统算法是灾难性的(这点和CV领域很像);
非均匀的复杂的数据Heterogeneous and Complex Data。由于DM的应用领域很广泛,但不同领域的数据的属性是不同的;属性中可能同时混杂着不同类型(连续的、离散的),比如同时包含文本、超链接和图片的网页。这对DM前的数学建模是个挑战;
数据归属和分布式Data Ownership and Distribution。有时,数据并不存储在一个地方;有时,数据并不属于单一的组织。因此,我们需要分布式DM技术。这里的难点主要在三个方面:如何降低分布式系统的通信成本;如何有效地合并多方的DM结果;以及如何处理数据安全的问题;
非传统式的统计分析Non-traditional Analysis。传统统计方法通常是一个假设和验证的过程,需要手工地收集数据、设计实验来验证假说。但当面临大规模数据应用时,这种劳动密集型的实验方法是不可取的。DM是一个自动提出假说并自动收集数据、自动验证的过程,不再有精巧设计的实验,数据更趋于偶然性。

数据挖掘的主要任务可以分为预测Predictive和描述Descriptive两大类。预测类任务指通过数据的一些属性估计其他属性;描述类任务指从数据中获取其隐藏的模式(趋势、相关性、聚类、异常性等等)。

预测建模Predictive Modeling。主要用于解决分类Classification和回归Regression两类问题(这点上与机器学习对预测的定义一致);
关联性分析Association Analysis。指从数据中发掘强烈存在的特征间的关系,这种关系通常通过隐藏的规则或者特征的子集来表示。我们开头提到的“可乐和纸尿布”就属于这类任务;
聚类分析Cluster Analysis。指从数据中发掘拥有相似外观的群体,使得类内距离最小,类间距离最大。比如,寻找商品的相似购买者,或者通过关键词对文档主题的聚类;
异常检测Anomaly Detection。指从数据中检测行为异常者,主要的目标是准确地发现异常行为,并且避免误判。这个应用十分有用,比如通过购买记录检测信用卡的异常消费行为——不符合持卡人的消费习惯或年龄等。

初步感觉这本书会讲到很多和机器学习、模式识别重复的内容,似乎可以理解为统计模型在大规模数据及具体环境下的应用问题,是个讲究实际的领域。

October 31, 2011

Job Hunting Season 终了!我想我要一份严肃的工作!

9月开始10月落幕,这一季算是过去了。
投出去一共33份简历,还有10家没有消息;
挂掉8家笔试,5家没去笔试;
收到9个面试:28所不要女生,科大讯飞放弃,百度明天我要问问他上海的问题再决定要否继续面下去,平安科技虽然我也不想去但的确二面被挂了,剩下的5个收到了offer。
(加了下发现少了1家,那家是sogou,恩,后来我发现简历一直处于未提交的状态,网上测评登陆进去就说通过了,但连笔试资格都没给,算是个奇葩)

学弟来问怎么找工作,我这个笔试老挂的人实在没什么说服力。但是真心的,再从头来过,我还是会做这么多项目,只是闲暇时间不会再按着自己的喜好写什么Handii读什么论文,而是会找陈越jj说“我要参加ACM拿奖”,或者熟读各种“程序员面试宝典”、“编程珠玑”和“Linux/数据库/网络精通”直到看到题目就能说出它和第几章某题差不多。不然,如何考得过那些早早地从实验室抽身开始脱产复习的勤奋的孩子,更考不过考场上见到的我拍过照的以及事后洋洋得意和我谈到的在笔试中组团Raid的孩子们。虽然这并不代表说,我在基础知识上觉得薄弱或者输于他们,只是一种手段。反正笔试嘛,也没有人要和我讨论CV算法的可并行性、多分类的混沌空间、统计模型的过拟合问题。(这是从找工作的角度,从个人成长的角度,还是多做事吧,为了几年后能接到猎头的电话)

另外就是职业目标的事情。本科的时候很梦想做游戏,但是又很纠结做游戏,一方面怀疑游戏行业的价值,一方面国内热衷的网络游戏实在不是我的菜。我要是去哪家网游公司做策划,这家公司会倒闭的,大饼这么说,我也觉得。投简历的时候,也没多想,后来才发现投的游戏公司不过寥寥几家,以前一直想去的盛大也转投了创新院做多媒体。有一晚在DM留守群上聊天,才发现自己的想法,“还是严肃一点的工作好”;游戏是我少年时的梦,但现在已经不是我想要追求的事业。我想追求人工智能,想做分布式,想继续做视觉做HCI,唯独没有想过要做游戏。人恐怕都是会变的,在追逐梦想的过程中,梦想也在改变。但无论做什么,我想工作真的还是严肃点的好,这样做起来容易找到人生的意义,容易说服自己努力,娱乐和生活也会更加有意思。

最后随便写点面经。面试其实我也没什么经验,认真面的就6家。

平安科技是我面的第一家公司,第一次遇到群P,第一次做面试前的自我介绍,很紧张,说话都有些发抖;但是完全没有技术面,在这点上对之后没有多少帮助。但有了第一次之后,以后的面试就感觉不到紧张了。

再接着是浙江大华。给不了多少钱,旁人总说你计算机的怎么看得上的一家公司。但我投它面它,是因为看重它未来的市场和前景,以及和我研究方向的高切合度。(大华是做安防、智能监控的,海康来的太晚,我就把它忽略了。)这场面试其实也没有具体的技术问题,似乎面试官是问过别人算法题的,不过到了我这里就变成“你做过的东西和我们部门的工作很相似,你要是愿意来,我们是很欢迎的”,就结束了。HR倒是问了些犀利的问题,还问了关于薪酬。在这之前我对薪酬是没有具体的概念的,就随便说了个数字,以致于后来谈offer都不好开口要求涨点。这是我对自身价值认知和不够坦率的问题,需要反省。

之后酱油阿里巴巴。一面遇到个做Java的,让随便写个冒泡排序,我刷刷刷写了,总觉得哪里错了但又想不起来,然后给他看,他居然说差不多(我擦,后来我会来重写了下,发现果然错了,内循环写错了点。。)那人后来还问我“你一直做C,让你做Java,会不会不行啊”,我当时脑子一热,心想不就是Java么,说“学Java只需要一个礼拜!”当时面试官就惊了,转而言其他。。现在想想,那应该是个好人,不然我当场就被赶出来了,居然当着人家Java程序员的面鄙视Java,活腻了,绝对活腻了。

之后等来了上海联影。联影是家刚起步的做医疗器械的新公司,但是听说有很多从西门子跳来的大牛。医疗器械是块大蛋糕,做的好了有市场了以后钱途无量,国外好多视觉图形学实验室都是靠医疗视觉的项目维持经费的。那天下午我接了大约6个电面电话,每个都长达半小时,面的范围包括OO概念、OS、视觉算法、Cuda、项目内容等等,接完还去现场面了技术和HR。真是虚脱了(中途我还酱油了完美的笔试,20+道选择题)。我很看好这家公司的前景,虽然他给钱不多,他加班,但这种创业型的公司拼的就是干劲、眼光、能力和运气。

第二天就面微策SE了。这是我面过最长时间的一个面试,4轮,每轮一个小时,从中午12点到下午5点。全英文。面到后来脑子都有点不灵清了,再加上前一天被轰炸过,面试官都说我“没睡醒”。。。都说微策爱面智力题,我却一题都没遇到,一下午尽写程序了;中途还被轰炸了些书本上的概念题,有些没答上来,回来翻了下博客才发现,我原来写过关于这方面的文章,垂足顿胸啊。一下午面下来,我对微策的感觉是很好的,正规,有条理,周到,面试官很nice(中途我把我的笔忘在了三面的地方,面试官还找到我四面的地方送过来,就是支便宜的自动铅笔,感动)。

AMD面试的流程就有些长了,从电面、笔试、再到面试,差不多有一个月的时间,也许这就是硬件公司的步调。不过AMD的人做事很认真,电面、笔试、面试前都特地电话过来确定我当天是否有空,把我感动的不行。最后面试的时候是3个面试官一起的,安排的40分钟,我差不多面了1个小时多10分钟,讲得口干舌燥。项目问的挺细,和他们做的方向不大一致,所以我就讲得浅显些。好在之前写过一些项目建议书,知道怎么通俗地描述我做的事情。沟通能力和描述问题的能力,在面试以及后续的工作中都很重要,这也是研究生2年半带给我最大的收获。

最后,感谢所有我面过、笔试过的公司。

September 26, 2011

怨妇贴。

这工作找的让人觉得大学7年就跟白读了一样,不如搞1年ACM,更不如上半年技校。

至今经历过的唯一我认为做的正确的笔试,只有WAP公司的三日编程题。虽然我最后因为时间关系没有实现完设计方案,当然更没有上交和之后的面试,但是很欣赏这样的笔试方式。

不过,大多的公司都不会有这家日企这么认真的态度,往往都是发张“代码不缩进”的卷子,好些的做个机考,考的也就是那些个题库里随机出来的ACM题。我从来不认为那些搞ACM的人有多牛掰,只是平日努力的方向不同而已。ACM得世界冠军固然难,可普通ACMer也就是“懂出题思路,懂ACM的通用Framework,做过90%题库”这样的水准。只是别人花在做项目、调系统、研究模型、发Paper的时间,他们花在了做ACM题上了而已。但就好比,料理竞赛再牛掰的大厨烧茶叶蛋也未必烧得好吃过一摆路边摊的一样,因为人家本来就是做这个的,而且天天做,日日做。

可是,公司们,说着“我们要找有坚实基础的、有解决问题能力的、有良好沟通能力和良好学习能力的人”,实际做的却是“来做ACM题吧”。也许公司并不是这么想的,但却这么做了。

我想我也是猜得到原因的。毕竟海面不可能,笔试是必须的。出优秀的题目太难,而且时效性很短,所以找题库或者根据题库改编是最方便的。而且ACM题有固定的标准,效率、内存,AC就是AC,不像开放题目,需要改卷管自己思考是否正确,而且标准模糊,从这个方面看也是最方便的。我并不否认考ACM题在某种意义上的公平性,但也是连高考也比不上的公平性。也许公司还认为“虽然不会做ACM不一定不是我们需要的人,但会做的人中笨的总不太多,反正应聘的人多,运气不好的我们也不要”。

所以,毕业求职季的种种笔试,成了又一次变相的高考,所有人看“程序员面试宝典”、看“编程珠玑”、看“编程之美”等等等,平日里碰都不会去碰的书。还有那些经典面试题,简直就是逼着你去看。大多数人也是从开始找工作的时候才开始看这些题,才开始了解到“原来还可以有这种题的”,比如我一直很不理解一道关于“单项链表查环”的题,为何不在插入链表时就保证无环呢?既然数据可能有环,为何不选择其他数据结构比如数组作为容器呢?这种笔试的结果通常是公司招到了看过这些题的人,而非会做这道题的人。

我并不希望做一个单纯的码农,并不喜欢捣鼓指针引用,代码只是工具,为了实现系统的一种交互不友善的软件而已,只是工具而已。也许是我在专业方向走的太远,再回过头来看这些充满Trick的ACM招式总觉得有些幼稚无聊。

不过现实就是这么无奈,逼着你同流合污,我也还是会去看这些书。写这篇日志的目的,是告诉10年20年后的我,如果做了笔试出题者或者面试管,记得己所不欲勿施于人,记得ACM考不出你想要的人。

August 18, 2011

八月中

君と夏の終わり 将来の夢 
大きな希望 忘れない
10年後の8月 また出会えるのを 信じて
最高の思い出を…

与你一起度过夏季的尽头 未来的梦想 庞大的希望 不会忘记
深信能够在十年后的八月重逢
成为最美好的回亿

今年四月番「あの日見た花の名前を僕達はまだ知らない。」我们仍未知道那天所看见的花的名字。这首ED至少贡献了这颗催泪弹80%的效果。据说是当年Zone乐队解散时的安可曲目,这种词,当年现场的一定哭翻了。

真TM煽情。

八月将逝。以此献给今生最后一个暑假。虽然不休假。

August 9, 2011

[基础算法] Random Forests

Random Forest(s),随机森林,又叫Random Trees[2][3],是一种由多棵决策树组合而成的联合预测模型,天然可以作为快速且有效的多类分类模型。如下图所示,RF中的每一棵决策树由众多split和node组成:split通过输入的test取值指引输出的走向(左或右);node为叶节点,决定单棵决策树的最终输出,在分类问题中为类属的概率分布或最大概率类属,在回归问题中为函数取值。整个RT的输出由众多决策树共同决定,argmax或者avg。
8-9-2011 2-41-59 PM

Node Test
node test通常很简单,但很多简单的拧在一起就变得无比强大,联合预测模型就是这样的东西。node test是因应用而异的。比如[1]的应用是基于深度图的人体部位识别,使用的node test是基于像素x的深度比较测试:
8-9-2011 2-53-40 PM
8-9-2011 2-54-54 PM
简单的说,就是比较像素x在u和v位移上的像素点的深度差是否大于某一阈值。u和v位移除以x深度值是为了让深度差与x本身的深度无关,与人体离相机的距离无关。这种node test乍一看是没有意义的,事实上也是没多少意义的,单个test的分类结果可能也只是比随机分类好那么一丁点。但就像Haar特征这种极弱的特征一样,起作用的关键在于后续的Boosting或Bagging——有效的联合可以联合的力量。

Training
RF属于Bagging类模型,因此大体训练过程和Bagging类似,关键在于样本的随机选取避免模型的overfitting问题。RF中的每棵决策树是分开训练的,彼此之间并无关联。对于每棵决策树,训练之前形成一个样本子集,在这个子集中有些样本可能出现多次,而另一些可能一次都没出现。接下去,就是循序决策树训练算法的,针对这个样本子集的单棵决策树训练。
单棵决策树的生成大致遵循以下过程:
1)随机生成样本子集;
2)分裂当前节点为左右节点,比较所有可选分裂,选取最优者;
3)重复2)直至达到最大节点深度,或当前节点分类精度达到要求。
这一过程是贪婪的。
当然对于不同的应用场合,训练过程中,会有细节上的差别,比如样本子集的生成过程、以及最优分割的定义。
在[1]中,决策树的真实样本其实是图片中的像素x,变量值则是上文提到的node test。但是,对于一张固定大小的图片而言可取的像素x是可数大量的,可取的位移(u,v)和深度差阈值几乎是不可数无限的。因此,[1]在训练单棵决策树前,要做的样本子集随机其实涉及到像素x集合的随机生成、位移(u,v)和深度差阈值组合的随机生成,最后还有训练深度图集合本身的随机生成。
最优分裂通常定义为使信息增量最大的分类,如[1]中的定义:
8-9-2011 3-34-37 PM
H指熵,通过分裂子集的部位标签分布计算。


Reference:
[1] J. Shotton, A. Fitzgibbon, M. Cook, T. Sharp, M. Finocchio, R. Moore, A. Kipman, and A. Blake. Real-Time Human Pose Recognition in Parts from a Single Depth Image. In CVPR 2011.
[2] L. Breiman. Random forests. Mach. Learning, 45(1):5–32, 2001.
[3] T. Hastie, R. Tibshirani, J. H. Friedman. The Elements of Statistical Learning. ISBN-13 978-0387952840, 2003, Springer.
[4] V. Lepetit, P. Lagger, and P. Fua. Randomized trees for real-time keypoint recognition. In Proc. CVPR, pages 2:775–781, 2005.

August 4, 2011

[源码笔记] OpenCV 2.3 :: Random Trees(二)

源码细节:

● 训练函数

bool CvRTrees::train( const CvMat* _train_data, int _tflag,
                        const CvMat* _responses, const CvMat* _var_idx,
                        const CvMat* _sample_idx, const CvMat* _var_type,
                        const CvMat* _missing_mask, CvRTParams params )

Step1:清理现场,调用clear()函数,删除和释放所有决策树,清除训练数据等;

Step2:构造适用于单棵决策树训练的参数包CvDTreeParams,主要就是对CvRTParams中一些参数的拷贝;

Step3:构建训练数据CvDTreeTrainData,主要涉及CvDTreeTrainData::set_data()函数。CvDTreeTrainData包含CvDTreeParams格式的参数包、被所有树共享的训练数据(优化结构使最优分裂更迅速)以及response类型和类数目等常用数据,还包括最终构造出来的树节点缓存等。

Step4:检查CvRTParams::nactive_vars使其不大于最大启用变量数;若nactive_vars传参为0,则默认赋值为最大启用变量数的平方根;若小于0,则报错退出;

Step5:创建并初始化一个变量活跃Mask(1×变量总数),初始化过程设置前nactive_vars个变量mask为1(活跃),其余为0(非活跃);

Step6:调用CvRTrees::grow_forest()开始生成森林。

● 生成森林

bool CvRTrees::grow_forest( const CvTermCriteria term_crit )

Step1:如果需要以准确率为终止条件或者需要计算变量的重要值(is_oob_or_vimportance = true),则需要创建并初始化以下数据:
oob_sample_votes  用于分类问题,样本数量×类数量,存储每个样本的测试分类;
oob_responses  用于回归问题,2×样本数量,这是一个不直接使用的数据,旨在为以下两个数据开辟空间;
oob_predictions_sum  用于回归问题,1×样本数量,存储每个样本的预测值之和;
oob_num_of_predictions  用于回归问题,1×样本数量,存储每个样本被预测的次数;
oob_samples_perm_ptr  用于存储乱序样本,样本数量×类数量;
samples_ptr / missing_ptr / true_resp_ptr  从训练数据中拷贝的样本数组、缺失Mask和真实response数组;
maximal_response  response的最大绝对值。

Step2:初始化以下数据:
trees  CvForestTree格式的单棵树集合,共max_ntrees棵,max_ntrees由CvDTreeParams定义;
sample_idx_mask_for_tree  存储每个样本是否参与当前树的构建,1×样本数量;
sample_idx_for_tree  存储在构建当前树时参与的样本序号,1×样本数量;

Step3:随机生成参与当前树构建的样本集(sample_idx_for_tree定义),调用CvForestTree::train()函数生成当前树,加入树集合中。CvForestTree::train()先调用CvDTreeTrainData::subsample_data()函数整理样本集,再通过调用CvForestTree::try_split_node()完成树的生成,try_split_node是一个递归函数,在分割当前节点后,会调用分割左右节点的try_split_node函数,直到准确率达到标准或者节点样本数过少;

Step4:如果需要以准确率为终止条件或者需要计算变量的重要值(is_oob_or_vimportance = true),则:
使用未参与当前树构建的样本,测试当前树的预测准确率;
若需计算变量的重要值,对于每一种变量,对每一个非参与样本,替换其该位置的变量值为另一随机样本的该变量值,再进行预测,其正确率的统计值与上一步当前树的预测准确率的差,将会累计到该变量的重要值中;

Step5:重复Step3 - 4,直到终止条件;

Step6:若需计算变量的重要值,归一化变量重要性到[0, 1]。

●训练单棵树

void CvDTree::try_split_node( CvDTreeNode* node )

Step1:调用CvDtree::calc_node_value()函数:对于分类问题,计算当前节点样本中最大样本数量的类别,最为该节点的类别,同时计算更新交叉验证错误率(命名带有cv_的数据);对于回归问题,也是类似的计算当前节点样本值的均值作为该节点的值,也计算更新交叉验证错误率;

Step2:作终止条件判断:样本数量是否过少;深度是否大于最大指定深度;对于分类问题,该节点是否只有一种类别;对于回归问题,交叉验证错误率是否已达到指定精度要求。若是,则停止分裂;

Step3:若可分裂,调用CvForestTree::find_best_split()函数寻找最优分裂,首先随机当前节点的活跃变量,再使用ForestTreeBestSplitFinder完成:ForestTreeBestSplitFinder对分类或回归问题、变量是否可数,分别处理。对于每个可用变量调用相应的find函数,获得针对某一变量的最佳分裂,再在这所有最佳分裂中依照quality值寻找最最优。find函数只关描述分类问题(回归其实差不多):

CvForestTree::find_split_ord_class():可数变量,在搜寻开始前,最主要的工作是建立一个按变量值升序的样本index序列,搜寻按照这个序列进行。最优分裂的依据是
8-3-2011 3-02-54 PM
也就是左右分裂所有类别中样本数量的平方  / 左右分裂的样本总数,再相加(= =还是公式看的懂些吧。。)
比如说,排序后的 A A B A B B C B C C 这样的序列,比较这样两种分裂方法:
          A A B A B B | C B C C 和 A A B A B B C B | C C
          第一种的quality是 (32 + 32 + 02) / 6 + (02 + 12 + 32) / 4 = 5.5
          第二种的quality是 (32 + 42 + 12) / 8 + (02 + 02 + 22) / 2 = 5.25
第一种更优秀些。感性地看,第一种的左分裂只有AB,右分裂只有BC,那么可能再来一次分裂就能完全分辨;而第二种虽然右分裂只有C,但是左分裂一团糟,其实完全没做什么事情。
最优搜寻过程中会跳过一些相差很小的以及不活跃的变量值,主要是为了避免在连续变量取值段出现分裂,这在真实预测中会降低树的鲁棒性。

CvForestTree::find_split_cat_class():不可数变量,分裂quality的计算与可数情况相似,不同的是分类的标准,不再是阈值对数值的左右划分,而是对变量取值的子集划分,比如将a b c d e五种可取变量值分为{a} + {b, c, d, e}、{a, b} + {c, d, e}等多种形式比较quality。统计的是左右分裂每个类别取该分裂子集中的变量值的样本数量的平方 / 左右分裂的样本总数,再相加。同样,搜寻会跳过样本数量很少的以及不活跃的分类取值。

Step4:若不存在最优分裂或者无法分裂,则释放相关数据后返回;否则,处理代理分裂、分割左右分裂数据、调用左右后续分裂。


References:
[1] OpenCV 2.3 Online Documentation: http://opencv.itseez.com/modules/ml/doc/random_trees.html
[2] Random Forests, Leo Breiman and Adele Cutler: http://www.stat.berkeley.edu/users/breiman/RandomForests/cc_home.htm
[3] T. Hastie, R. Tibshirani, J. H. Friedman. The Elements of Statistical Learning. ISBN-13 978-0387952840, 2003, Springer.

August 1, 2011

[源码笔记] OpenCV 2.3 :: Random Trees(一)

OpenCV2.3中Random Trees(R.T.)的继承结构:
7-22-2011 10-25-55 AM

API:

CvRTParams 定义R.T.训练用参数,CvDTreeParams的扩展子类,但并不用到CvDTreeParams(单一决策树)所需的所有参数。比如说,R.T.通常不需要剪枝,因此剪枝参数就不被用到。
max_depth
  单棵树所可能达到的最大深度
min_sample_count  树节点持续分裂的最小样本数量,也就是说,小于这个数节点就不持续分裂,变成叶子了
regression_accuracy  回归树的终止条件,如果所有节点的精度都达到要求就停止
use_surrogates  是否使用代理分裂。通常都是false,在有缺损数据或计算变量重要性的场合为true,比如,变量是色彩,而图片中有一部分区域因为光照是全黑的
max_categories  将所有可能取值聚类到有限类,以保证计算速度。树会以次优分裂(suboptimal split)的形式生长。只对2种取值以上的树有意义
priors  优先级设置,设定某些你尤其关心的类或值,使训练过程更关注它们的分类或回归精度。通常不设置
calc_var_importance  设置是否需要获取变量的重要值,一般设置true
nactive_vars  树的每个节点随机选择变量的数量,根据这些变量寻找最佳分裂。如果设置0值,则自动取变量总和的平方根
max_num_of_trees_in_the_forest  R.T.中可能存在的树的最大数量
forest_accuracy  准确率(作为终止条件)
termcrit_type  终止条件设置
  -- CV_TERMCRIT_ITER  以树的数目为终止条件,max_num_of_trees_in_the_forest生效
  -- CV_TERMCRIT_EPS  以准确率为终止条件,forest_accuracy生效
  -- CV_TERMCRIT_ITER | CV_TERMCRIT_EPS  两者同时作为终止条件
CvRTrees::train 训练R.T.
return bool  训练是否成功
train_data  训练数据:样本(一个样本由固定数量的多个变量定义),以Mat的形式存储,以列或行排列,必须是CV_32FC1格式
tflag  trainData的排列结构
  -- CV_ROW_SAMPLE  行排列
  -- CV_COL_SAMPLE  列排列
responses  训练数据:样本的值(输出),以一维Mat的形式存储,对应trainData,必须是CV_32FC1或CV_32SC1格式。对于分类问题,responses是类标签;对于回归问题,responses是需要逼近的函数取值
var_idx  定义感兴趣的变量,变量中的某些,传null表示全部
sample_idx  定义感兴趣的样本,样本中的某些,传null表示全部
var_type  定义responses的类型
  -- CV_VAR_CATEGORICAL 分类标签
  -- CV_VAR_ORDERED(CV_VAR_NUMERICAL)数值,用于回归问题
missing_mask  定义缺失数据,和train_data一样大的8位Mat
params  CvRTParams定义的训练参数
CvRTrees::train 训练R.T.(简短版的train函数)
return bool  训练是否成功
data  训练数据:CvMLData格式,可从外部.csv格式的文件读入,内部以Mat形式存储,也是类似的value / responses / missing mask。
params CvRTParams定义的训练参数
CvRTrees:predict 对一组输入样本进行预测(分类或回归)
return double  预测结果
sample  输入样本,格式同CvRTrees::train的train_data
missing_mask  定义缺失数据

Example:

  1. #include <cv.h>
  2. #include <stdio.h>
  3. #include <highgui.h>
  4. #include <ml.h>
  5. #include <map>
  6.  
  7. void print_result(float train_err, float test_err,
  8.                   const CvMat* _var_imp)
  9. {
  10.     printf( "train error    %f\n", train_err );
  11.     printf( "test error    %f\n\n", test_err );
  12.  
  13.     if (_var_imp)
  14.     {
  15.         cv::Mat var_imp(_var_imp), sorted_idx;
  16.         cv::sortIdx(var_imp, sorted_idx, CV_SORT_EVERY_ROW +
  17.             CV_SORT_DESCENDING);
  18.  
  19.         printf( "variable importance:\n" );
  20.         int i, n = (int)var_imp.total();
  21.         int type = var_imp.type();
  22.         CV_Assert(type == CV_32F || type == CV_64F);
  23.  
  24.         for( i = 0; i < n; i++)
  25.         {
  26.             int k = sorted_idx.at<int>(i);
  27.             printf( "%d\t%f\n", k, type == CV_32F ?
  28.                 var_imp.at<float>(k) :
  29.                 var_imp.at<double>(k));
  30.         }
  31.     }
  32.     printf("\n");
  33. }
  34.  
  35. int main()
  36. {
  37.     const char* filename = "data.xml";
  38.     int response_idx = 0;
  39.  
  40.     CvMLData data;
  41.     data.read_csv( filename ); // read data
  42.     data.set_response_idx( response_idx ); // set response index
  43.     data.change_var_type( response_idx,
  44.         CV_VAR_CATEGORICAL ); // set response type
  45.     // split train and test data
  46.     CvTrainTestSplit spl( 0.5f );
  47.     data.set_train_test_split( &spl );
  48.     data.set_miss_ch("?"); // set missing value
  49.  
  50.     CvRTrees rtrees;
  51.     rtrees.train( &data, CvRTParams( 10, 2, 0, false,
  52.         16, 0, true, 0, 100, 0, CV_TERMCRIT_ITER ));
  53.     print_result( rtrees.calc_error( &data, CV_TRAIN_ERROR),
  54.         rtrees.calc_error( &data, CV_TEST_ERROR ),
  55.         rtrees.get_var_importance() );
  56.  
  57.     return 0;
  58. }


References:
[1] OpenCV 2.3 Online Documentation: http://opencv.itseez.com/modules/ml/doc/random_trees.html
[2] Random Forests, Leo Breiman and Adele Cutler: http://www.stat.berkeley.edu/users/breiman/RandomForests/cc_home.htm
[3] T. Hastie, R. Tibshirani, J. H. Friedman. The Elements of Statistical Learning. ISBN-13 978-0387952840, 2003, Springer.