网站功能测试方法经验积累

网站的测试抛除行业业务外的测试
1、链接测试
1)链接是否存在
2)跳转链接是否符合预期
3)退出网站,是否能够继续访问某一孤立页面
第三点很重要,在企业级应用中一定需要测试,这类验证一般在框架上,所以在网站第一版本验证没有问题,后续只需要适当测试即可。(很多大型开放平台都支付单点登录功能,目前我还没有接触到这类测试)

2、表单测试
我们提交信息时就需要填写表单,例如注册、登录、新增某些业务等信息提交。例如身份证号的校验规则、手机、邮箱的校验规则、省份与城市/区域的校验等等。
1)必填项
2)值类型(中文、字母、数字、特殊字符)
3)边界值(取值范围、长度)
4)关联数据项(省份与城市/区域)
5)特殊校验规则(手机号11位,且规则比较固定;邮箱必须包含“@”符号)
表单的测试比较繁琐,但是要分类逐一校验,确保每一个数据项被充分校验(每一数据项至少有两类典型特征数值输入),才能确保我们的程序的健壮性。主要测试方法为:边界值测试、等价类测试,以及异常类测试。

3、导入验证
导入数据类似于表单的测试,导入数据的测试在每个数据项的验证基础上需要额外的验证
1)文件格式
2)office版本
3)导入文件为空
4)文件内容为空
5)文件中间有空行
导入不一定是excel,还有可能是图片、word,但是我们校验最多的事Excel/csv格式的文件。

4、列表查询
列表查询展示跟数据库息息相关,多表关联查询时数据展示等。主要有以下几个测试项:
1)进入页面时展示
2)输入查询条件是否正常显示数据
3)数据总数是否跟实际数据条数一致
4)是否能够正常翻页,尤其首页、尾页,翻页时数据是否能够正常切换
5)是否存在重复数据
6)如果列表有勾选数据项功能,勾选与取消是否能够正常操作,全选与全取消

5、中间件测试
有一些网站因为特殊业务原因,用到了一些中间件,例如mq消息组件。
1)mq是否有持久化要求?重启mq数据是否丢失
2)数据是否正常流转
3)删除队列后,是否能够自动恢复
之前在测试服务的时候,用以上方法比较多,在纯网站的测试上没有关注。不过有一次因为项目正好发版本。数据进入mq,但是没有写入数据库,更换版本后数据库中出现重复的数据。

6、数据库的测试
数据库的测试大多数是基于业务的,主外键的设置是否合理,表关联是否正确等。之前在做车联网服务测试时,经常会将数据库表关闭后观察数据是否写入本地文件,是否存在数据丢失等
1)重复数据
2)误删、误修改数据
3)数据未正常入库
4)非关系型数据的写入是否正常

7、复合场景测试
其实复合场景测试是我自己取的名字,之前测试车联网项目的时候特别有效。比如我把终端设备电源拔掉同时服务关掉等,比较容易发现一些不常见的问题。
这种测试方法在纯软件测试中不常见,只要我们考虑的场景足够多,就不会有遗漏???其实我也没有太多经验

8、兼容性测试
我总是听别人说兼容性测试,但是我自己所在项目一直都是重业务,所以这一块关注不多。一般web项目兼容性也就是IE,火狐、Chrome、360等一类浏览器的兼容性么?

中国数字文化

天干地支,简称为干支,源自中国远古时代对天象的观测。“甲、乙、丙、丁、戊、己、庚、辛、壬、癸”称为十天干,“子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥”称为十二地支。 天干地支组成形成了古代纪年历法。十干和十二支依次相配,组成六十个基本单位,两者按固定的顺序相互配合,组成了干支纪元法。从殷墟出土的甲骨文来看,天干地支在中国古代主要用于纪日,此外还曾用来纪月、纪年、纪时等。
一.准备知识

无极
“无极”出自《道德经》,一种古代哲学思想,指称道的终极性的概念。 [1] 无边际,无穷尽,无限,无终。“无极”一词在文言文中是表示“没有中心”的意思。代表着上古华人对事物产生之前状态的抽象理解。
一种连中心点都没有的状态,那里没有边界可言。既没有中心又没有边界,这种状态当然是无穷无尽“混沌”。
太极
太极,中国古代哲学用以说明世界本原的范畴,“太极”一词,出于《庄子》:“大道,在太极之上而不为高;在六极之下而不为深;先天地而不为久;长于上古而不为老”。太,即大;极,指尽头,极点。物极则变,变则化,所以变化之源是太极。
两仪
阴、阳
四象
少阳、少阴、老阳、老阴
五行
木、火、土、金、水
八卦
乾、兑、离、震、巽、坎、艮、坤
八卦:乾qián、坤kūn、震zhèn、巽xùn、坎kǎn、离lí、艮gèn、兑duì。
十天干
甲、乙、丙、丁、戊、己、庚、辛、壬、癸
甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊(wù)、己(jǐ)、庚(gēng)、辛(xīn)、壬(rén)、癸(guǐ)。
十二地支,又称“十二支”,古称十二子
子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥
子(zǐ)、丑(chǒu)、寅(yín)、卯(mǎo)、辰(chén)、巳(sì)、午(wǔ)、未(wèi)、申(shēn)、酉(yǒu)、戌(xū)、亥(hài)
地支,也是古代人用来纪录时闸的符号,因为有十二个符号,所以叫做十二支。这十二个符号是:子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥.古代中国人民用十二地攴纪月,月为阴.阴为地。 地支十二个符号也分为阴支和阳支两大类:
  阳支:子、寅、辰、午、申、戌;
  阴支:丑、卯、巳、未、酉、亥。

二、中国古文化
2.1 两仪的世界

阴阳是“对立统一或矛盾关系”的一种划分或细分,两者是种属关系。中国的传统学术中,有所谓“孤阴不生,独阳不长”及“无阳则阴无以生,无阴则阳无以化”的观念。老子在《道德经》中说:“道生一,一生二,二生三,三生万物。万物负阴而抱阳,冲气以为和”。阴阳的特性如下:

两者互相对立:万物皆有其互相对立的特性。如热为阳,寒为阴;天为阳,地为阴,说明了宇宙间所有事物皆对立存在。然这种相对特性并非绝对,而是相对。如上为阳,下为阴,平地相对于山峰,山峰为阳,平地为阴;但平地若相对于地底,则平地属阳、地底属阴,可见阴阳的相对性关系。

两者相互依靠、转化、消长:阴阳存在着互根互依,互相转化的关系,阴中有阳,阳中有阴,任何一方都不可能离开另一方单独存在,因彼此的消长,阴阳可以变化出许多不同的现象分类。

一切事物的最基本对立面  
在道,天为阳,地为阴;实为阳,虚为阴。轻为阳,重为阴。上为阳,下为阴。清为阳,浊为阴。
在天,日为阳,月为阴;明为阳,暗为阴。悟为阳,迷为阴。放下为阳,执著为阴。升为阳,降为阴。
在地,昼为阳,夜为阴;早为阳,晚为阴。热为阳,冷为阴。燥为阳,湿为阴。动为阳,静为阴。
在时,暑为阳,寒为阴;春夏为阳,秋冬为阴。快为阳,慢为阴。急为阳,缓为阴。速为阳,迟为阴。
在国,君为阳,臣为阴;尊为阳,卑为阴。本为阳,末为阴。始为阳,终为阴。高为阳,低为阴。
在家,父为阳,母为阴;夫为阳,妇为阴。雄为阳,雌为阴。攻为阳,守为阴。健为阳,顺为阴。
在事,象为阳,理为阴;雷电为阳,雨雪为阴。表为阳,里为阴。膜为阳,核为阴。皮为阳,骨为阴。
在人,男为阳,女为阴;得为阳,失为阴。进为阳,退为阴。助为阳,阻为阴。热情为阳,冷淡为阴。
在数,奇为阳,偶为阴;少为阳,多为阴。一为阳,万为阴。聚为阳,散为阴。专为阳,杂为阴。
在门,开为阳,合为阴;出为阳,入为阴。通为阳,隔为阴。外为阳,内为阴。左为阳,右为阴。
在心,向为阳,背为阴;前为阳,后为阴。未来为阳,过去为阴。远为阳,近为阴。宽为阳,窄为阴。
在命,生为阳,死为阴;长为阳,灭为阴。露为阳,隐为阴。起为阳,伏为阴。显为阳,藏为阴。盛为阳,衰为阴。强为阳,弱为阴。刚为阳,柔为阴。硬为阳,软为阴。
2.2. 四象的世界

指春、夏、秋、冬四时。体现于卦上,则指少阳、老阳、少阴、老阴四种爻象。
古代用来表示天空东、北、西、南四个方向的星象。即东方苍龙,北方玄武,西方白虎,南方朱雀。
指日、月、星、辰。
指阴、阳、刚、柔或吉、凶、悔、吝。
指暇、顺、雍、嘉四种治政要求。
指六书的象形、象事、象意、象声四体。
四象(或作四相)在中国传统文化中指青龙、白虎、朱雀、玄武,分别代表东西南北四个方向。
在二十八宿中,四象用来划分天上的星星,也称四神、四灵。春秋易传的天文阴阳学说中,是指四季天然气象,分别称为少阳,太阳,少阴,太阴。
中国传统方位是以南方在上方,和现代以北方在上方不同,所以描述四象方位,又会说左青龙(东)、右白虎(西)、前朱雀(南)、后玄武(北)来表示,并与五行学在方位(东木西金,北水南火)上相呼应。
四象的概念在古代的日本和朝鲜极度受重视,这些国家常以四圣、四圣兽称之。值得注意的是,虽然近来受到日本流行文化的影响,而开始习惯这种说法,但事实上中国历来对此四象并没有四圣的说法,一般所指的四圣乃伏羲、文王、周公和孔子等四个圣人。四象也指风、雨、雷、电,四种自然天候气象。
2.3. 五行的世界
初始含义
木——植物
火——热能
土——土地
金——金属
水——液体
对应关系
五行相生:木→火→土→金→水
木生火,火生土,土生金,金生水,水生木
阳木克火,阳火克土,阳土克金,阳金克活水,阳水克木
木生火:木干暖生火;
火生土:火焚木生土;
土生金:土藏矿生金;
金生水:金销熔生水;
水生木:水润泽生木。
五行相克:金→木→土→水→火
金克木,木克土,土克水,水克火,火克金
刚胜柔,故金胜木;因为刀具可砍伐树木;(兵器、剪刀不宜放床头)
专胜散,故木胜土;因为树木可扎根土里;木材
实胜虚,故土胜水;因为堤坝可阻止水流;石料
众胜寡,故水胜火;因为大水可熄灭火焰;泉水
精胜坚,故火胜金;因为烈火可熔化金属。
看似相克,其实是相生,木克土生火,水克火。(冰)亥克水。
2.4 八卦的世界
所谓卦,其实是中国古代劳动人民通过测量太阳位置,从而知季节、记录劳作规律的手段。
卦字的右边“卜”字,是象形,表示在地上竖杆子,右边那一点是太阳的影子。“卦”字左边的“圭”字是尺子,用来测量影子的长度位置。
通过长期测量,古代劳动人民掌握了春耕秋收的各种季节规律。
所谓八卦,应该是在地之八方测量结果的记录。
卦形歌诀
乾三连,坤六断,震仰盂,艮覆碗,离中虚,坎中满,兑上缺,巽下断。
八卦代数
先天八卦:乾一,兑二,离三,震四,巽五,坎六,艮七,坤八。
后天八卦:坎一、坤二、震三、巽四、五为中宫,乾六、兑七、艮八、离九。
八卦方位
先天八卦:乾南,坤北,离东,坎西,兑东南,震东北,巽西南,艮西北。
后天八卦:震东,兑西,离南,坎北,乾西北,坤西南,艮东北,巽东南。
八卦所属
乾、兑(金);震、巽(木);坤、艮(土);离(火);坎(水)。
八卦生克
伏羲八卦方位图
乾、兑(金)生坎(水),坎(水)生震、巽(木),震、巽(木)生离(火),离(火)生坤、艮(土),坤、艮(土)生乾、兑(金)。
乾、兑(金)克震、巽(木),震、巽(木)克坤、艮(土),坤、艮(土)克坎(水),坎(水)克离(火),离(火)克乾、兑(金)。
八卦旺衰
乾、兑旺于秋,衰于冬;震、巽旺于春,衰于夏;
坤、艮旺于四季,衰于秋;离旺于夏,衰于四季;
坎旺于冬,衰于春.(四季是指每个季节的后一个月。)
2.5 十天干
甲木为雷。雷者,阳气之嘘也,甲木属阳,故取象于雷焉。稽诸月令,仲春之月,雷乃发声,甲木旺,即其验也,况雷奋于地,木生于地,其理又无不同者。甲木至申而遂绝,以雷声至申而渐收也。凡命属甲日,主喜值春天,或类象,或趋干,或遥巳,或拱贵,俱大吉;运不喜西方。经云:木在春生,处世安然,必寿。
乙木为风。乙木长生在午,败在巳。在午而生者,盖乙为山林活木,至夏来而畅茂,诗所谓千章夏木青是也;其败巳云何?巳乃巽地,巽为风,木盛风生也,风生于木而反摧木,犹之火生于木而反焚木,其取败也固宜,所谓乙木为风者,木其所自生云尔。如人乙日建生者,在秋令大吉,秋令金旺,乙木能化能从而盘根错节,非利器无所裁成;逢亥必死,其落叶归根之时耶?
丙火为日。《说卦传》日:离为火为日,日与火皆文明之象,是以丙火为日之名不易焉。太阳朝出而夕入,阳火寅生而酉死,而又何异乎?凡六丙生冬夏,不如春秋,春日有暄万物之功,秋阳有燥万物之用,冬则阴晦,夏则炎蒸,宜细堆之。
丁火为星。丙火死而丁火遂从生焉,在天之日薄而星回也。类如此星象唯入夜故灿烂,阴火唯近晦故辉煌,丁不谓之星而何?凡丁日生人喜遇夜,喜遇秋,如星光之得时也;又喜行身 弱地,如石里所藏属丁火,石虽在水,即时取击,亦自有火;其丁巳一日,多克父兄妻子,盖财忌比劫,兄屈弟下,巳中有戊土,伤官也。
戊土为霞。土无专气,依火而生,霞无定体,借日以现,知丙火之为日,则知戊土之为霞矣。是霞者,日之馀也,日尽而霞将灭没,火熄则土无生意,故谓之霞也。如戊土日主爱四柱带水则为上格,霞水相辉而成文彩也;更喜年月干见癸,癸则为雨,雨后霞现而睹文明也。

己土为云。己土生居酉,酉,兑方也,其象为泽。先正曰:“天降时雨,山川出云。”然则云者,山泽之气也,己虽属土,以此论之,则其谓之云也亦宜。故甲己合而化土,其气上升而云施;云雷交而作雨,其泽下究而土润。此造化之至妙者与!凡身主属己土,贵坐酉,贵春生,贵见印,坐亥者不可见乙木,云升天,遇风则狼籍而不禁也。
庚金为月。庚乃酉方阳金,何以知其配月乎?曰:五行之有庚,犹四时之有月也;庚不待秋而长生,然必秋而始盛;月不待秋而后月,然必秋而益明。以色言,月固白也,其色同矣;以气言,金生水也,潮应月也,其气同矣。经云:金沈在子。见其与月沈波也,三日月见庚方见,月初生与庚为位也,故曰庚金为月。如人庚日生者,四柱有乙巳字出,谓之月白风清,秋为上,冬次之,春夏无取。
辛金为霜。八月,辛金建禄之地,是月也天气肃杀,白露为霜,草木黄落而衰,故五行阴木绝在此地,若木经斧斤之斩伐,未有所生焉者也。斧斤以时入山林,严霜以时杀草木,揆之天道,参之人事,信乎辛金之为霜矣。如辛人坐卯,未透乙,大富,坐亥透丙则贵。爱冬生。
壬水为秋露。春亦有露,何独拟之以秋?盖春露、雨露既濡之露,秋露、霜露既降之露也,露一也,春主生,秋主杀,功用不同有如此,然吾以壬为秋露也,盖露属水,而壬水生于申,水本能生木者,水既然在此而生,木何由于此而绝?故知
壬之为露,秋露也。如壬日生秋,见丁火最显,丁为星河,壬为秋露,一洗炎蒸,象纬昭然矣。
癸水为春霖。癸水生卯月,号曰春霖。盖阴木得雨而发生也,然至申则死,七、八月多干旱也。且卯前一位是辰,辰,龙宫也,卯近龙宫而水生,龙一奋遂化为雨焉;卯为雷门,雷一震而龙必兴焉,观此则癸水其春霖矣。如癸卯日透出己字者,有云行雨施之象,其人必有经济才也。春夏吉,秋冬不吉。
2.6 十二地支

一年十二个月,即地支十二个符号一个循环纪录。一月三旬.一旬十天,即天干十个符号一个循环纪录。将十二地支与十天干组合排列得到六十个不同的符号,这就是六十甲子。用甲子循环既可以纪年.又可以纪月,还可以纪日,甚至也可以纪时辰,十天干相对于十二地支而言,则为阳;十二地支相对于十天干而言,则为阴。天干与地支的关系犹如树干与树枝的关系一样,天干为树干,地支为树枝。
子是兹的意思,指万物兹萌于既动之阳气下。
丑是纽,阳气在上未降。
寅是移,引的意思,指万物始生寅然也。

卯是茂,言万物茂也。
辰是震的意思,物经震动而长。
巳是起,指阳气之盛。
午是仵的意思,指万物盛大枝柯密布。
未是味,万物皆成有滋味也。
申是身的意思,指万物的身体都已成就。
酉是老的意思,万物之老也。
戌是灭的意思,万物尽灭。
亥是核的意思,万物收藏。

十二生肖年
子鼠 丑牛 寅虎 卯兔 辰龙 巳蛇 午马 未羊 申猴 酉鸡 戌狗 亥猪

代表的时间
【子时】夜半,又名子夜、中夜:十二时辰的第一个时辰。(北京时间23时至01时)。
【丑时】鸡鸣,又名荒鸡:十二时辰的第二个时辰。(北京时间01时至03时)。
【寅时】平旦,又名黎明、早晨、日旦等:时是夜与日的交替之际。(北京时间03时至05时)。
【卯时】日出,又名日始、破晓、旭日等:指太阳刚刚露脸,冉冉初升的那段时间。(北京时间05时至07时)。
【辰时】食时,又名早食等:古代中国人民“朝食”之时也就是吃早饭时间,(北京时间07时至09时)。
【巳时】隅中,又名日禺等:临近中午的时候称为隅中。(北京时间09 时至11时)。
【午时】日中,又名日正、中午等:(北京时间11时至13时)。
【未时】日昳,又名日跌、日央等:太阳偏西为日跌。(北京时间13时至15时)。
【申时】哺时,又名日铺、夕食等:(北京时间15时至17时)。
【酉时】日入,又名日落、日沉、傍晚:意为太阳落山的时候。(北京时间17时至19时)。
【戌时】黄昏,又名日夕、日暮、日晚等:此时太阳已经落山,天将黑未黑。天地昏黄,万物朦胧,故称黄昏。(北京时间19时至21时)。
【亥时】人定,又名定昏等:此时夜色已深,人们也已经停止活动,安歇睡眠了。人定也就是人静。(北京时间21时至23时)。

对应日
日:由甲子日开始,按顺序先后排列,六十日刚好是一个干支的周期。

对应月份
寅、卯、辰、巳、午、未、申、酉、戌、亥、子、丑
正、二、三、四、五、六、七、八、九、十、十一月、腊月
寅、卯、辰是农历正二三月春季,春季万物发芽滋生,三合会为木
巳、午、未是农历四五六月夏季,夏季万物开花茂盛天气炎热,三合会为火
申、酉、戌是农历七八九月秋季,秋季万物成熟,肃杀,三合会为金
亥、子、丑是农历十十一腊月冬,冬季万物收藏,归于地下,冰雪覆盖地面,三合会为水

六十花甲子
中国古代采取天干地支作为计算年,月,日,时的方法,就是把每一个天干和地支按照一定的顺序而不重复地搭配起来,用来作为纪年,纪月,纪日,纪时的代号。把“天干”中的一个字摆在前面,后面配上“地支”中的一个字,这样就构成一对干支。如果“天干”以“甲”字开始,“地支”以“子”字开始顺序组合,就可以得到:
01.甲子02.乙丑03.丙寅04.丁卯05.戊辰06.己巳07.庚午08.辛未09.壬申10.癸酉
11.甲戌12.乙亥13.丙子14.丁丑15.戊寅16.己卯17.庚辰18.辛巳19.壬午20.癸未
21.甲申22.乙酉23.丙戌24.丁亥25.戊子26.己丑27.庚寅28.辛卯29.壬辰30.癸巳
31.甲午32.乙未33.丙申34.丁酉35.戊戌36.己亥37.庚子38.辛丑39.壬寅40.癸卯
41.甲辰42.乙巳43.丙午44.丁未45.戊申46.己酉47.庚戌48.辛亥49.壬子50.癸丑
51.甲寅52.乙卯53.丙辰54.丁巳55.戊午56.己未57.庚申58.辛酉59.壬戌60.癸亥

第16章 推荐系统

背景与挖掘目标

随着互联网的快速发展,用户很难快速从海量信息中寻找到自己感兴趣的信息。因此诞生了:搜索引擎+推荐系统

本章节-推荐系统:

帮助用户发现其感兴趣和可能感兴趣的信息。
让网站价值信息脱颖而出,得到广大用户的认可。
提高用户对网站的忠诚度和关注度,建立稳固用户群体。

分析方法与过程

本案例的目标是对用户进行推荐,即以一定的方式将用户与物品(本次指网页)之间建立联系。

由于用户访问网站的数据记录很多,如果不对数据进行分类处理,对所有的记录直接采用推荐系统进行推荐,这样会存在一下问题。

数据量太大意味着物品数与用户数很多,在模型构建用户与物品稀疏矩阵时,出现设备内存空间不够的情况,并且模型计算需要消耗大量的时间。
用户区别很大,不同的用户关注的信息不一样,因此,即使能够得到推荐结果,其效果也会不好。

为了避免出现上述问题,需要进行分类处理与分析。

正常的情况下,需要对用户的兴趣爱好以及需求进行分类。 因为在用户访问记录中,没有记录用户访问页面时间的长短,因此不容易判断用户兴趣爱好。 因此,本文根据用户浏览的网页信息进行分析处理,主要采用以下方法处理:以用户浏览网页的类型进行分类,然后对每个类型中的内容进行推荐。

分析过程如下:

从系统中获取用户访问网站的原始记录。
对数据进行多维分析,包括用户访问内容,流失用户分析以及用户分类等分析。
对数据进行预处理,包含数据去重、数据变换和数据分类鞥处理过程。
以用户访问html后缀的页面为关键条件,对数据进行处理。
对比多种推荐算法进行推荐,通过模型评价,得到比较好的智能推荐模型。通过模型对样本数据进行预测,获得推荐结果。

主流推荐算法
推荐方法 描述
基于内容推荐
协同过滤推荐
基于规则推荐
基于效用推荐
基于知识推荐
组合推荐

推荐方法对比
基于知识推荐

基于知识的推荐(Knowledge-based Recommendation)在某种程度是可以看成是一种推理(Inference)技术,它不是建立在用户需要和偏好基础上推荐的。基于知识的方法因它们所用的功能知识不同而有明显区别。效用知识(Functional Knowledge)是一种关于一个项目如何满足某一特定用户的知识,因此能解释需要和推荐的关系,所以用户资料可以是任何能支持推理的知识结构,它可以是用户已经规范化的查询,也可以是一个更详细的用户需要的表示。

基于知识的推荐
协同过滤推荐

memory-based推荐
    Item-based方法
    User-based方法
    Memory-based推荐方法通过执行最近邻搜索,把每一个Item或者User看成一个向量,计算其他所有Item或者User与它的相似度。有了Item或者User之间的两两相似度之后,就可以进行预测与推荐了。
model-based推荐
    Model-based推荐最常见的方法为Matrix factorization.
    矩阵分解通过把原始的评分矩阵R分解为两个矩阵相乘,并且只考虑有评分的值,训练时不考虑missing项的值。R矩阵分解成为U与V两个矩阵后,评分矩阵R中missing的值就可以通过U矩阵中的某列和V矩阵的某行相乘得到
    矩阵分解的目标函数: U矩阵与V矩阵的可以通过梯度下降(gradient descent)算法求得,通过交替更新u与v多次迭代收敛之后可求出U与V。
    矩阵分解背后的核心思想,找到两个矩阵,它们相乘之后得到的那个矩阵的值,与评分矩阵R中有值的位置中的值尽可能接近。这样一来,分解出来的两个矩阵相乘就尽可能还原了评分矩阵R,因为有值的地方,值都相差得尽可能地小,那么missing的值通过这样的方式计算得到,比较符合趋势。
协同过滤中主要存在如下两个问题:稀疏性与冷启动问题。已有的方案通常会通过引入多个不同的数据源或者辅助信息(Side information)来解决这些问题,用户的Side information可以是用户的基本个人信息、用户画像信息等,而Item的Side information可以是物品的content信息等。

效果评估

召回率和准确率 【人为统计分析】
F值(P-R曲线) 【偏重:非均衡问题】
ROC和AUC 【偏重:不同结果的对比】

第15章 大数据与MapReduce

大数据 概述

大数据: 收集到的数据已经远远超出了我们的处理能力。
大数据 场景

假如你为一家网络购物商店工作,很多用户访问该网站,其中有些人会购买商品,有些人则随意浏览后就离开。
对于你来说,可能很想识别那些有购物意愿的用户。
那么问题就来了,数据集可能会非常大,在单机上训练要运行好几天。
接下来:我们讲讲 MapRedece 如何来解决这样的问题

MapRedece
Hadoop 概述

Hadoop 是 MapRedece 框架的一个免费开源实现。
MapReduce: 分布式的计算框架,可以将单个计算作业分配给多台计算机执行。

MapRedece 原理

MapRedece 工作原理

主节点控制 MapReduce 的作业流程
MapReduce 的作业可以分成map任务和reduce任务
map 任务之间不做数据交流,reduce 任务也一样
在 map 和 reduce 阶段中间,有一个 sort 和 combine 阶段
数据被重复存放在不同的机器上,以防止某个机器失效
mapper 和 reducer 传输的数据形式为 key/value对

MapReduce框架的示意图

MapRedece 特点

优点: 使程序以并行的方式执行,可在短时间内完成大量工作。
缺点: 算法必须经过重写,需要对系统工程有一定的理解。
适用数据类型: 数值型和标称型数据。

Hadoop 流(Python 调用)

理论简介

例如: Hadoop流可以像Linux命令一样执行

cat inputFile.txt | python mapper.py | sort | python reducer.py > outputFile.txt

类似的Hadoop流就可以在多台机器上分布式执行,用户可以通过Linux命令来测试Python语言编写的MapReduce脚本。

实战脚本

测试 Mapper

Linux

cat input/15.BigData_MapReduce/inputFile.txt | python src/python/15.BigData_MapReduce/mrMeanMapper.py

Window

python src/python/15.BigData_MapReduce/mrMeanMapper.py < input/15.BigData_MapReduce/inputFile.txt

测试 Reducer

Linux

cat input/15.BigData_MapReduce/inputFile.txt | python src/python/15.BigData_MapReduce/mrMeanMapper.py | python src/python/15.BigData_MapReduce/mrMeanReducer.py

Window

python src/python/15.BigData_MapReduce/mrMeanMapper.py < input/15.BigData_MapReduce/inputFile.txt | python src/python/15.BigData_MapReduce/mrMeanReducer.py

MapReduce 机器学习
Mahout in Action

简单贝叶斯:它属于为数不多的可以很自然的使用MapReduce的算法。通过统计在某个类别下某特征的概率。
k-近邻算法:高维数据下(如文本、图像和视频)流行的近邻查找方法是局部敏感哈希算法。
支持向量机(SVM):使用随机梯度下降算法求解,如Pegasos算法。
奇异值分解:Lanczos算法是一个有效的求解近似特征值的算法。
k-均值聚类:canopy算法初始化k个簇,然后再运行K-均值求解结果。

使用 mrjob 库将 MapReduce 自动化

理论简介

MapReduce 作业流自动化的框架:Cascading 和 Oozie.
mrjob 是一个不错的学习工具,与2010年底实现了开源,来之于 Yelp(一个餐厅点评网站).

python src/python/15.BigData_MapReduce/mrMean.py < input/15.BigData_MapReduce/inputFile.txt > input/15.BigData_MapReduce/myOut.txt

实战脚本

测试 mrjob的案例

先测试一下mapper方法

python src/python/15.BigData_MapReduce/mrMean.py –mapper < input/15.BigData_MapReduce/inputFile.txt

运行整个程序,移除 –mapper 就行

python src/python/15.BigData_MapReduce/mrMean.py < input/15.BigData_MapReduce/inputFile.txt

项目案例:分布式 SVM 的 Pegasos 算法

Pegasos是指原始估计梯度求解器(Peimal Estimated sub-GrAdient Solver)
Pegasos 工作原理

从训练集中随机挑选一些样本点添加到待处理列表中
按序判断每个样本点是否被正确分类
    如果是则忽略
    如果不是则将其加入到待更新集合。
批处理完毕后,权重向量按照这些错分的样本进行更新。

上述算法伪代码如下:

将 回归系数w 初始化为0
对每次批处理
随机选择 k 个样本点(向量)
对每个向量
如果该向量被错分:
更新权重向量 w
累加对 w 的更新

开发流程

收集数据:数据按文本格式存放。
准备数据:输入数据已经是可用的格式,所以不需任何准备工作。如果你需要解析一个大规模的数据集,建议使用 map 作业来完成,从而达到并行处理的目的。
分析数据:无。
训练算法:与普通的 SVM 一样,在分类器训练上仍需花费大量的时间。
测试算法:在二维空间上可视化之后,观察超平面,判断算法是否有效。
使用算法:本例不会展示一个完整的应用,但会展示如何在大数据集上训练SVM。该算法其中一个应用场景就是本文分类,通常在文本分类里可能有大量的文档和成千上万的特征。

收集数据

文本文件数据格式如下:

0.365032 2.465645 -1
-2.494175 -0.292380 -1
-3.039364 -0.123108 -1
1.348150 0.255696 1
2.768494 1.234954 1
1.232328 -0.601198 1

准备数据

def loadDataSet(fileName):
dataMat = []
labelMat = []
fr = open(fileName)
for line in fr.readlines():
lineArr = line.strip().split(‘\t’)
# dataMat.append([float(lineArr[0]), float(lineArr[1]), float(lineArr[2])])
dataMat.append([float(lineArr[0]), float(lineArr[1])])
labelMat.append(float(lineArr[2]))
return dataMat, labelMat

分析数据: 无

训练算法

def batchPegasos(dataSet, labels, lam, T, k):
“””batchPegasos()

Args:
    dataMat    特征集合
    labels     分类结果集合
    lam        固定值
    T          迭代次数
    k          待处理列表大小
Returns:
    w          回归系数
"""
m, n = shape(dataSet)
w = zeros(n)  # 回归系数
dataIndex = range(m)
for t in range(1, T+1):
    wDelta = mat(zeros(n))  # 重置 wDelta

    # 它是学习率,代表了权重调整幅度的大小。(也可以理解为随机梯度的步长,使它不断减小,便于拟合)
    # 输入T和K分别设定了迭代次数和待处理列表的大小。在T次迭代过程中,每次需要重新计算eta
    eta = 1.0/(lam*t)
    random.shuffle(dataIndex)
    for j in range(k):      # 全部的训练集  内循环中执行批处理,将分类错误的值全部做累加后更新权重向量
        i = dataIndex[j]
        p = predict(w, dataSet[i, :])              # mapper 代码

        # 如果预测正确,并且预测结果的绝对值>=1,因为最大间隔为1, 认为没问题。
        # 否则算是预测错误, 通过预测错误的结果,来累计更新w.
        if labels[i]*p < 1:                        # mapper 代码
            wDelta += labels[i]*dataSet[i, :].A    # 累积变化
    # w通过不断的随机梯度的方式来优化
    w = (1.0 - 1/t)*w + (eta/k)*wDelta             # 在每个 T上应用更改
    # print '-----', w
# print '++++++', w
return w

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/15.BigData_MapReduce/pegasos.py

运行方式:python /opt/git/MachineLearning/src/python/15.BigData_MapReduce/mrSVM.py < input/15.BigData_MapReduce/inputFile.txt MR版本的代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/15.BigData_MapReduce/mrSVM.py

第14章 利用SVD简化数据

SVD 概述

奇异值分解(SVD, Singular Value Decomposition):
提取信息的一种方法,可以把 SVD 看成是从噪声数据中抽取相关特征。从生物信息学到金融学,SVD 是提取信息的强大工具。

SVD 场景

信息检索-隐性语义检索(Lstent Semantic Indexing, LSI)或 隐形语义分析(Latent Semantic Analysis, LSA)

隐性语义索引:矩阵 = 文档 + 词语

是最早的 SVD 应用之一,我们称利用 SVD 的方法为隐性语义索引(LSI)或隐性语义分析(LSA)。

LSA举例

推荐系统

利用 SVD 从数据中构建一个主题空间。
再在该空间下计算其相似度。(从高维-低维空间的转化,在低维空间来计算相似度,SVD 提升了推荐系统的效率。)

主题空间案例1

上图右边标注的为一组共同特征,表示美式 BBQ 空间;另一组在上图右边未标注的为日式食品 空间。

图像压缩

例如:3232=1024 => 322+21+322=130(2*1表示去掉了除对角线的0), 几乎获得了10倍的压缩比。

SVD公式
SVD 原理
SVD 工作原理

矩阵分解

矩阵分解是将数据矩阵分解为多个独立部分的过程。
矩阵分解可以将原始矩阵表示成新的易于处理的形式,这种新形式是两个或多个矩阵的乘积。(类似代数中的因数分解)
举例:如何将12分解成两个数的乘积?(1,12)、(2,6)、(3,4)都是合理的答案。

SVD 是矩阵分解的一种类型,也是矩阵分解最常见的技术

SVD 将原始的数据集矩阵 Data 分解成三个矩阵 U、∑、V
举例:如果原始矩阵 \(Data_{m*n}\) 是m行n列,
    \(U_{m * k}\) 表示m行k列
    \(∑_{k * k}\) 表示k行k列
    \(V_{k * n}\) 表示k行n列。

(Data_{mn} = U_{m\k} * ∑{k*k} * V{k*n})

SVD公式

具体的案例:(大家可以试着推导一下:https://wenku.baidu.com/view/b7641217866fb84ae45c8d17.html )

SVD公式

上述分解中会构建出一个矩阵∑,该矩阵只有对角元素,其他元素均为0(近似于0)。另一个惯例就是,∑的对角元素是从大到小排列的。这些对角元素称为奇异值。
奇异值与特征值(PCA 数据中重要特征)是有关系的。这里的奇异值就是矩阵 \(Data * Data^T\) 特征值的平方根。
普遍的事实:在某个奇异值的数目(r 个=>奇异值的平方和累加到总值的90%以上)之后,其他的奇异值都置为0(近似于0)。这意味着数据集中仅有 r 个重要特征,而其余特征则都是噪声或冗余特征。

SVD 算法特点

优点:简化数据,去除噪声,优化算法的结果
缺点:数据的转换可能难以理解
使用的数据类型:数值型数据

推荐系统
推荐系统 概述

推荐系统是利用电子商务网站向客户提供商品信息和建议,帮助用户决定应该购买什么产品,模拟销售人员帮助客户完成购买过程。
推荐系统 场景

Amazon 会根据顾客的购买历史向他们推荐物品
Netflix 会向其用户推荐电影
新闻网站会对用户推荐新闻频道

推荐系统 要点

基于协同过滤(collaborative filtering) 的推荐引擎

利用Python 实现 SVD(Numpy 有一个称为 linalg 的线性代数工具箱)
协同过滤:是通过将用户和其他用户的数据进行对比来实现推荐的。
当知道了两个用户或两个物品之间的相似度,我们就可以利用已有的数据来预测未知用户的喜好。

基于物品的相似度和基于用户的相似度:物品比较少则选择物品相似度,用户比较少则选择用户相似度。【矩阵还是小一点好计算】

基于物品的相似度:计算物品之间的距离。【耗时会随物品数量的增加而增加】
由于物品A和物品C 相似度(相关度)很高,所以给买A的人推荐C。

SVD公式

基于用户的相似度:计算用户之间的距离。【耗时会随用户数量的增加而增加】
由于用户A和用户C 相似度(相关度)很高,所以A和C是兴趣相投的人,对于C买的物品就会推荐给A。

SVD公式

相似度计算

inA, inB 对应的是 列向量
欧氏距离:指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。二维或三维中的欧氏距离就是两点之间的实际距离。
    相似度= 1/(1+欧式距离)
    相似度= 1.0/(1.0 + la.norm(inA - inB))
    物品对越相似,它们的相似度值就越大。
皮尔逊相关系数:度量的是两个向量之间的相似度。
    相似度= 0.5 + 0.5corrcoef() 【皮尔逊相关系数的取值范围从 -1 到 +1,通过函数0.5 + 0.5\corrcoef()这个函数计算,把值归一化到0到1之间】
    相似度= 0.5 + 0.5 * corrcoef(inA, inB, rowvar = 0)[0][1]
    相对欧氏距离的优势:它对用户评级的量级并不敏感。
余弦相似度:计算的是两个向量夹角的余弦值。
    余弦值 = (A·B)/(||A||·||B||) 【余弦值的取值范围也在-1到+1之间】
    相似度= 0.5 + 0.5*余弦值
    相似度= 0.5 + 0.5*( float(inA.T*inB) / la.norm(inA)*la.norm(inB))
    如果夹角为90度,则相似度为0;如果两个向量的方向相同,则相似度为1.0。

推荐系统的评价

采用交叉测试的方法。【拆分数据为训练集和测试集】
推荐引擎评价的指标: 最小均方根误差(Root mean squared error, RMSE),也称标准误差(Standard error),就是计算均方误差的平均值然后取其平方根。
    如果RMSE=1, 表示相差1个星级;如果RMSE=2.5, 表示相差2.5个星级。

推荐系统 原理

推荐系统的工作过程:给定一个用户,系统会为此用户返回N个最好的推荐菜。
实现流程大致如下:
    寻找用户没有评级的菜肴,即在用户-物品矩阵中的0值。
    在用户没有评级的所有物品中,对每个物品预计一个可能的评级分数。这就是说:我们认为用户可能会对物品的打分(这就是相似度计算的初衷)。
    对这些物品的评分从高到低进行排序,返回前N个物品。

项目案例: 餐馆菜肴推荐系统
项目概述

假如一个人在家决定外出吃饭,但是他并不知道该到哪儿去吃饭,该点什么菜。推荐系统可以帮他做到这两点。
开发流程

收集 并 准备数据

SVD 矩阵

def loadExData3():
# 利用SVD提高推荐效果,菜肴矩阵
“””
行:代表人
列:代表菜肴名词
值:代表人对菜肴的评分,0表示未评分
“””
return[[2, 0, 0, 4, 4, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0],
[3, 3, 4, 0, 3, 0, 0, 2, 2, 0, 0],
[5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],
[4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5],
[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4],
[0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],
[0, 0, 0, 3, 0, 0, 0, 0, 4, 5, 0],
[1, 1, 2, 1, 1, 2, 1, 0, 4, 5, 0]]

分析数据: 这里不做过多的讨论(当然此处可以对比不同距离之间的差别)

训练算法: 通过调用 recommend() 函数进行推荐

recommend() 会调用 基于物品相似度 或者是 基于SVD,得到推荐的物品评分。

1.基于物品相似度

基于物品相似度

欧式距离的计算方式

基于物品相似度的推荐引擎

def standEst(dataMat, user, simMeas, item):
“””standEst(计算某用户未评分物品中,以对该物品和其他物品评分的用户的物品相似度,然后进行综合评分)

Args:
    dataMat         训练数据集
    user            用户编号
    simMeas         相似度计算方法
    item            未评分的物品编号
Returns:
    ratSimTotal/simTotal     评分(0~5之间的值)
"""
# 得到数据集中的物品数目
n = shape(dataMat)[1]
# 初始化两个评分值
simTotal = 0.0
ratSimTotal = 0.0
# 遍历行中的每个物品(对用户评过分的物品进行遍历,并将它与其他物品进行比较)
for j in range(n):
    userRating = dataMat[user, j]
    # 如果某个物品的评分值为0,则跳过这个物品
    if userRating == 0:
        continue
    # 寻找两个用户都评级的物品
    # 变量 overLap 给出的是两个物品当中已经被评分的那个元素的索引ID
    # logical_and 计算x1和x2元素的真值。
    overLap = nonzero(logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[0]
    # 如果相似度为0,则两着没有任何重合元素,终止本次循环
    if len(overLap) == 0:
        similarity = 0
    # 如果存在重合的物品,则基于这些重合物重新计算相似度。
    else:
        similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])
    # print 'the %d and %d similarity is : %f'(iten,j,similarity)
    # 相似度会不断累加,每次计算时还考虑相似度和当前用户评分的乘积
    # similarity  用户相似度,   userRating 用户评分
    simTotal += similarity
    ratSimTotal += similarity * userRating
if simTotal == 0:
    return 0
# 通过除以所有的评分总和,对上述相似度评分的乘积进行归一化,使得最后评分在0~5之间,这些评分用来对预测值进行排序
else:
    return ratSimTotal/simTotal

2.基于SVD(参考地址:http://www.codeweblog.com/svd-%E7%AC%94%E8%AE%B0/)

基于SVD.png

基于SVD的评分估计

在recommend() 中,这个函数用于替换对standEst()的调用,该函数对给定用户给定物品构建了一个评分估计值

def svdEst(dataMat, user, simMeas, item):
“””svdEst(计算某用户未评分物品中,以对该物品和其他物品评分的用户的物品相似度,然后进行综合评分)

Args:
    dataMat         训练数据集
    user            用户编号
    simMeas         相似度计算方法
    item            未评分的物品编号
Returns:
    ratSimTotal/simTotal     评分(0~5之间的值)
"""
# 物品数目
n = shape(dataMat)[1]
# 对数据集进行SVD分解
simTotal = 0.0
ratSimTotal = 0.0
# 奇异值分解
# 在SVD分解之后,我们只利用包含了90%能量值的奇异值,这些奇异值会以NumPy数组的形式得以保存
U, Sigma, VT = la.svd(dataMat)

# # 分析 Sigma 的长度取值
# analyse_data(Sigma, 20)

# 如果要进行矩阵运算,就必须要用这些奇异值构建出一个对角矩阵
Sig4 = mat(eye(4) * Sigma[: 4])
# 利用U矩阵将物品转换到低维空间中,构建转换后的物品(物品+4个主要的特征)
xformedItems = dataMat.T * U[:, :4] * Sig4.I
# 对于给定的用户,for循环在用户对应行的元素上进行遍历,
# 这和standEst()函数中的for循环的目的一样,只不过这里的相似度计算时在低维空间下进行的。
for j in range(n):
    userRating = dataMat[user, j]
    if userRating == 0 or j == item:
        continue
    # 相似度的计算方法也会作为一个参数传递给该函数
    similarity = simMeas(xformedItems[item, :].T, xformedItems[j, :].T)
    # for 循环中加入了一条print语句,以便了解相似度计算的进展情况。如果觉得累赘,可以去掉
    print 'the %d and %d similarity is: %f' % (item, j, similarity)
    # 对相似度不断累加求和
    simTotal += similarity
    # 对相似度及对应评分值的乘积求和
    ratSimTotal += similarity * userRating
if simTotal == 0:
    return 0
else:
    # 计算估计评分
    return ratSimTotal/simTotal

排序获取最后的推荐结果

recommend()函数,就是推荐引擎,它默认调用standEst()函数,产生了最高的N个推荐结果。

如果不指定N的大小,则默认值为3。该函数另外的参数还包括相似度计算方法和估计方法

def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst):
# 寻找未评级的物品
# 对给定的用户建立一个未评分的物品列表
unratedItems = nonzero(dataMat[user, :].A == 0)[1]
# 如果不存在未评分物品,那么就退出函数
if len(unratedItems) == 0:
return ‘you rated everything’
# 物品的编号和评分值
itemScores = []
# 在未评分物品上进行循环
for item in unratedItems:
estimatedScore = estMethod(dataMat, user, simMeas, item)
# 寻找前N个未评级物品,调用standEst()来产生该物品的预测得分,该物品的编号和估计值会放在一个元素列表itemScores中
itemScores.append((item, estimatedScore))
# 按照估计得分,对该列表进行排序并返回。列表逆排序,第一个值就是最大值
return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[: N]

测试 和 项目调用,可直接参考我们的代码

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/14.SVD/svdRecommend.py
要点补充

基于内容(content-based)的推荐

通过各种标签来标记菜肴
将这些属性作为相似度计算所需要的数据
这就是:基于内容的推荐。

构建推荐引擎面临的挑战

问题

1)在大规模的数据集上,SVD分解会降低程序的速度
2)存在其他很多规模扩展性的挑战性问题,比如矩阵的表示方法和计算相似度得分消耗资源。
3)如何在缺乏数据时给出好的推荐-称为冷启动【简单说:用户不会喜欢一个无效的物品,而用户不喜欢的物品又无效】

建议

1)在大型系统中,SVD分解(可以在程序调入时运行一次)每天运行一次或者其频率更低,并且还要离线运行。
2)在实际中,另一个普遍的做法就是离线计算并保存相似度得分。(物品相似度可能被用户重复的调用)
3)冷启动问题,解决方案就是将推荐看成是搜索问题,通过各种标签/属性特征进行基于内容的推荐。

项目案例: 基于 SVD 的图像压缩

收集 并 准备数据

将文本数据转化为矩阵

加载并转换数据

def imgLoadData(filename):
myl = []
# 打开文本文件,并从文件以数组方式读入字符
for line in open(filename).readlines():
newRow = []
for i in range(32):
newRow.append(int(line[i]))
myl.append(newRow)
# 矩阵调入后,就可以在屏幕上输出该矩阵
myMat = mat(myl)
return myMat

分析数据: 分析 Sigma 的长度个数

通常保留矩阵 80% ~ 90% 的能量,就可以得到重要的特征并去除噪声。

def analyse_data(Sigma, loopNum=20):
“””analyse_data(分析 Sigma 的长度取值)

Args:
    Sigma         Sigma的值
    loopNum       循环次数
"""
# 总方差的集合(总能量值)
Sig2 = Sigma**2
SigmaSum = sum(Sig2)
for i in range(loopNum):
    SigmaI = sum(Sig2[:i+1])
    '''
    根据自己的业务情况,就行处理,设置对应的 Singma 次数

    通常保留矩阵 80% ~ 90% 的能量,就可以得到重要的特征并取出噪声。
    '''
    print '主成分:%s, 方差占比:%s%%' % (format(i+1, '2.0f'), format(SigmaI/SigmaSum*100, '4.2f'))

使用算法: 对比使用 SVD 前后的数据差异对比,对于存储大家可以试着写写

例如:3232=1024 => 322+21+322=130(2*1表示去掉了除对角线的0), 几乎获得了10倍的压缩比。

打印矩阵

def printMat(inMat, thresh=0.8):
# 由于矩阵保护了浮点数,因此定义浅色和深色,遍历所有矩阵元素,当元素大于阀值时打印1,否则打印0
for i in range(32):
for k in range(32):
if float(inMat[i, k]) > thresh:
print 1,
else:
print 0,
print ”

实现图像压缩,允许基于任意给定的奇异值数目来重构图像

def imgCompress(numSV=3, thresh=0.8):
“””imgCompress( )

Args:
    numSV       Sigma长度   
    thresh      判断的阈值
"""
# 构建一个列表
myMat = imgLoadData('input/14.SVD/0_5.txt')

print "****original matrix****"
# 对原始图像进行SVD分解并重构图像e
printMat(myMat, thresh)

# 通过Sigma 重新构成SigRecom来实现
# Sigma是一个对角矩阵,因此需要建立一个全0矩阵,然后将前面的那些奇异值填充到对角线上。
U, Sigma, VT = la.svd(myMat)
# SigRecon = mat(zeros((numSV, numSV)))
# for k in range(numSV):
#     SigRecon[k, k] = Sigma[k]

# 分析插入的 Sigma 长度
analyse_data(Sigma, 20)

SigRecon = mat(eye(numSV) * Sigma[: numSV])
reconMat = U[:, :numSV] * SigRecon * VT[:numSV, :]
print "****reconstructed matrix using %d singular values *****" % numSV
printMat(reconMat, thresh)

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/14.SVD/svdRecommend.py

第13章 利用 PCA 来简化数据

降维技术

场景

我们正通过电视观看体育比赛,在电视的显示器上有一个球。
显示器大概包含了100万像素点,而球则可能是由较少的像素点组成,例如说一千个像素点。
人们实时的将显示器上的百万像素转换成为一个三维图像,该图像就给出运动场上球的位置。
在这个过程中,人们已经将百万像素点的数据,降至为三维。这个过程就称为降维(dimensionality reduction)

数据显示 并非大规模特征下的唯一难题,对数据进行简化还有如下一系列的原因:

1) 使得数据集更容易使用
2) 降低很多算法的计算开销
3) 去除噪音
4) 使得结果易懂

适用范围: 

在已标注与未标注的数据上都有降维技术。
这里我们将主要关注未标注数据上的降维技术,将技术同样也可以应用于已标注的数据。

在以下3种降维技术中, PCA的应用目前最为广泛,因此本章主要关注PCA。

1) 主成分分析(Principal Component Analysis, PCA)
    通俗理解:就是找出一个最主要的特征,然后进行分析。
    例如: 考察一个人的智力情况,就直接看数学成绩就行(存在:数学、语文、英语成绩)
2) 因子分析(Factor Analysis)
    通俗理解:将多个实测变量转换为少数几个综合指标。它反映一种降维的思想,通过降维将相关性高的变量聚在一起,从而减少需要分析的变量的数量,而减少问题分析的复杂性
    例如: 考察一个人的整体情况,就直接组合3样成绩(隐变量),看平均成绩就行(存在:数学、语文、英语成绩)
    应用的领域:社会科学、金融和其他领域
    在因子分析中,我们
        假设观察数据的成分中有一些观察不到的隐变量(latent variable)。
        假设观察数据是这些隐变量和某些噪音的线性组合。
        那么隐变量的数据可能比观察数据的数目少,也就说通过找到隐变量就可以实现数据的降维。
3) 独立成分分析(Independ Component Analysis, ICA)
    通俗理解:ICA 认为观测信号是若干个独立信号的线性组合,ICA 要做的是一个解混过程。
    例如:我们去ktv唱歌,想辨别唱的是什么歌曲?ICA 是观察发现是原唱唱的一首歌【2个独立的声音(原唱/主唱)】。
    ICA 是假设数据是从 N 个数据源混合组成的,这一点和因子分析有些类似,这些数据源之间在统计上是相互独立的,而在 PCA 中只假设数据是不 相关(线性关系)的。
    同因子分析一样,如果数据源的数目少于观察数据的数目,则可以实现降维过程。

PCA
PCA 概述

主成分分析(Principal Component Analysis, PCA):通俗理解:就是找出一个最主要的特征,然后进行分析。
PCA 场景

例如: 考察一个人的智力情况,就直接看数学成绩就行(存在:数学、语文、英语成绩)
PCA 原理

PCA 工作原理

找出第一个主成分的方向,也就是数据 方差最大 的方向。
找出第二个主成分的方向,也就是数据 方差次大 的方向,并且该方向与第一个主成分方向 正交(orthogonal 如果是二维空间就叫垂直)。
通过这种方式计算出所有的主成分方向。
通过数据集的协方差矩阵及其特征值分析,我们就可以得到这些主成分的值。
一旦得到了协方差矩阵的特征值和特征向量,我们就可以保留最大的 N 个特征。这些特征向量也给出了 N 个最重要特征的真实结构,我们就可以通过将数据乘上这 N 个特征向量 从而将它转换到新的空间上。

为什么正交?

正交是为了数据有效性损失最小
正交的一个原因是特征值的特征向量是正交的

例如下图:

应用PCA降维

PCA 优缺点

优点:降低数据的复杂性,识别最重要的多个特征。
缺点:不一定需要,且可能损失有用信息。
适用数据类型:数值型数据。

项目案例: 对半导体数据进行降维处理
项目概述

半导体是在一些极为先进的工厂中制造出来的。设备的生命早期有限,并且花费极其巨大。
虽然通过早期测试和频繁测试来发现有瑕疵的产品,但仍有一些存在瑕疵的产品通过测试。
如果我们通过机器学习技术用于发现瑕疵产品,那么它就会为制造商节省大量的资金。

具体来讲,它拥有590个特征。我们看看能否对这些特征进行降维处理。

对于数据的缺失值的问题,我们有一些处理方法(参考第5章)
目前该章节处理的方案是:将缺失值NaN(Not a Number缩写),全部用平均值来替代(如果用0来处理的策略就太差劲了)。

开发流程

收集数据:提供文本文件

文件名:secom.data

文本文件数据格式如下:

3030.93 2564 2187.7333 1411.1265 1.3602 100 97.6133 0.1242 1.5005 0.0162 -0.0034 0.9455 202.4396 0 7.9558 414.871 10.0433 0.968 192.3963 12.519 1.4026 -5419 2916.5 -4043.75 751 0.8955 1.773 3.049 64.2333 2.0222 0.1632 3.5191 83.3971 9.5126 50.617 64.2588 49.383 66.3141 86.9555 117.5132 61.29 4.515 70 352.7173 10.1841 130.3691 723.3092 1.3072 141.2282 1 624.3145 218.3174 0 4.592 4.841 2834 0.9317 0.9484 4.7057 -1.7264 350.9264 10.6231 108.6427 16.1445 21.7264 29.5367 693.7724 0.9226 148.6009 1 608.17 84.0793 NaN NaN 0 0.0126 -0.0206 0.0141 -0.0307 -0.0083 -0.0026 -0.0567 -0.0044 7.2163 0.132 NaN 2.3895 0.969 1747.6049 0.1841 8671.9301 -0.3274 -0.0055 -0.0001 0.0001 0.0003 -0.2786 0 0.3974 -0.0251 0.0002 0.0002 0.135 -0.0042 0.0003 0.0056 0 -0.2468 0.3196 NaN NaN NaN NaN 0.946 0 748.6115 0.9908 58.4306 0.6002 0.9804 6.3788 15.88 2.639 15.94 15.93 0.8656 3.353 0.4098 3.188 -0.0473 0.7243 0.996 2.2967 1000.7263 39.2373 123 111.3 75.2 46.2 350.671 0.3948 0 6.78 0.0034 0.0898 0.085 0.0358 0.0328 12.2566 0 4.271 10.284 0.4734 0.0167 11.8901 0.41 0.0506 NaN NaN 1017 967 1066 368 0.09 0.048 0.095 2 0.9 0.069 0.046 0.725 0.1139 0.3183 0.5888 0.3184 0.9499 0.3979 0.16 0 0 20.95 0.333 12.49 16.713 0.0803 5.72 0 11.19 65.363 0 0 0 0 0 0 0.292 5.38 20.1 0.296 10.62 10.3 5.38 4.04 16.23 0.2951 8.64 0 10.3 97.314 0 0.0772 0.0599 0.07 0.0547 0.0704 0.052 0.0301 0.1135 3.4789 0.001 NaN 0.0707 0.0211 175.2173 0.0315 1940.3994 0 0.0744 0.0546 0 0 0 0 0 0 0 0 0 0.0027 0.004 0 0 0 0 NaN NaN NaN NaN 0.0188 0 219.9453 0.0011 2.8374 0.0189 0.005 0.4269 0 0 0 0 0 0 0 0 0 0 0 0.0472 40.855 4.5152 30.9815 33.9606 22.9057 15.9525 110.2144 0.131 0 2.5883 0.001 0.0319 0.0197 0.012 0.0109 3.9321 0 1.5123 3.5811 0.1337 0.0055 3.8447 0.1077 0.0167 NaN NaN 418.1363 398.3185 496.1582 158.333 0.0373 0.0202 0.0462 0.6083 0.3032 0.02 0.0174 0.2827 0.0434 0.1342 0.2419 0.1343 0.367 0.1431 0.061 0 0 0 6.2698 0.1181 3.8208 5.3737 0.0254 1.6252 0 3.2461 18.0118 0 0 0 0 0 0 0.0752 1.5989 6.5893 0.0913 3.0911 8.4654 1.5989 1.2293 5.3406 0.0867 2.8551 0 2.9971 31.8843 NaN NaN 0 0.0215 0.0274 0.0315 0.0238 0.0206 0.0238 0.0144 0.0491 1.2708 0.0004 NaN 0.0229 0.0065 55.2039 0.0105 560.2658 0 0.017 0.0148 0.0124 0.0114 0 0 0 0 0 0 0 0.001 0.0013 0 0 0 0 NaN NaN NaN NaN 0.0055 0 61.5932 0.0003 0.9967 0.0082 0.0017 0.1437 0 0 0 0 0 0 0 0 0 0 0 0.0151 14.2396 1.4392 5.6188 3.6721 2.9329 2.1118 24.8504 29.0271 0 6.9458 2.738 5.9846 525.0965 0 3.4641 6.0544 0 53.684 2.4788 4.7141 1.7275 6.18 3.275 3.6084 18.7673 33.1562 26.3617 49.0013 10.0503 2.7073 3.1158 3.1136 44.5055 42.2737 1.3071 0.8693 1.1975 0.6288 0.9163 0.6448 1.4324 0.4576 0.1362 0 0 0 5.9396 3.2698 9.5805 2.3106 6.1463 4.0502 0 1.7924 29.9394 0 0 0 0 0 0 6.2052 311.6377 5.7277 2.7864 9.7752 63.7987 24.7625 13.6778 2.3394 31.9893 5.8142 0 1.6936 115.7408 0 613.3069 291.4842 494.6996 178.1759 843.1138 0 53.1098 0 48.2091 0.7578 NaN 2.957 2.1739 10.0261 17.1202 22.3756 0 0 0 0 0 0 0 0 0 0 0 0 64.6707 0 0 0 0 0 NaN NaN NaN NaN 1.9864 0 29.3804 0.1094 4.856 3.1406 0.5064 6.6926 0 0 0 0 0 0 0 0 0 0 0 2.057 4.0825 11.5074 0.1096 0.0078 0.0026 7.116 1.0616 395.57 75.752 0.4234 12.93 0.78 0.1827 5.7349 0.3363 39.8842 3.2687 1.0297 1.0344 0.4385 0.1039 42.3877 NaN NaN NaN NaN NaN NaN NaN NaN 533.85 2.1113 8.95 0.3157 3.0624 0.1026 1.6765 14.9509 NaN NaN NaN NaN 0.5005 0.0118 0.0035 2.363 NaN NaN NaN NaN
3095.78 2465.14 2230.4222 1463.6606 0.8294 100 102.3433 0.1247 1.4966 -0.0005 -0.0148 0.9627 200.547 0 10.1548 414.7347 9.2599 0.9701 191.2872 12.4608 1.3825 -5441.5 2604.25 -3498.75 -1640.25 1.2973 2.0143 7.39 68.4222 2.2667 0.2102 3.4171 84.9052 9.7997 50.6596 64.2828 49.3404 64.9193 87.5241 118.1188 78.25 2.773 70 352.2445 10.0373 133.1727 724.8264 1.2887 145.8445 1 631.2618 205.1695 0 4.59 4.842 2853 0.9324 0.9479 4.682 0.8073 352.0073 10.3092 113.98 10.9036 19.1927 27.6301 697.1964 1.1598 154.3709 1 620.3582 82.3494 NaN NaN 0 -0.0039 -0.0198 0.0004 -0.044 -0.0358 -0.012 -0.0377 0.0017 6.8043 0.1358 NaN 2.3754 0.9894 1931.6464 0.1874 8407.0299 0.1455 -0.0015 0 -0.0005 0.0001 0.5854 0 -0.9353 -0.0158 -0.0004 -0.0004 -0.0752 -0.0045 0.0002 0.0015 0 0.0772 -0.0903 NaN NaN NaN NaN 0.9425 0 731.2517 0.9902 58.668 0.5958 0.9731 6.5061 15.88 2.541 15.91 15.88 0.8703 2.771 0.4138 3.272 -0.0946 0.8122 0.9985 2.2932 998.1081 37.9213 98 80.3 81 56.2 219.7679 0.2301 0 5.7 0.0049 0.1356 0.06 0.0547 0.0204 12.3319 0 6.285 13.077 0.5666 0.0144 11.8428 0.35 0.0437 NaN NaN 568 59 297 3277 0.112 0.115 0.124 2.2 1.1 0.079 0.561 1.0498 0.1917 0.4115 0.6582 0.4115 1.0181 0.2315 0.325 0 0 17.99 0.439 10.14 16.358 0.0892 6.92 0 9.05 82.986 0 0 0 0 0 0 0.222 3.74 19.59 0.316 11.65 8.02 3.74 3.659 15.078 0.358 8.96 0 8.02 134.25 0 0.0566 0.0488 0.1651 0.1578 0.0468 0.0987 0.0734 0.0747 3.9578 0.005 NaN 0.0761 0.0014 128.4285 0.0238 1988 0 0.0203 0.0236 0 0 0 0 0 0 0 0 0 0.0064 0.0036 0 0 0 0 NaN NaN NaN NaN 0.0154 0 193.0287 0.0007 3.8999 0.0187 0.0086 0.5749 0 0 0 0 0 0 0 0 0 0 0 0.0411 29.743 3.6327 29.0598 28.9862 22.3163 17.4008 83.5542 0.0767 0 1.8459 0.0012 0.044 0.0171 0.0154 0.0069 3.9011 0 2.1016 3.9483 0.1662 0.0049 3.7836 0.1 0.0139 NaN NaN 233.9865 26.5879 139.2082 1529.7622 0.0502 0.0561 0.0591 0.8151 0.3464 0.0291 0.1822 0.3814 0.0715 0.1667 0.263 0.1667 0.3752 0.0856 0.1214 0 0 0 5.6522 0.1417 2.9939 5.2445 0.0264 1.8045 0 2.7661 23.623 0 0 0 0 0 0 0.0778 1.1506 5.9247 0.0878 3.3604 7.7421 1.1506 1.1265 5.0108 0.1013 2.4278 0 2.489 41.708 NaN NaN 0 0.0142 0.023 0.0768 0.0729 0.0143 0.0513 0.0399 0.0365 1.2474 0.0017 NaN 0.0248 0.0005 46.3453 0.0069 677.1873 0 0.0053 0.0059 0.0081 0.0033 0 0 0 0 0 0 0 0.0022 0.0013 0 0 0 0 NaN NaN NaN NaN 0.0049 0 65.0999 0.0002 1.1655 0.0068 0.0027 0.1921 0 0 0 0 0 0 0 0 0 0 0 0.012 10.5837 1.0323 4.3465 2.5939 3.2858 2.5197 15.015 27.7464 0 5.5695 3.93 9.0604 0 368.9713 2.1196 6.1491 0 61.8918 3.1531 6.1188 1.4857 6.1911 2.8088 3.1595 10.4383 2.2655 8.4887 199.7866 8.6336 5.7093 1.6779 3.2153 48.5294 37.5793 16.4174 1.2364 1.9562 0.8123 1.0239 0.834 1.5683 0.2645 0.2751 0 0 0 5.1072 4.3737 7.6142 2.2568 6.9233 4.7448 0 1.4336 40.4475 0 0 0 0 0 0 4.7415 463.2883 5.5652 3.0652 10.2211 73.5536 19.4865 13.243 2.1627 30.8643 5.8042 0 1.2928 163.0249 0 0 246.7762 0 359.0444 130.635 820.79 194.4371 0 58.1666 3.6822 NaN 3.2029 0.1441 6.6487 12.6788 23.6469 0 0 0 0 0 0 0 0 0 0 0 0 141.4365 0 0 0 0 0 NaN NaN NaN NaN 1.6292 0 26.397 0.0673 6.6475 3.131 0.8832 8.837 0 0 0 0 0 0 0 0 0 0 0 1.791 2.9799 9.5796 0.1096 0.0078 0.0026 7.116 1.3526 408.798 74.64 0.7193 16 1.33 0.2829 7.1196 0.4989 53.1836 3.9139 1.7819 0.9634 0.1745 0.0375 18.1087 NaN NaN NaN NaN NaN NaN NaN NaN 535.0164 2.4335 5.92 0.2653 2.0111 0.0772 1.1065 10.9003 0.0096 0.0201 0.006 208.2045 0.5019 0.0223 0.0055 4.4447 0.0096 0.0201 0.006 208.2045
2932.61 2559.94 2186.4111 1698.0172 1.5102 100 95.4878 0.1241 1.4436 0.0041 0.0013 0.9615 202.0179 0 9.5157 416.7075 9.3144 0.9674 192.7035 12.5404 1.4123 -5447.75 2701.75 -4047 -1916.5 1.3122 2.0295 7.5788 67.1333 2.3333 0.1734 3.5986 84.7569 8.659 50.153 64.1114 49.847 65.8389 84.7327 118.6128 14.37 5.434 70 364.3782 9.8783 131.8027 734.7924 1.2992 141.0845 1 637.2655 185.7574 0 4.486 4.748 2936 0.9139 0.9447 4.5873 23.8245 364.5364 10.1685 115.6273 11.3019 16.1755 24.2829 710.5095 0.8694 145.8 1 625.9636 84.7681 140.6972 485.2665 0 -0.0078 -0.0326 -0.0052 0.0213 -0.0054 -0.1134 -0.0182 0.0287 7.1041 0.1362 NaN 2.4532 0.988 1685.8514 0.1497 9317.1698 0.0553 0.0006 -0.0013 0 0.0002 -0.1343 0 -0.1427 0.1218 0.0006 -0.0001 0.0134 -0.0026 -0.0016 -0.0006 0.0013 -0.0301 -0.0728 NaN NaN NaN 0.4684 0.9231 0 718.5777 0.9899 58.4808 0.6015 0.9772 6.4527 15.9 2.882 15.94 15.95 0.8798 3.094 0.4777 3.272 -0.1892 0.8194 0.9978 2.2592 998.444 42.0579 89 126.4 96.5 45.1001 306.038 0.3263 0 8.33 0.0038 0.0754 0.0483 0.0619 0.0221 8.266 0 4.819 8.443 0.4909 0.0177 8.2054 0.47 0.0497 NaN NaN 562 788 759 2100 0.187 0.117 0.068 2.1 1.4 0.123 0.319 1.0824 0.0369 0.3141 0.5753 0.3141 0.9677 0.2706 0.326 0 0 17.78 0.745 13.31 22.912 0.1959 9.21 0 17.87 60.11 0 0 0 0 0 0 0.139 5.09 19.75 0.949 9.71 16.73 5.09 11.059 22.624 0.1164 13.3 0 16.73 79.618 0 0.0339 0.0494 0.0696 0.0406 0.0401 0.084 0.0349 0.0718 2.4266 0.0014 NaN 0.0963 0.0152 182.4956 0.0284 839.6006 0 0.0192 0.017 0 0 0 0 0 0 0 0 0 0.0062 0.004 0 0 0 0 NaN NaN NaN 0.1729 0.0273 0 104.4042 0.0007 4.1446 0.0733 0.0063 0.4166 0 0 0 0 0 0 0 0 0 0 0 0.0487 29.621 3.9133 23.551 41.3837 32.6256 15.7716 97.3868 0.1117 0 2.5274 0.0012 0.0249 0.0152 0.0157 0.0075 2.8705 0 1.5306 2.5493 0.1479 0.0059 2.8046 0.1185 0.0167 NaN NaN 251.4536 329.6406 325.0672 902.4576 0.08 0.0583 0.0326 0.6964 0.4031 0.0416 0.1041 0.3846 0.0151 0.1288 0.2268 0.1288 0.3677 0.1175 0.1261 0 0 0 5.7247 0.2682 3.8541 6.1797 0.0546 2.568 0 4.6067 16.0104 0 0 0 0 0 0 0.0243 1.5481 5.9453 0.2777 3.16 8.9855 1.5481 2.9844 6.2277 0.0353 3.7663 0 5.6983 24.7959 13.5664 15.4488 0 0.0105 0.0208 0.0327 0.0171 0.0116 0.0428 0.0154 0.0383 0.7786 0.0005 NaN 0.0302 0.0046 58.0575 0.0092 283.6616 0 0.0054 0.0043 0.003 0.0037 0 0 0 0 0 0 0 0.0021 0.0015 0 0 0 0 NaN NaN NaN 0.0221 0.01 0 28.7334 0.0003 1.2356 0.019 0.002 0.1375 0 0 0 0 0 0 0 0 0 0 0 0.019 11.4871 1.1798 4.0782 4.3102 3.7696 2.0627 18.0233 21.6062 0 8.7236 3.0609 5.2231 0 0 2.2943 4.0917 0 50.6425 2.0261 5.2707 1.8268 4.2581 3.7479 3.522 10.3162 29.1663 18.7546 109.5747 14.2503 5.765 0.8972 3.1281 60 70.9161 8.8647 1.2771 0.4264 0.6263 0.8973 0.6301 1.4698 0.3194 0.2748 0 0 0 4.8795 7.5418 10.0984 3.1182 15.079 6.528 0 2.8042 32.3594 0 0 0 0 0 0 3.0301 21.3645 5.4178 9.3327 8.3977 148.0287 31.4674 45.5423 3.1842 13.3923 9.1221 0 2.6727 93.9245 0 434.2674 151.7665 0 190.3869 746.915 74.0741 191.7582 250.1742 34.1573 1.0281 NaN 3.9238 1.5357 10.8251 18.9849 9.0113 0 0 0 0 0 0 0 0 0 0 0 0 240.7767 244.2748 0 0 0 0 NaN NaN NaN 36.9067 2.9626 0 14.5293 0.0751 7.087 12.1831 0.6451 6.4568 0 0 0 0 0 0 0 0 0 0 0 2.1538 2.9667 9.3046 0.1096 0.0078 0.0026 7.116 0.7942 411.136 74.654 0.1832 16.16 0.85 0.0857 7.1619 0.3752 23.0713 3.9306 1.1386 1.5021 0.3718 0.1233 24.7524 267.064 0.9032 1.1 0.6219 0.4122 0.2562 0.4119 68.8489 535.0245 2.0293 11.21 0.1882 4.0923 0.064 2.0952 9.2721 0.0584 0.0484 0.0148 82.8602 0.4958 0.0157 0.0039 3.1745 0.0584 0.0484 0.0148 82.8602
2988.72 2479.9 2199.0333 909.7926 1.3204 100 104.2367 0.1217 1.4882 -0.0124 -0.0033 0.9629 201.8482 0 9.6052 422.2894 9.6924 0.9687 192.1557 12.4782 1.4011 -5468.25 2648.25 -4515 -1657.25 1.3137 2.0038 7.3145 62.9333 2.6444 0.2071 3.3813 84.9105 8.6789 50.51 64.1125 49.49 65.1951 86.6867 117.0442 76.9 1.279 70 363.0273 9.9305 131.8027 733.8778 1.3027 142.5427 1 637.3727 189.9079 0 4.486 4.748 2936 0.9139 0.9447 4.5873 24.3791 361.4582 10.2112 116.1818 13.5597 15.6209 23.4736 710.4043 0.9761 147.6545 1 625.2945 70.2289 160.321 464.9735 0 -0.0555 -0.0461 -0.04 0.04 0.0676 -0.1051 0.0028 0.0277 7.5925 0.1302 NaN 2.4004 0.9904 1752.0968 0.1958 8205.7 0.0697 -0.0003 -0.0021 -0.0001 0.0002 0.0411 0 0.0177 -0.0195 -0.0002 0 -0.0699 -0.0059 0.0003 0.0003 0.0021 -0.0483 -0.118 NaN NaN NaN 0.4647 0.9564 0 709.0867 0.9906 58.6635 0.6016 0.9761 6.4935 15.55 3.132 15.61 15.59 1.366 2.48 0.5176 3.119 0.2838 0.7244 0.9961 2.3802 980.451 41.1025 127 118 123.7 47.8 162.432 0.1915 0 5.51 0.003 0.114 0.0393 0.0613 0.019 13.2651 0 9.073 15.241 1.3029 0.015 11.9738 0.35 0.0699 NaN NaN 859 355 3433 3004 0.068 0.108 0.1 1.7 0.9 0.086 0.241 0.9386 0.0356 0.2618 0.4391 0.2618 0.8567 0.2452 0.39 0 0 16.22 0.693 14.67 22.562 0.1786 5.69 0 18.2 52.571 0 0 0 0 0 0 0.139 5.92 23.6 1.264 10.63 13.56 5.92 11.382 24.32 0.3458 9.56 0 21.97 104.95 0 0.1248 0.0463 0.1223 0.0354 0.0708 0.0754 0.0643 0.0932 5.5398 0.0023 NaN 0.0764 0.0015 152.0885 0.0573 820.3999 0 0.0152 0.0149 0 0 0 0 0 0 0 0 0 0.0067 0.004 0 0 0 0 NaN NaN NaN 0.0191 0.0234 0 94.0954 0.001 3.2119 0.0406 0.0072 0.4212 0 0 0 0 0 0 0 0 0 0 0 0.0513 31.83 3.1959 33.896 37.8477 44.3906 16.9347 50.3631 0.0581 0 2.1775 0.0007 0.0417 0.0115 0.0172 0.0063 4.2154 0 2.896 4.0526 0.3882 0.0049 3.9403 0.0916 0.0245 NaN NaN 415.5048 157.0889 1572.6896 1377.4276 0.0285 0.0445 0.0465 0.6305 0.3046 0.0286 0.0824 0.3483 0.0128 0.1004 0.1701 0.1004 0.3465 0.0973 0.1675 0 0 0 5.444 0.2004 4.19 6.3329 0.0479 1.7339 0 4.966 15.7375 0 0 0 0 0 0 0.0243 1.7317 6.6262 0.3512 3.2699 9.402 1.7317 3.0672 6.6839 0.0928 3.0229 0 6.3292 29.0339 8.4026 4.8851 0 0.0407 0.0198 0.0531 0.0167 0.0224 0.0422 0.0273 0.0484 1.8222 0.0006 NaN 0.0252 0.0004 45.7058 0.0188 309.8492 0 0.0046 0.0049 0.0028 0.0034 0 0 0 0 0 0 0 0.0024 0.0014 0 0 0 0 NaN NaN NaN 0.0038 0.0068 0 32.4228 0.0003 1.1135 0.0132 0.0023 0.1348 0 0 0 0 0 0 0 0 0 0 0 0.0155 13.3972 1.1907 5.6363 3.9482 4.9881 2.1737 17.8537 14.5054 0 5.286 2.4643 7.6602 317.7362 0 1.9689 6.5718 0 94.4594 3.6091 13.442 1.5441 6.2313 2.8049 4.9898 15.7089 13.4051 76.0354 181.2641 5.176 5.3899 1.3671 2.7013 34.0336 41.5236 7.1274 1.1054 0.4097 0.5183 0.6849 0.529 1.3141 0.2829 0.3332 0 0 0 4.468 6.9785 11.1303 3.0744 13.7105 3.9918 0 2.8555 27.6824 0 0 0 0 0 0 3.0301 24.2831 6.5291 12.3786 9.1494 100.0021 37.8979 48.4887 3.4234 35.4323 6.4746 0 3.5135 149.4399 0 225.0169 100.4883 305.75 88.5553 104.666 71.7583 0 336.766 72.9635 1.767 NaN 3.1817 0.1488 8.6804 29.2542 9.9979 0 0 711.6418 0 0 0 0 0 0 0 0 0 113.5593 0 0 0 0 0 NaN NaN NaN 4.12 2.4416 0 13.2699 0.0977 5.4751 6.7553 0.7404 6.4865 0 0 0 0 0 0 0 0 0 0 0 2.1565 3.2465 7.7754 0.1096 0.0078 0.0026 7.116 1.165 372.822 72.442 1.8804 131.68 39.33 0.6812 56.9303 17.4781 161.4081 35.3198 54.2917 1.1613 0.7288 0.271 62.7572 268.228 0.6511 7.32 0.163 3.5611 0.067 2.729 25.0363 530.5682 2.0253 9.33 0.1738 2.8971 0.0525 1.7585 8.5831 0.0202 0.0149 0.0044 73.8432 0.499 0.0103 0.0025 2.0544 0.0202 0.0149 0.0044 73.8432
3032.24 2502.87 2233.3667 1326.52 1.5334 100 100.3967 0.1235 1.5031 -0.0031 -0.0072 0.9569 201.9424 0 10.5661 420.5925 10.3387 0.9735 191.6037 12.4735 1.3888 -5476.25 2635.25 -3987.5 117 1.2887 1.9912 7.2748 62.8333 3.1556 0.2696 3.2728 86.3269 8.7677 50.248 64.1511 49.752 66.1542 86.1468 121.4364 76.39 2.209 70 353.34 10.4091 176.3136 789.7523 1.0341 138.0882 1 667.7418 233.5491 0 4.624 4.894 2865 0.9298 0.9449 4.6414 -12.2945 355.0809 9.7948 144.0191 21.9782 32.2945 44.1498 745.6025 0.9256 146.6636 1 645.7636 65.8417 NaN NaN 0 -0.0534 0.0183 -0.0167 -0.0449 0.0034 -0.0178 -0.0123 -0.0048 7.5017 0.1342 NaN 2.453 0.9902 1828.3846 0.1829 9014.46 0.0448 -0.0077 -0.0001 -0.0001 -0.0001 0.2189 0 -0.6704 -0.0167 0.0004 -0.0003 0.0696 -0.0045 0.0002 0.0078 0 -0.0799 -0.2038 NaN NaN NaN NaN 0.9424 0 796.595 0.9908 58.3858 0.5913 0.9628 6.3551 15.75 3.148 15.73 15.71 0.946 3.027 0.5328 3.299 -0.5677 0.778 1.001 2.3715 993.1274 38.1448 119 143.2 123.1 48.8 296.303 0.3744 0 3.64 0.0041 0.0634 0.0451 0.0623 0.024 14.2354 0 9.005 12.506 0.4434 0.0126 13.9047 0.43 0.0538 NaN NaN 699 283 1747 1443 0.147 0.04 0.113 3.9 0.8 0.101 0.499 0.576 0.0631 0.3053 0.583 0.3053 0.8285 0.1308 0.922 0 0 15.24 0.282 10.85 37.715 0.1189 3.98 0 25.54 72.149 0 0 0 0 0 0 0.25 5.52 15.76 0.519 10.71 19.77 5.52 8.446 33.832 0.3951 9.09 0 19.77 92.307 0 0.0915 0.0506 0.0769 0.1079 0.0797 0.1047 0.0924 0.1015 4.1338 0.003 NaN 0.0802 0.0004 69.151 0.197 1406.4004 0 0.0227 0.0272 0 0 0 0 0 0 0 0 0 0.0067 0.0031 0 0 0 0 NaN NaN NaN NaN 0.024 0 149.2172 0.0006 2.5775 0.0177 0.0214 0.4051 0 0 0 0 0 0 0 0 0 0 0 0.0488 19.862 3.6163 34.125 55.9626 53.0876 17.4864 88.7672 0.1092 0 1.0929 0.0013 0.0257 0.0116 0.0163 0.008 4.4239 0 3.2376 3.6536 0.1293 0.004 4.3474 0.1275 0.0181 NaN NaN 319.1252 128.0296 799.5884 628.3083 0.0755 0.0181 0.0476 1.35 0.2698 0.032 0.1541 0.2155 0.031 0.1354 0.2194 0.1354 0.3072 0.0582 0.3574 0 0 0 4.8956 0.0766 2.913 11.0583 0.0327 1.1229 0 7.3296 23.116 0 0 0 0 0 0 0.0822 1.6216 4.7279 0.1773 3.155 9.7777 1.6216 2.5923 10.5352 0.1301 3.0939 0 6.3767 32.0537 NaN NaN 0 0.0246 0.0221 0.0329 0.0522 0.0256 0.0545 0.0476 0.0463 1.553 0.001 NaN 0.0286 0.0001 21.0312 0.0573 494.7368 0 0.0063 0.0077 0.0052 0.0027 0 0 0 0 0 0 0 0.0025 0.0012 0 0 0 0 NaN NaN NaN NaN 0.0089 0 57.2692 0.0002 0.8495 0.0065 0.0077 0.1356 0 0 0 0 0 0 0 0 0 0 0 0.0165 7.1493 1.1704 5.3823 4.7226 4.9184 2.185 22.3369 24.4142 0 3.6256 3.3208 4.2178 0 866.0295 2.5046 7.0492 0 85.2255 2.9734 4.2892 1.2943 7.257 3.4473 3.8754 12.7642 10.739 43.8119 0 11.4064 2.0088 1.5533 6.2069 25.3521 37.4691 15.247 0.6672 0.7198 0.6076 0.9088 0.6136 1.2524 0.1518 0.7592 0 0 0 4.3131 2.7092 6.1538 4.7756 11.4945 2.8822 0 3.8248 30.8924 0 0 0 0 0 0 5.3863 44.898 4.4384 5.2987 7.4365 89.9529 17.0927 19.1303 4.5375 42.6838 6.1979 0 3.0615 140.1953 0 171.4486 276.881 461.8619 240.1781 0 587.3773 748.1781 0 55.1057 2.2358 NaN 3.2712 0.0372 3.7821 107.6905 15.6016 0 293.1396 0 0 0 0 0 0 0 0 0 0 148.0663 0 0 0 0 0 NaN NaN NaN NaN 2.5512 0 18.7319 0.0616 4.4146 2.9954 2.2181 6.3745 0 0 0 0 0 0 0 0 0 0 0 2.0579 1.9999 9.4805 0.1096 0.0078 0.0026 7.116 1.4636 399.914 79.156 1.0388 19.63 1.98 0.4287 9.7608 0.8311 70.9706 4.9086 2.5014 0.9778 0.2156 0.0461 22.05 NaN NaN NaN NaN NaN NaN NaN NaN 532.0155 2.0275 8.83 0.2224 3.1776 0.0706 1.6597 10.9698 NaN NaN NaN NaN 0.48 0.4766 0.1045 99.3032 0.0202 0.0149 0.0044 73.8432

准备数据:将value为NaN的求均值

def replaceNanWithMean():
datMat = loadDataSet(‘input/13.PCA/secom.data’, ‘ ‘)
numFeat = shape(datMat)[1]
for i in range(numFeat):
# 对value不为NaN的求均值
# .A 返回矩阵基于的数组
meanVal = mean(datMat[nonzero(~isnan(datMat[:, i].A))[0], i])
# 将value为NaN的值赋值为均值
datMat[nonzero(isnan(datMat[:, i].A))[0],i] = meanVal
return datMat

分析数据:统计分析 N 的阈值

PCA分析数据过程

PCA 数据降维

在等式 Av=入v 中,v 是特征向量, 入是特征值。
表示 如果特征向量 v 被某个矩阵 A 左乘,那么它就等于某个标量 入 乘以 v.
幸运的是: Numpy 中有寻找特征向量和特征值的模块 linalg,它有 eig() 方法,该方法用于求解特征向量和特征值。

def pca(dataMat, topNfeat=9999999):
“””pca

Args:
    dataMat   原数据集矩阵
    topNfeat  应用的N个特征
Returns:
    lowDDataMat  降维后数据集
    reconMat     新的数据集空间
"""

# 计算每一列的均值
meanVals = mean(dataMat, axis=0)
# print 'meanVals', meanVals

# 每个向量同时都减去 均值
meanRemoved = dataMat - meanVals
# print 'meanRemoved=', meanRemoved

# cov协方差=[(x1-x均值)*(y1-y均值)+(x2-x均值)*(y2-y均值)+...+(xn-x均值)*(yn-y均值)+]/(n-1)
'''
方差:(一维)度量两个随机变量关系的统计量
协方差: (二维)度量各个维度偏离其均值的程度
协方差矩阵:(多维)度量各个维度偏离其均值的程度

当 cov(X, Y)>0时,表明X与Y正相关;(X越大,Y也越大;X越小Y,也越小。这种情况,我们称为“正相关”。)
当 cov(X, Y)<0时,表明X与Y负相关;
当 cov(X, Y)=0时,表明X与Y不相关。
'''
covMat = cov(meanRemoved, rowvar=0)

# eigVals为特征值, eigVects为特征向量
eigVals, eigVects = linalg.eig(mat(covMat))
# print 'eigVals=', eigVals
# print 'eigVects=', eigVects
# 对特征值,进行从小到大的排序,返回从小到大的index序号
# 特征值的逆序就可以得到topNfeat个最大的特征向量
'''
>>> x = np.array([3, 1, 2])
>>> np.argsort(x)
array([1, 2, 0])  # index,1 = 1; index,2 = 2; index,0 = 3
>>> y = np.argsort(x)
>>> y[::-1]
array([0, 2, 1])
>>> y[:-3:-1]
array([0, 2])  # 取出 -1, -2
>>> y[:-6:-1]
array([0, 2, 1])
'''
eigValInd = argsort(eigVals)
# print 'eigValInd1=', eigValInd

# -1表示倒序,返回topN的特征值[-1 到 -(topNfeat+1) 但是不包括-(topNfeat+1)本身的倒叙]
eigValInd = eigValInd[:-(topNfeat+1):-1]
# print 'eigValInd2=', eigValInd
# 重组 eigVects 最大到最小
redEigVects = eigVects[:, eigValInd]
# print 'redEigVects=', redEigVects.T
# 将数据转换到新空间
# --- (1567, 590) (590, 20)
# print "---", shape(meanRemoved), shape(redEigVects)
lowDDataMat = meanRemoved * redEigVects
reconMat = (lowDDataMat * redEigVects.T) + meanVals
# print 'lowDDataMat=', lowDDataMat
# print 'reconMat=', reconMat
return lowDDataMat, reconMat

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/13.PCA/pca.py
要点补充

降维技术使得数据变的更易使用,并且它们往往能够去除数据中的噪音,使得其他机器学习任务更加精确。
降维往往作为预处理步骤,在数据应用到其他算法之前清洗数据。
比较流行的降维技术: 独立成分分析、因子分析 和 主成分分析, 其中又以主成分分析应用最广泛。

本章中的PCA将所有的数据集都调入了内存,如果无法做到,就需要其他的方法来寻找其特征值。
如果使用在线PCA分析的方法,你可以参考一篇优秀的论文 “Incremental Eigenanalysis for Classification”。
下一章要讨论的奇异值分解方法也可以用于特征值分析。

第12章 使用FP-growth算法来高效发现频繁项集

前言

在 第11章 时我们已经介绍了用 Apriori 算法发现 频繁项集 与 关联规则。
本章将继续关注发现 频繁项集 这一任务,并使用 FP-growth 算法更有效的挖掘 频繁项集。
FP-growth 算法简介

一种非常好的发现频繁项集算法。
基于Apriori算法构建,但是数据结构不同,使用叫做 FP树 的数据结构结构来存储集合。下面我们会介绍这种数据结构。

FP-growth 算法步骤

基于数据构建FP树
从FP树种挖掘频繁项集

FP树 介绍

FP树的节点结构如下:

class treeNode:
def init(self, nameValue, numOccur, parentNode):
self.name = nameValue # 节点名称
self.count = numOccur # 节点出现次数
self.nodeLink = None # 不同项集的相同项通过nodeLink连接在一起
# needs to be updated
self.parent = parentNode # 指向父节点
self.children = {} # 存储叶子节点

FP-growth 原理

基于数据构建FP树

步骤1:

遍历所有的数据集合,计算所有项的支持度。
丢弃非频繁的项。
基于 支持度 降序排序所有的项。
所有数据集合按照得到的顺序重新整理。
重新整理完成后,丢弃每个集合末尾非频繁的项。

步骤2:

读取每个集合插入FP树中,同时用一个头部链表数据结构维护不同集合的相同项。
最终得到下面这样一棵FP树

从FP树中挖掘出频繁项集

步骤3:

对头部链表进行降序排序

对头部链表节点从小到大遍历,得到条件模式基,同时获得一个频繁项集。 如上图,从头部链表 t 节点开始遍历,t 节点加入到频繁项集。找到以 t 节点为结尾的路径如下: 去掉FP树中的t节点,得到条件模式基<左边路径,左边是值>[z,x,y,s,t]:2,[z,x,y,r,t]:1 。条件模式基的值取决于末尾节点 t ,因为 t 的出现次数最小,一个频繁项集的支持度由支持度最小的项决定。所以 t 节点的条件模式基的值可以理解为对于以 t 节点为末尾的前缀路径出现次数。

条件模式基继续构造条件 FP树, 得到频繁项集,和之前的频繁项组合起来,这是一个递归遍历头部链表生成FP树的过程,递归截止条件是生成的FP树的头部链表为空。 根据步骤 2 得到的条件模式基 [z,x,y,s,t]:2,[z,x,y,r,t]:1 作为数据集继续构造出一棵FP树,计算支持度,去除非频繁项,集合按照支持度降序排序,重复上面构造FP树的步骤。最后得到下面 t-条件FP树 : 然后根据 t-条件FP树 的头部链表进行遍历,从 y 开始。得到频繁项集 ty 。然后又得到 y 的条件模式基,构造出 ty的条件FP树,即 ty-条件FP树。继续遍历ty-条件FP树的头部链表,得到频繁项集 tyx,然后又得到频繁项集 tyxz. 然后得到构造tyxz-条件FP树的头部链表是空的,终止遍历。我们得到的频繁项集有 t->ty->tyz->tyzx,这只是一小部分。

条件模式基:头部链表中的某一点的前缀路径组合就是条件模式基,条件模式基的值取决于末尾节点的值。

条件FP树:以条件模式基为数据集构造的FP树叫做条件FP树。

FP-growth 算法优缺点:

  • 优点: 1. 因为 FP-growth 算法只需要对数据集遍历两次,所以速度更快。
    2. FP树将集合按照支持度降序排序,不同路径如果有相同前缀路径共用存储空间,使得数据得到了压缩。
    3. 不需要生成候选集。
    4. 比Apriori更快。
  • 缺点: 1. FP-Tree第二次遍历会存储很多中间过程的值,会占用很多内存。
    2. 构建FP-Tree是比较昂贵的。
  • 适用数据类型:标称型数据(离散型数据)。

FP-growth 代码讲解

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/12.FrequentPattemTree/fpGrowth.py

main 方法大致步骤:

if name == “main“:
simpDat = loadSimpDat() #加载数据集。
initSet = createInitSet(simpDat) #对数据集进行整理,相同集合进行合并。
myFPtree, myHeaderTab = createTree(initSet, 3)#创建FP树。
freqItemList = []
mineTree(myFPtree, myHeaderTab, 3, set([]), freqItemList) #递归的从FP树中挖掘出频繁项集。
print freqItemList

大家看懂原理,再仔细跟踪一下代码。基本就没有问题了。

第 11 章 使用 Apriori 算法进行关联分析

关联分析

关联分析是一种在大规模数据集中寻找有趣关系的任务。 这些关系可以有两种形式:

频繁项集(frequent item sets): 经常出现在一块的物品的集合。
关联规则(associational rules): 暗示两种物品之间可能存在很强的关系。

相关术语

关联分析(关联规则学习): 从大规模数据集中寻找物品间的隐含关系被称作 关联分析(associati analysis) 或者 关联规则学习(association rule learning) 。 下面是用一个 杂货店 例子来说明这两个概念,如下图所示:
关联分析示例1

频繁项集: {葡萄酒, 尿布, 豆奶} 就是一个频繁项集的例子。

关联规则: 尿布 -> 葡萄酒 就是一个关联规则。这意味着如果顾客买了尿布,那么他很可能会买葡萄酒。

那么 频繁 的定义是什么呢?怎么样才算频繁呢? 度量它们的方法有很多种,这里我们来简单的介绍下支持度和可信度。

支持度: 数据集中包含该项集的记录所占的比例。例如上图中,{豆奶} 的支持度为 4/5。{豆奶, 尿布} 的支持度为 3/5。
可信度: 针对一条诸如 {尿布} -> {葡萄酒} 这样具体的关联规则来定义的。这条规则的 可信度 被定义为 支持度({尿布, 葡萄酒})/支持度({尿布}),从图中可以看出 支持度({尿布, 葡萄酒}) = 3/5,支持度({尿布}) = 4/5,所以 {尿布} -> {葡萄酒} 的可信度 = 3/5 / 4/5 = 3/4 = 0.75。

支持度 和 可信度 是用来量化 关联分析 是否成功的一个方法。 假设想找到支持度大于 0.8 的所有项集,应该如何去做呢? 一个办法是生成一个物品所有可能组合的清单,然后对每一种组合统计它出现的频繁程度,但是当物品成千上万时,上述做法就非常非常慢了。 我们需要详细分析下这种情况并讨论下 Apriori 原理,该原理会减少关联规则学习时所需的计算量。
Apriori 原理

假设我们一共有 4 个商品: 商品0, 商品1, 商品2, 商品3。 所有可能的情况如下:
4种商品的所有组合
如果我们计算所有组合的支持度,也需要计算 15 次。即 2^N – 1 = 2^4 – 1 = 15。
随着物品的增加,计算的次数呈指数的形式增长 …
为了降低计算次数和时间,研究人员发现了一种所谓的 Apriori 原理,即某个项集是频繁的,那么它的所有子集也是频繁的。 例如,如果 {0, 1} 是频繁的,那么 {0}, {1} 也是频繁的。 该原理直观上没有什么帮助,但是如果反过来看就有用了,也就是说如果一个项集是 非频繁项集,那么它的所有超集也是非频繁项集,如下图所示:

非频繁项集

在图中我们可以看到,已知灰色部分 {2,3} 是 非频繁项集,那么利用上面的知识,我们就可以知道 {0,2,3} {1,2,3} {0,1,2,3} 都是 非频繁的。 也就是说,计算出 {2,3} 的支持度,知道它是 非频繁 的之后,就不需要再计算 {0,2,3} {1,2,3} {0,1,2,3} 的支持度,因为我们知道这些集合不会满足我们的要求。 使用该原理就可以避免项集数目的指数增长,从而在合理的时间内计算出频繁项集。

Apriori 算法优缺点

  • 优点:易编码实现
  • 缺点:在大数据集上可能较慢
  • 适用数据类型:数值型 或者 标称型数据。

Apriori 算法流程步骤:

  • 收集数据:使用任意方法。
  • 准备数据:任何数据类型都可以,因为我们只保存集合。
  • 分析数据:使用任意方法。
  • 训练数据:使用Apiori算法来找到频繁项集。
  • 测试算法:不需要测试过程。
  • 使用算法:用于发现频繁项集以及物品之间的关联规则。

Apriori 算法的使用

前面提到,关联分析的目标包括两项: 发现 频繁项集 和发现 关联规则。 首先需要找到 频繁项集,然后才能发现 关联规则。
Apriori 算法是发现 频繁项集 的一种方法。 Apriori 算法的两个输入参数分别是最小支持度和数据集。 该算法首先会生成所有单个物品的项集列表。 接着扫描交易记录来查看哪些项集满足最小支持度要求,那些不满足最小支持度要求的集合会被去掉。 燃尽后对生下来的集合进行组合以声场包含两个元素的项集。 接下来再重新扫描交易记录,去掉不满足最小支持度的项集。 该过程重复进行直到所有项集被去掉。
生成候选项集

下面会创建一个用于构建初始集合的函数,也会创建一个通过扫描数据集以寻找交易记录子集的函数, 数据扫描的伪代码如下:

对数据集中的每条交易记录 tran
对每个候选项集 can
    检查一下 can 是否是 tran 的子集: 如果是则增加 can 的计数值
对每个候选项集
    如果其支持度不低于最小值,则保留该项集
    返回所有频繁项集列表 以下是一些辅助函数。

加载数据集

加载数据集

def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

创建集合 C1。即对 dataSet 进行去重,排序,放入 list 中,然后转换所有的元素为 frozenset

创建集合 C1。即对 dataSet 进行去重,排序,放入 list 中,然后转换所有的元素为 frozenset

def createC1(dataSet):
“””createC1(创建集合 C1)

Args:
    dataSet 原始数据集
Returns:
    frozenset 返回一个 frozenset 格式的 list
"""

C1 = []
for transaction in dataSet:
    for item in transaction:
        if not [item] in C1:
            # 遍历所有的元素,如果不在 C1 出现过,那么就 append
            C1.append([item])
# 对数组进行 `从小到大` 的排序
print 'sort 前=', C1
C1.sort()
# frozenset 表示冻结的 set 集合,元素无改变;可以把它当字典的 key 来使用
print 'sort 后=', C1
print 'frozenset=', map(frozenset, C1)
return map(frozenset, C1)

计算候选数据集 CK 在数据集 D 中的支持度,并返回支持度大于最小支持度(minSupport)的数据

计算候选数据集 CK 在数据集 D 中的支持度,并返回支持度大于最小支持度(minSupport)的数据

def scanD(D, Ck, minSupport):
“””scanD(计算候选数据集 CK 在数据集 D 中的支持度,并返回支持度大于最小支持度 minSupport 的数据)

Args:
    D 数据集
    Ck 候选项集列表
    minSupport 最小支持度
Returns:
    retList 支持度大于 minSupport 的集合
    supportData 候选项集支持度数据
"""

# ssCnt 临时存放选数据集 Ck 的频率. 例如: a->10, b->5, c->8
ssCnt = {}
for tid in D:
    for can in Ck:
        # s.issubset(t)  测试是否 s 中的每一个元素都在 t 中
        if can.issubset(tid):
            if not ssCnt.has_key(can):
                ssCnt[can] = 1
            else:
                ssCnt[can] += 1
numItems = float(len(D)) # 数据集 D 的数量
retList = []
supportData = {}
for key in ssCnt:
    # 支持度 = 候选项(key)出现的次数 / 所有数据集的数量
    support = ssCnt[key]/numItems
    if support >= minSupport:
        # 在 retList 的首位插入元素,只存储支持度满足频繁项集的值
        retList.insert(0, key)
    # 存储所有的候选项(key)和对应的支持度(support)
    supportData[key] = support
return retList, supportData

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/11.Apriori/apriori.py
组织完整的 Apriori 算法
输入频繁项集列表 Lk 与返回的元素个数 k,然后输出所有可能的候选项集 Ck

输入频繁项集列表 Lk 与返回的元素个数 k,然后输出所有可能的候选项集 Ck

def aprioriGen(Lk, k):
“””aprioriGen(输入频繁项集列表 Lk 与返回的元素个数 k,然后输出候选项集 Ck。
例如: 以 {0},{1},{2} 为输入且 k = 2 则输出 {0,1}, {0,2}, {1,2}. 以 {0,1},{0,2},{1,2} 为输入且 k = 3 则输出 {0,1,2}
仅需要计算一次,不需要将所有的结果计算出来,然后进行去重操作
这是一个更高效的算法)

Args:
    Lk 频繁项集列表
    k 返回的项集元素个数(若元素的前 k-2 相同,就进行合并)
Returns:
    retList 元素两两合并的数据集
"""

retList = []
lenLk = len(Lk)
for i in range(lenLk):
    for j in range(i+1, lenLk):
        L1 = list(Lk[i])[: k-2]
        L2 = list(Lk[j])[: k-2]
        # print '-----i=', i, k-2, Lk, Lk[i], list(Lk[i])[: k-2]
        # print '-----j=', j, k-2, Lk, Lk[j], list(Lk[j])[: k-2]
        L1.sort()
        L2.sort()
        # 第一次 L1,L2 为空,元素直接进行合并,返回元素两两合并的数据集
        # if first k-2 elements are equal
        if L1 == L2:
            # set union
            # print 'union=', Lk[i] | Lk[j], Lk[i], Lk[j]
            retList.append(Lk[i] | Lk[j])
return retList

找出数据集 dataSet 中支持度 >= 最小支持度的候选项集以及它们的支持度。即我们的频繁项集。

找出数据集 dataSet 中支持度 >= 最小支持度的候选项集以及它们的支持度。即我们的频繁项集。

def apriori(dataSet, minSupport=0.5):
“””apriori(首先构建集合 C1,然后扫描数据集来判断这些只有一个元素的项集是否满足最小支持度的要求。那么满足最小支持度要求的项集构成集合 L1。然后 L1 中的元素相互组合成 C2,C2 再进一步过滤变成 L2,然后以此类推,知道 CN 的长度为 0 时结束,即可找出所有频繁项集的支持度。)

Args:
    dataSet 原始数据集
    minSupport 支持度的阈值
Returns:
    L 频繁项集的全集
    supportData 所有元素和支持度的全集
"""
# C1 即对 dataSet 进行去重,排序,放入 list 中,然后转换所有的元素为 frozenset
C1 = createC1(dataSet)
# 对每一行进行 set 转换,然后存放到集合中
D = map(set, dataSet)
print 'D=', D
# 计算候选数据集 C1 在数据集 D 中的支持度,并返回支持度大于 minSupport 的数据
L1, supportData = scanD(D, C1, minSupport)
# print "L1=", L1, "\n", "outcome: ", supportData

# L 加了一层 list, L 一共 2 层 list
L = [L1]
k = 2
# 判断 L 的第 k-2 项的数据长度是否 > 0。第一次执行时 L 为 [[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])]]。L[k-2]=L[0]=[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])],最后面 k += 1
while (len(L[k-2]) > 0):
    print 'k=', k, L, L[k-2]
    Ck = aprioriGen(L[k-2], k) # 例如: 以 {0},{1},{2} 为输入且 k = 2 则输出 {0,1}, {0,2}, {1,2}. 以 {0,1},{0,2},{1,2} 为输入且 k = 3 则输出 {0,1,2}
    print 'Ck', Ck

    Lk, supK = scanD(D, Ck, minSupport) # 计算候选数据集 CK 在数据集 D 中的支持度,并返回支持度大于 minSupport 的数据
    # 保存所有候选项集的支持度,如果字典没有,就追加元素,如果有,就更新元素
    supportData.update(supK)
    if len(Lk) == 0:
        break
    # Lk 表示满足频繁子项的集合,L 元素在增加,例如: 
    # l=[[set(1), set(2), set(3)]]
    # l=[[set(1), set(2), set(3)], [set(1, 2), set(2, 3)]]
    L.append(Lk)
    k += 1
    # print 'k=', k, len(L[k-2])
return L, supportData

到这一步,我们就找出我们所需要的 频繁项集 和他们的 支持度 了,接下来再找出关联规则即可!

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/11.Apriori/apriori.py
从频繁项集中挖掘关联规则

前面我们介绍了用于发现 频繁项集 的 Apriori 算法,现在要解决的问题是如何找出 关联规则。

要找到 关联规则,我们首先从一个 频繁项集 开始。 我们知道集合中的元素是不重复的,但我们想知道基于这些元素能否获得其它内容。 某个元素或某个元素集合可能会推导出另一个元素。 从先前 杂货店 的例子可以得到,如果有一个频繁项集 {豆奶,莴苣},那么就可能有一条关联规则 “豆奶 -> 莴苣”。 这意味着如果有人买了豆奶,那么在统计上他会购买莴苣的概率比较大。 但是,这一条件反过来并不总是成立。 也就是说 “豆奶 -> 莴苣” 统计上显著,那么 “莴苣 -> 豆奶” 也不一定成立。

前面我们给出了 频繁项集 的量化定义,即它满足最小支持度要求。
对于 关联规则,我们也有类似的量化方法,这种量化指标称之为 可信度。
一条规则 A -> B 的可信度定义为 support(A | B) / support(A)。(注意: 在 python 中 | 表示集合的并操作,而数学书集合并的符号是 U)。
A | B 是指所有出现在集合 A 或者集合 B 中的元素。
由于我们先前已经计算出所有 频繁项集 的支持度了,现在我们要做的只不过是提取这些数据做一次除法运算即可。
一个频繁项集可以产生多少条关联规则呢?

如下图所示,给出的是项集 {0,1,2,3} 产生的所有关联规则:
关联规则网格示意图
与我们前面的 频繁项集 生成一样,我们可以为每个频繁项集产生许多关联规则。
如果能减少规则的数目来确保问题的可解析,那么计算起来就会好很多。
通过观察,我们可以知道,如果某条规则并不满足 最小可信度 要求,那么该规则的所有子集也不会满足 最小可信度 的要求。
如上图所示,假设 123 -> 3 并不满足最小可信度要求,那么就知道任何左部为 {0,1,2} 子集的规则也不会满足 最小可信度 的要求。 即 12 -> 03 , 02 -> 13 , 01 -> 23 , 2 -> 013, 1 -> 023, 0 -> 123 都不满足 最小可信度 要求。

可以利用关联规则的上述性质属性来减少需要测试的规则数目,跟先前 Apriori 算法的套路一样。
以下是一些辅助函数:
计算可信度

计算可信度(confidence)

def calcConf(freqSet, H
, supportData, brl, minConf=0.7):
“””calcConf(对两个元素的频繁项,计算可信度,例如: {1,2}/{1} 或者 {1,2}/{2} 看是否满足条件)

Args:
    freqSet 频繁项集中的元素,例如: frozenset([1, 3])    
    H 频繁项集中的元素的集合,例如: [frozenset([1]), frozenset([3])]
    supportData 所有元素的支持度的字典
    brl 关联规则列表的空数组
    minConf 最小可信度
Returns:
    prunedH 记录 可信度大于阈值的集合
"""
# 记录可信度大于最小可信度(minConf)的集合
prunedH = []
for conseq in H: # 假设 freqSet = frozenset([1, 3]), H = [frozenset([1]), frozenset([3])],那么现在需要求出 frozenset([1]) -> frozenset([3]) 的可信度和 frozenset([3]) -> frozenset([1]) 的可信度

    # print 'confData=', freqSet, H, conseq, freqSet-conseq
    conf = supportData[freqSet]/supportData[freqSet-conseq] # 支持度定义: a -> b = support(a | b) / support(a). 假设  freqSet = frozenset([1, 3]), conseq = [frozenset([1])],那么 frozenset([1]) 至 frozenset([3]) 的可信度为 = support(a | b) / support(a) = supportData[freqSet]/supportData[freqSet-conseq] = supportData[frozenset([1, 3])] / supportData[frozenset([1])]
    if conf >= minConf:
        # 只要买了 freqSet-conseq 集合,一定会买 conseq 集合(freqSet-conseq 集合和 conseq 集合是全集)
        print freqSet-conseq, '-->', conseq, 'conf:', conf
        brl.append((freqSet-conseq, conseq, conf))
        prunedH.append(conseq)
return prunedH

`

递归计算频繁项集的规则

递归计算频繁项集的规则

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
“””rulesFromConseq

Args:
    freqSet 频繁项集中的元素,例如: frozenset([2, 3, 5])    
    H 频繁项集中的元素的集合,例如: [frozenset([2]), frozenset([3]), frozenset([5])]
    supportData 所有元素的支持度的字典
    brl 关联规则列表的数组
    minConf 最小可信度
"""
# H[0] 是 freqSet 的元素组合的第一个元素,并且 H 中所有元素的长度都一样,长度由 aprioriGen(H, m+1) 这里的 m + 1 来控制
# 该函数递归时,H[0] 的长度从 1 开始增长 1 2 3 ...
# 假设 freqSet = frozenset([2, 3, 5]), H = [frozenset([2]), frozenset([3]), frozenset([5])]
# 那么 m = len(H[0]) 的递归的值依次为 1 2
# 在 m = 2 时, 跳出该递归。假设再递归一次,那么 H[0] = frozenset([2, 3, 5]),freqSet = frozenset([2, 3, 5]) ,没必要再计算 freqSet 与 H[0] 的关联规则了。
m = len(H[0])
if (len(freqSet) > (m + 1)):
    print 'freqSet******************', len(freqSet), m + 1, freqSet, H, H[0]
    # 生成 m+1 个长度的所有可能的 H 中的组合,假设 H = [frozenset([2]), frozenset([3]), frozenset([5])]
    # 第一次递归调用时生成 [frozenset([2, 3]), frozenset([2, 5]), frozenset([3, 5])]
    # 第二次 。。。没有第二次,递归条件判断时已经退出了
    Hmp1 = aprioriGen(H, m+1)
    # 返回可信度大于最小可信度的集合
    Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
    print 'Hmp1=', Hmp1
    print 'len(Hmp1)=', len(Hmp1), 'len(freqSet)=', len(freqSet)
    # 计算可信度后,还有数据大于最小可信度的话,那么继续递归调用,否则跳出递归
    if (len(Hmp1) > 1):
        print '----------------------', Hmp1
        # print len(freqSet),  len(Hmp1[0]) + 1
        rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

生成关联规则

生成关联规则

def generateRules(L, supportData, minConf=0.7):
“””generateRules

Args:
    L 频繁项集列表
    supportData 频繁项集支持度的字典
    minConf 最小置信度
Returns:
    bigRuleList 可信度规则列表(关于 (A->B+置信度) 3个字段的组合)
"""
bigRuleList = []
# 假设 L = [[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])]]
for i in range(1, len(L)):
    # 获取频繁项集中每个组合的所有元素
    for freqSet in L[i]:
        # 假设:freqSet= frozenset([1, 3]), H1=[frozenset([1]), frozenset([3])]
        # 组合总的元素并遍历子元素,并转化为 frozenset 集合,再存放到 list 列表中
        H1 = [frozenset([item]) for item in freqSet]
        # 2 个的组合,走 else, 2 个以上的组合,走 if
        if (i > 1):
            rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
        else:
            calcConf(freqSet, H1, supportData, bigRuleList, minConf)
return bigRuleList

到这里为止,通过调用 generateRules 函数即可得出我们所需的 关联规则。

分级法: 频繁项集->关联规则
    1.首先从一个频繁项集开始,接着创建一个规则列表,其中规则右部分只包含一个元素,然后对这个规则进行测试。
    2.接下来合并所有剩余规则来创建一个新的规则列表,其中规则右部包含两个元素。
    如下图:
    所有可能的项集组合
最后: 每次增加频繁项集的大小,Apriori 算法都会重新扫描整个数据集,是否有优化空间呢? 下一章:FP-growth算法等着你的到来

第 10 章 K-Means(K-均值)聚类算法

聚类

聚类,简单来说,就是将一个庞杂数据集中具有相似特征的数据自动归类到一起,称为一个簇,簇内的对象越相似,聚类的效果越好。它是一种无监督的学习(Unsupervised Learning)方法,不需要预先标注好的训练集。聚类与分类最大的区别就是分类的目标事先已知,例如猫狗识别,你在分类之前已经预先知道要将它分为猫、狗两个种类;而在你聚类之前,你对你的目标是未知的,同样以动物为例,对于一个动物集来说,你并不清楚这个数据集内部有多少种类的动物,你能做的只是利用聚类方法将它自动按照特征分为多类,然后人为给出这个聚类结果的定义(即簇识别)。例如,你将一个动物集分为了三簇(类),然后通过观察这三类动物的特征,你为每一个簇起一个名字,如大象、狗、猫等,这就是聚类的基本思想。

至于“相似”这一概念,是利用距离这个评价标准来衡量的,我们通过计算对象与对象之间的距离远近来判断它们是否属于同一类别,即是否是同一个簇。至于距离如何计算,科学家们提出了许多种距离的计算方法,其中欧式距离是最为简单和常用的,除此之外还有曼哈顿距离和余弦相似性距离等。

欧式距离,我想大家再熟悉不过了,但为免有一些基础薄弱的同学,在此再说明一下,它的定义为:
对于x点(坐标为(x1,x2,x3,…,xn))和 y点(坐标为(y1,y2,y3,…,yn)),两者的欧式距离为 d(x,y)={\sqrt {(x_{1}-y_{1})^{2}+(x_{2}-y_{2})^{2}+\cdots +(x_{n}-y_{n})^{2}}}={\sqrt {\sum {{i=1}}^{n}(x{i}-y_{i})^{2}}}
在二维平面,它就是我们初中时就学过的两点距离公式
K-Means 算法

K-Means 是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值 是因为它可以发现 K 个不同的簇, 且每个簇的中心采用簇中所含值的均值计算而成.
簇个数 K 是用户指定的, 每一个簇通过其质心(centroid), 即簇中所有点的中心来描述.
聚类与分类算法的最大区别在于, 分类的目标类别已知, 而聚类的目标类别是未知的.

优点:

属于无监督学习,无须准备训练集
原理简单,实现起来较为容易
结果可解释性较好

缺点:

需手动设置k值。 在算法开始预测之前,我们需要手动设置k值,即估计数据大概的类别个数,不合理的k值会使结果缺乏解释性
可能收敛到局部最小值, 在大规模数据集上收敛较慢
对于异常点、离群点敏感

使用数据类型 : 数值型数据
K-Means 场景

kmeans,如前所述,用于数据集内种类属性不明晰,希望能够通过数据挖掘出或自动归类出有相似特点的对象的场景。其商业界的应用场景一般为挖掘出具有相似特点的潜在客户群体以便公司能够重点研究、对症下药。

例如,在2000年和2004年的美国总统大选中,候选人的得票数比较接近或者说非常接近。任一候选人得到的普选票数的最大百分比为50.7%而最小百分比为47.9% 如果1%的选民将手中的选票投向另外的候选人,那么选举结果就会截然不同。 实际上,如果妥善加以引导与吸引,少部分选民就会转换立场。尽管这类选举者占的比例较低,但当候选人的选票接近时,这些人的立场无疑会对选举结果产生非常大的影响。如何找出这类选民,以及如何在有限的预算下采取措施来吸引他们? 答案就是聚类(Clustering)。

那么,具体如何实施呢?首先,收集用户的信息,可以同时收集用户满意或不满意的信息,这是因为任何对用户重要的内容都可能影响用户的投票结果。然后,将这些信息输入到某个聚类算法中。接着,对聚类结果中的每一个簇(最好选择最大簇 ), 精心构造能够吸引该簇选民的消息。最后, 开展竞选活动并观察上述做法是否有效。

另一个例子就是产品部门的市场调研了。为了更好的了解自己的用户,产品部门可以采用聚类的方法得到不同特征的用户群体,然后针对不同的用户群体可以对症下药,为他们提供更加精准有效的服务。
K-Means 术语

簇: 所有数据的点集合,簇中的对象是相似的。
质心: 簇中所有点的中心(计算所有点的均值而来).
SSE: Sum of Sqared Error(误差平方和), 它被用来评估模型的好坏,SSE 值越小,表示越接近它们的质心. 聚类效果越好。由于对误差取了平方,因此更加注重那些远离中心的点(一般为边界点或离群点)。详情见kmeans的评价标准。

有关 簇 和 质心 术语更形象的介绍, 请参考下图:

K-Means 术语图
K-Means 工作流程

首先, 随机确定 K 个初始点作为质心(不必是数据中的点)。
然后将数据集中的每个点分配到一个簇中, 具体来讲, 就是为每个点找到距其最近的质心, 并将其分配该质心所对应的簇. 这一步完成之后, 每个簇的质心更新为该簇所有点的平均值. 3.重复上述过程直到数据集中的所有点都距离它所对应的质心最近时结束。

上述过程的 伪代码 如下:

创建 k 个点作为起始质心(通常是随机选择)
当任意一个点的簇分配结果发生改变时(不改变时算法结束)
    对数据集中的每个数据点
        对每个质心
            计算质心与数据点之间的距离
        将数据点分配到距其最近的簇
    对每一个簇, 计算簇中所有点的均值并将均值作为质心

K-Means 开发流程

收集数据:使用任意方法
准备数据:需要数值型数据类计算距离, 也可以将标称型数据映射为二值型数据再用于距离计算
分析数据:使用任意方法
训练算法:不适用于无监督学习,即无监督学习不需要训练步骤
测试算法:应用聚类算法、观察结果.可以使用量化的误差指标如误差平方和(后面会介绍)来评价算法的结果.
使用算法:可以用于所希望的任何应用.通常情况下, 簇质心可以代表整个簇的数据来做出决策.

K-Means 的评价标准

k-means算法因为手动选取k值和初始化随机质心的缘故,每一次的结果不会完全一样,而且由于手动选取k值,我们需要知道我们选取的k值是否合理,聚类效果好不好,那么如何来评价某一次的聚类效果呢?也许将它们画在图上直接观察是最好的办法,但现实是,我们的数据不会仅仅只有两个特征,一般来说都有十几个特征,而观察十几维的空间对我们来说是一个无法完成的任务。因此,我们需要一个公式来帮助我们判断聚类的性能,这个公式就是SSE (Sum of Squared Error, 误差平方和 ),它其实就是每一个点到其簇内质心的距离的平方值的总和,这个数值对应kmeans函数中clusterAssment矩阵的第一列之和。 SSE值越小表示数据点越接近于它们的质心,聚类效果也越好。 因为对误差取了平方,因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数,但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。
K-Means 聚类算法函数
从文件加载数据集

从文本中构建矩阵,加载文本文件,然后处理

def loadDataSet(fileName): # 通用函数,用来解析以 tab 键分隔的 floats(浮点数),例如: 1.658985 4.285136
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split(‘\t’)
fltLine = map(float,curLine) # 映射所有的元素为 float(浮点数)类型
dataMat.append(fltLine)
return dataMat

计算两个向量的欧氏距离

计算两个向量的欧式距离(可根据场景选择其他距离公式)

def distEclud(vecA, vecB):
return sqrt(sum(power(vecA – vecB, 2))) # la.norm(vecA-vecB)

构建一个包含 K 个随机质心的集合

为给定数据集构建一个包含 k 个随机质心的集合。随机质心必须要在整个数据集的边界之内,这可以通过找到数据集每一维的最小和最大值来完成。然后生成 0~1.0 之间的随机数并通过取值范围和最小值,以便确保随机点在数据的边界之内。

def randCent(dataSet, k):
n = shape(dataSet)[1] # 列的数量,即数据的特征个数
centroids = mat(zeros((k,n))) # 创建k个质心矩阵
for j in range(n): # 创建随机簇质心,并且在每一维的边界内
minJ = min(dataSet[:,j]) # 最小值
rangeJ = float(max(dataSet[:,j]) – minJ) # 范围 = 最大值 – 最小值
centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1)) # 随机生成,mat为numpy函数,需要在最开始写上 from numpy import *
return centroids

K-Means 聚类算法

k-means 聚类算法

该算法会创建k个质心,然后将每个点分配到最近的质心,再重新计算质心。

这个过程重复数次,直到数据点的簇分配结果不再改变位置。

运行结果(多次运行结果可能会不一样,可以试试,原因为随机质心的影响,但总的结果是对的, 因为数据足够相似,也可能会陷入局部最小值)

def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
m = shape(dataSet)[0] # 行数,即数据个数
clusterAssment = mat(zeros((m, 2))) # 创建一个与 dataSet 行数一样,但是有两列的矩阵,用来保存簇分配结果
centroids = createCent(dataSet, k) # 创建质心,随机k个质心
clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m): # 循环每一个数据点并分配到最近的质心中去
minDist = inf; minIndex = -1
for j in range(k):
distJI = distMeas(centroids[j,:],dataSet[i,:]) # 计算数据点到质心的距离
if distJI < minDist: # 如果距离比 minDist(最小距离)还小,更新 minDist(最小距离)和最小质心的 index(索引)
minDist = distJI; minIndex = j
if clusterAssment[i, 0] != minIndex: # 簇分配结果改变
clusterChanged = True # 簇改变
clusterAssment[i, :] = minIndex,minDist**2 # 更新簇分配结果为最小质心的 index(索引),minDist(最小距离)的平方
print centroids
for cent in range(k): # 更新质心
ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A==cent)[0]] # 获取该簇中的所有点
centroids[cent,:] = mean(ptsInClust, axis=0) # 将质心修改为簇中所有点的平均值,mean 就是求平均值的
return centroids, clusterAssment

测试函数

测试一下以上的基础函数是否可以如预期运行, 请看: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/10.kmeans/kMeans.py
测试一下 kMeans 函数是否可以如预期运行, 请看: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/10.kmeans/kMeans.py

参考运行结果如下:
K-Means 运行结果1
K-Means 聚类算法的缺陷

在 kMeans 的函数测试中,可能偶尔会陷入局部最小值(局部最优的结果,但不是全局最优的结果).

局部最小值的的情况如下:
K-Means 局部最小值1 出现这个问题有很多原因,可能是k值取的不合适,可能是距离函数不合适,可能是最初随机选取的质心靠的太近,也可能是数据本身分布的问题。

为了解决这个问题,我们可以对生成的簇进行后处理,一种方法是将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-均值算法,令k设为2。

为了保持簇总数不变,可以将某两个簇进行合并。从上图中很明显就可以看出,应该将上图下部两个出错的簇质心进行合并。那么问题来了,我们可以很容易对二维数据上的聚类进行可视化, 但是如果遇到40维的数据应该如何去做?

有两种可以量化的办法:合并最近的质心,或者合并两个使得SSE增幅最小的质心。 第一种思路通过计算所有质心之间的距离, 然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程,直到找到合并最佳的两个簇为止。

因为上述后处理过程实在是有些繁琐,所以有更厉害的大佬提出了另一个称之为二分K-均值(bisecting K-Means)的算法.
二分 K-Means 聚类算法

该算法首先将所有点作为一个簇,然后将该簇一分为二。
之后选择其中一个簇继续进行划分,选择哪一个簇进行划分取决于对其划分时候可以最大程度降低 SSE(平方和误差)的值。
上述基于 SSE 的划分过程不断重复,直到得到用户指定的簇数目为止。
二分 K-Means 聚类算法伪代码

将所有点看成一个簇
当簇数目小于 k 时
对于每一个簇
    计算总误差
    在给定的簇上面进行 KMeans 聚类(k=2)
    计算将该簇一分为二之后的总误差
选择使得误差最小的那个簇进行划分操作

另一种做法是选择 SSE 最大的簇进行划分,直到簇数目达到用户指定的数目位置。 接下来主要介绍该做法的python2代码实现
二分 K-Means 聚类算法代码

二分 KMeans 聚类算法, 基于 kMeans 基础之上的优化,以避免陷入局部最小值

def biKMeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2))) # 保存每个数据点的簇分配结果和平方误差
centroid0 = mean(dataSet, axis=0).tolist()[0] # 质心初始化为所有数据点的均值
centList =[centroid0] # 初始化只有 1 个质心的 list
for j in range(m): # 计算所有数据点到初始质心的距离平方误差
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
while (len(centList) < k): # 当质心数量小于 k 时
lowestSSE = inf
for i in range(len(centList)): # 对每一个质心
ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:] # 获取当前簇 i 下的所有数据点
centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas) # 将当前簇 i 进行二分 kMeans 处理
sseSplit = sum(splitClustAss[:,1]) # 将二分 kMeans 结果中的平方和的距离进行求和
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1]) # 将未参与二分 kMeans 分配结果中的平方和的距离进行求和
print “sseSplit, and notSplit: “,sseSplit,sseNotSplit
if (sseSplit + sseNotSplit) < lowestSSE: # 总的(未拆分和已拆分)误差和越小,越相似,效果越优化,划分的结果更好(注意:这里的理解很重要,不明白的地方可以和我们一起讨论)
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy()
lowestSSE = sseSplit + sseNotSplit
# 找出最好的簇分配结果
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) # 调用二分 kMeans 的结果,默认簇是 0,1. 当然也可以改成其它的数字
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit # 更新为最佳质心
print ‘the bestCentToSplit is: ‘,bestCentToSplit
print ‘the len of bestClustAss is: ‘, len(bestClustAss)
# 更新质心列表
centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0] # 更新原质心 list 中的第 i 个质心为使用二分 kMeans 后 bestNewCents 的第一个质心
centList.append(bestNewCents[1,:].tolist()[0]) # 添加 bestNewCents 的第二个质心
clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss # 重新分配最好簇下的数据(质心)以及SSE
return mat(centList), clusterAssment

测试二分 KMeans 聚类算法

测试一下二分 KMeans 聚类算法,请看: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/10.kmeans/kMeans.py

上述函数可以运行多次,聚类会收敛到全局最小值,而原始的 kMeans() 函数偶尔会陷入局部最小值。
运行参考结果如下:
二分 K-Means 运行结果1

第9章 树回归

树回归 概述

我们本章介绍 CART(Classification And Regression Trees, 分类回归树) 的树构建算法。该算法既可以用于分类还可以用于回归。
树回归 场景

我们在第 8 章中介绍了线性回归的一些强大的方法,但这些方法创建的模型需要拟合所有的样本点(局部加权线性回归除外)。当数据拥有众多特征并且特征之间关系十分复杂时,构建全局模型的想法就显得太难了,也略显笨拙。而且,实际生活中很多问题都是非线性的,不可能使用全局线性模型来拟合任何数据。

一种可行的方法是将数据集切分成很多份易建模的数据,然后利用我们的线性回归技术来建模。如果首次切分后仍然难以拟合线性模型就继续切分。在这种切分方式下,树回归和回归法就相当有用。

除了我们在 第3章 中介绍的 决策树算法,我们介绍一个新的叫做 CART(Classification And Regression Trees, 分类回归树) 的树构建算法。该算法既可以用于分类还可以用于回归。
1、树回归 原理
1.1、树回归 原理概述

为成功构建以分段常数为叶节点的树,需要度量出数据的一致性。第3章使用树进行分类,会在给定节点时计算数据的混乱度。那么如何计算连续型数值的混乱度呢?

在这里,计算连续型数值的混乱度是非常简单的。首先计算所有数据的均值,然后计算每条数据的值到均值的差值。为了对正负差值同等看待,一般使用绝对值或平方值来代替上述差值。

上述做法有点类似于前面介绍过的统计学中常用的方差计算。唯一不同就是,方差是平方误差的均值(均方差),而这里需要的是平方误差的总值(总方差)。总方差可以通过均方差乘以数据集中样本点的个数来得到。
1.2、树构建算法 比较

我们在 第3章 中使用的树构建算法是 ID3 。ID3 的做法是每次选取当前最佳的特征来分割数据,并按照该特征的所有可能取值来切分。也就是说,如果一个特征有 4 种取值,那么数据将被切分成 4 份。一旦按照某特征切分后,该特征在之后的算法执行过程中将不会再起作用,所以有观点认为这种切分方式过于迅速。另外一种方法是二元切分法,即每次把数据集切分成两份。如果数据的某特征值等于切分所要求的值,那么这些数据就进入树的左子树,反之则进入树的右子树。

除了切分过于迅速外, ID3 算法还存在另一个问题,它不能直接处理连续型特征。只有事先将连续型特征转换成离散型,才能在 ID3 算法中使用。但这种转换过程会破坏连续型变量的内在性质。而使用二元切分法则易于对树构造过程进行调整以处理连续型特征。具体的处理方法是: 如果特征值大于给定值就走左子树,否则就走右子树。另外,二元切分法也节省了树的构建时间,但这点意义也不是特别大,因为这些树构建一般是离线完成,时间并非需要重点关注的因素。

CART 是十分著名且广泛记载的树构建算法,它使用二元切分来处理连续型变量。对 CART 稍作修改就可以处理回归问题。第 3 章中使用香农熵来度量集合的无组织程度。如果选用其他方法来代替香农熵,就可以使用树构建算法来完成回归。

回归树与分类树的思路类似,但是叶节点的数据类型不是离散型,而是连续型。
1.2.1、附加 各常见树构造算法的划分分支方式

还有一点要说明,构建决策树算法,常用到的是三个方法: ID3, C4.5, CART.
三种方法区别是划分树的分支的方式:

ID3 是信息增益分支
C4.5 是信息增益率分支
CART 做分类工作时,采用 GINI 值作为节点分裂的依据;回归时,采用样本的最小方差作为节点的分裂依据。

工程上总的来说:

CART 和 C4.5 之间主要差异在于分类结果上,CART 可以回归分析也可以分类,C4.5 只能做分类;C4.5 子节点是可以多分的,而 CART 是无数个二叉子节点;

以此拓展出以 CART 为基础的 “树群” Random forest , 以 回归树 为基础的 “树群” GBDT 。
1.3、树回归 工作原理

1、找到数据集切分的最佳位置,函数 chooseBestSplit() 伪代码大致如下:

对每个特征:
对每个特征值:
将数据集切分成两份(小于该特征值的数据样本放在左子树,否则放在右子树)
计算切分的误差
如果当前误差小于当前最小误差,那么将当前切分设定为最佳切分并更新最小误差
返回最佳切分的特征和阈值

2、树构建算法,函数 createTree() 伪代码大致如下:

找到最佳的待切分特征:
如果该节点不能再分,将该节点存为叶节点
执行二元切分
在右子树调用 createTree() 方法
在左子树调用 createTree() 方法

1.4、树回归 开发流程

(1) 收集数据:采用任意方法收集数据。
(2) 准备数据:需要数值型数据,标称型数据应该映射成二值型数据。
(3) 分析数据:绘出数据的二维可视化显示结果,以字典方式生成树。
(4) 训练算法:大部分时间都花费在叶节点树模型的构建上。
(5) 测试算法:使用测试数据上的R^2值来分析模型的效果。
(6) 使用算法:使用训练处的树做预测,预测结果还可以用来做很多事情。

1.5、树回归 算法特点

优点:可以对复杂和非线性的数据建模。
缺点:结果不易理解。
适用数据类型:数值型和标称型数据。

1.6、回归树 项目案例
1.6.1、项目概述

在简单数据集上生成一棵回归树。
1.6.2、开发流程

收集数据:采用任意方法收集数据
准备数据:需要数值型数据,标称型数据应该映射成二值型数据
分析数据:绘出数据的二维可视化显示结果,以字典方式生成树
训练算法:大部分时间都花费在叶节点树模型的构建上
测试算法:使用测试数据上的R^2值来分析模型的效果
使用算法:使用训练出的树做预测,预测结果还可以用来做很多事情

收集数据:采用任意方法收集数据

data1.txt 文件中存储的数据格式如下:

0.036098 0.155096
0.993349 1.077553
0.530897 0.893462
0.712386 0.564858
0.343554 -0.371700
0.098016 -0.332760

准备数据:需要数值型数据,标称型数据应该映射成二值型数据

分析数据:绘出数据的二维可视化显示结果,以字典方式生成树

基于 CART 算法构建回归树的简单数据集
基于 CART 算法构建回归树的简单数据集

用于测试回归树的分段常数数据集
用于测试回归树的分段常数数据集

训练算法: 构造树的数据结构

def binSplitDataSet(dataSet, feature, value):
“””binSplitDataSet(将数据集,按照feature列的value进行 二元切分)
Description:在给定特征和特征值的情况下,该函数通过数组过滤方式将上述数据集合切分得到两个子集并返回。
Args:
dataMat 数据集
feature 待切分的特征列
value 特征列要比较的值
Returns:
mat0 小于等于 value 的数据集在左边
mat1 大于 value 的数据集在右边
Raises:
“””
# # 测试案例
# print ‘dataSet[:, feature]=’, dataSet[:, feature]
# print ‘nonzero(dataSet[:, feature] > value)[0]=’, nonzero(dataSet[:, feature] > value)[0]
# print ‘nonzero(dataSet[:, feature] <= value)[0]=’, nonzero(dataSet[:, feature] <= value)[0]

# dataSet[:, feature] 取去每一行中,第1列的值(从0开始算)
# nonzero(dataSet[:, feature] > value)  返回结果为true行的index下标
mat0 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :]
mat1 = dataSet[nonzero(dataSet[:, feature] > value)[0], :]
return mat0, mat1

1.用最佳方式切分数据集

2.生成相应的叶节点

def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
“””chooseBestSplit(用最佳方式切分数据集 和 生成相应的叶节点)

Args:
    dataSet   加载的原始数据集
    leafType  建立叶子点的函数
    errType   误差计算函数(求总方差)
    ops       [容许误差下降值,切分的最少样本数]。
Returns:
    bestIndex feature的index坐标
    bestValue 切分的最优值
Raises:
"""

# ops=(1,4),非常重要,因为它决定了决策树划分停止的threshold值,被称为预剪枝(prepruning),其实也就是用于控制函数的停止时机。
# 之所以这样说,是因为它防止决策树的过拟合,所以当误差的下降值小于tolS,或划分后的集合size小于tolN时,选择停止继续划分。
# 最小误差下降值,划分后的误差减小小于这个差值,就不用继续划分
tolS = ops[0]
# 划分最小 size 小于,就不继续划分了
tolN = ops[1]
# 如果结果集(最后一列为1个变量),就返回退出
# .T 对数据集进行转置
# .tolist()[0] 转化为数组并取第0列
if len(set(dataSet[:, -1].T.tolist()[0])) == 1: # 如果集合size为1,不用继续划分。
    #  exit cond 1
    return None, leafType(dataSet)
# 计算行列值
m, n = shape(dataSet)
# 无分类误差的总方差和
# the choice of the best feature is driven by Reduction in RSS error from mean
S = errType(dataSet)
# inf 正无穷大
bestS, bestIndex, bestValue = inf, 0, 0
# 循环处理每一列对应的feature值
for featIndex in range(n-1): # 对于每个特征
    # [0]表示这一列的[所有行],不要[0]就是一个array[[所有行]]
    for splitVal in set(dataSet[:, featIndex].T.tolist()[0]):
        # 对该列进行分组,然后组内的成员的val值进行 二元切分
        mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
        # 判断二元切分的方式的元素数量是否符合预期
        if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):
            continue
        newS = errType(mat0) + errType(mat1)
        # 如果二元切分,算出来的误差在可接受范围内,那么就记录切分点,并记录最小误差
        # 如果划分后误差小于 bestS,则说明找到了新的bestS
        if newS < bestS:
            bestIndex = featIndex
            bestValue = splitVal
            bestS = newS
# 判断二元切分的方式的元素误差是否符合预期
# if the decrease (S-bestS) is less than a threshold don't do the split
if (S - bestS) < tolS:
    return None, leafType(dataSet)
mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
# 对整体的成员进行判断,是否符合预期
# 如果集合的 size 小于 tolN 
if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): # 当最佳划分后,集合过小,也不划分,产生叶节点
    return None, leafType(dataSet)
return bestIndex, bestValue

assume dataSet is NumPy Mat so we can array filtering

假设 dataSet 是 NumPy Mat 类型的,那么我们可以进行 array 过滤

def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1, 4)):
“””createTree(获取回归树)
Description:递归函数:如果构建的是回归树,该模型是一个常数,如果是模型树,其模型师一个线性方程。
Args:
dataSet 加载的原始数据集
leafType 建立叶子点的函数
errType 误差计算函数
ops=(1, 4) [容许误差下降值,切分的最少样本数]
Returns:
retTree 决策树最后的结果
“””
# 选择最好的切分方式: feature索引值,最优切分值
# choose the best split
feat, val = chooseBestSplit(dataSet, leafType, errType, ops)
# if the splitting hit a stop condition return val
# 如果 splitting 达到一个停止条件,那么返回 val
if feat is None:
return val
retTree = {}
retTree[‘spInd’] = feat
retTree[‘spVal’] = val
# 大于在右边,小于在左边,分为2个数据集
lSet, rSet = binSplitDataSet(dataSet, feat, val)
# 递归的进行调用,在左右子树中继续递归生成树
retTree[‘left’] = createTree(lSet, leafType, errType, ops)
retTree[‘right’] = createTree(rSet, leafType, errType, ops)
return retTree

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py

测试算法:使用测试数据上的R^2值来分析模型的效果

使用算法:使用训练出的树做预测,预测结果还可以用来做很多事情

2、树剪枝

一棵树如果节点过多,表明该模型可能对数据进行了 “过拟合”。

通过降低决策树的复杂度来避免过拟合的过程称为 剪枝(pruning)。在函数 chooseBestSplit() 中提前终止条件,实际上是在进行一种所谓的 预剪枝(prepruning)操作。另一个形式的剪枝需要使用测试集和训练集,称作 后剪枝(postpruning)。
2.1、预剪枝(prepruning)

顾名思义,预剪枝就是及早的停止树增长,在构造决策树的同时进行剪枝。

所有决策树的构建方法,都是在无法进一步降低熵的情况下才会停止创建分支的过程,为了避免过拟合,可以设定一个阈值,熵减小的数量小于这个阈值,即使还可以继续降低熵,也停止继续创建分支。但是这种方法实际中的效果并不好。
2.2、后剪枝(postpruning)

决策树构造完成后进行剪枝。剪枝的过程是对拥有同样父节点的一组节点进行检查,判断如果将其合并,熵的增加量是否小于某一阈值。如果确实小,则这一组节点可以合并一个节点,其中包含了所有可能的结果。合并也被称作 塌陷处理 ,在回归树中一般采用取需要合并的所有子树的平均值。后剪枝是目前最普遍的做法。

后剪枝 prune() 的伪代码如下:

基于已有的树切分测试数据:
如果存在任一子集是一棵树,则在该子集递归剪枝过程
计算将当前两个叶节点合并后的误差
计算不合并的误差
如果合并会降低误差的话,就将叶节点合并

2.3、剪枝 代码

回归树剪枝函数

判断节点是否是一个字典

def isTree(obj):
“””
Desc:
测试输入变量是否是一棵树,即是否是一个字典
Args:
obj — 输入变量
Returns:
返回布尔类型的结果。如果 obj 是一个字典,返回true,否则返回 false
“””
return (type(obj).name == ‘dict’)

计算左右枝丫的均值

def getMean(tree):
“””
Desc:
从上往下遍历树直到叶节点为止,如果找到两个叶节点则计算它们的平均值。
对 tree 进行塌陷处理,即返回树平均值。
Args:
tree — 输入的树
Returns:
返回 tree 节点的平均值
“””
if isTree(tree[‘right’]):
tree[‘right’] = getMean(tree[‘right’])
if isTree(tree[‘left’]):
tree[‘left’] = getMean(tree[‘left’])
return (tree[‘left’]+tree[‘right’])/2.0

检查是否适合合并分枝

def prune(tree, testData):
“””
Desc:
从上而下找到叶节点,用测试数据集来判断将这些叶节点合并是否能降低测试误差
Args:
tree — 待剪枝的树
testData — 剪枝所需要的测试数据 testData
Returns:
tree — 剪枝完成的树
“””
# 判断是否测试数据集没有数据,如果没有,就直接返回tree本身的均值
if shape(testData)[0] == 0:
return getMean(tree)

# 判断分枝是否是dict字典,如果是就将测试数据集进行切分
if (isTree(tree['right']) or isTree(tree['left'])):
    lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
# 如果是左边分枝是字典,就传入左边的数据集和左边的分枝,进行递归
if isTree(tree['left']):
    tree['left'] = prune(tree['left'], lSet)
# 如果是右边分枝是字典,就传入左边的数据集和左边的分枝,进行递归
if isTree(tree['right']):
    tree['right'] = prune(tree['right'], rSet)

# 上面的一系列操作本质上就是将测试数据集按照训练完成的树拆分好,对应的值放到对应的节点

# 如果左右两边同时都不是dict字典,也就是左右两边都是叶节点,而不是子树了,那么分割测试数据集。
# 1. 如果正确 
#   * 那么计算一下总方差 和 该结果集的本身不分枝的总方差比较
#   * 如果 合并的总方差 < 不合并的总方差,那么就进行合并
# 注意返回的结果: 如果可以合并,原来的dict就变为了 数值
if not isTree(tree['left']) and not isTree(tree['right']):
    lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
    # power(x, y)表示x的y次方
    errorNoMerge = sum(power(lSet[:, -1] - tree['left'], 2)) + sum(power(rSet[:, -1] - tree['right'], 2))
    treeMean = (tree['left'] + tree['right'])/2.0
    errorMerge = sum(power(testData[:, -1] - treeMean, 2))
    # 如果 合并的总方差 < 不合并的总方差,那么就进行合并
    if errorMerge < errorNoMerge:
        print "merging"
        return treeMean
    else:
        return tree
else:
    return tree

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py
3、模型树
3.1、模型树 简介

用树来对数据建模,除了把叶节点简单地设定为常数值之外,还有一种方法是把叶节点设定为分段线性函数,这里所谓的 分段线性(piecewise linear) 是指模型由多个线性片段组成。

我们看一下图 9-4 中的数据,如果使用两条直线拟合是否比使用一组常数来建模好呢?答案显而易见。可以设计两条分别从 0.00.3、从 0.31.0 的直线,于是就可以得到两个线性模型。因为数据集里的一部分数据(0.00.3)以某个线性模型建模,而另一部分数据(0.31.0)则以另一个线性模型建模,因此我们说采用了所谓的分段线性模型。

决策树相比于其他机器学习算法的优势之一在于结果更易理解。很显然,两条直线比很多节点组成一棵大树更容易解释。模型树的可解释性是它优于回归树的特点之一。另外,模型树也具有更高的预测准确度。

分段线性数据

将之前的回归树的代码稍作修改,就可以在叶节点生成线性模型而不是常数值。下面将利用树生成算法对数据进行划分,且每份切分数据都能很容易被线性模型所表示。这个算法的关键在于误差的计算。

那么为了找到最佳切分,应该怎样计算误差呢?前面用于回归树的误差计算方法这里不能再用。稍加变化,对于给定的数据集,应该先用模型来对它进行拟合,然后计算真实的目标值与模型预测值间的差值。最后将这些差值的平方求和就得到了所需的误差。
3.2、模型树 代码

模型树的叶节点生成函数

得到模型的ws系数:f(x) = x0 + x1featrue1+ x3featrue2 …

create linear model and return coeficients

def modelLeaf(dataSet):
“””
Desc:
当数据不再需要切分的时候,生成叶节点的模型。
Args:
dataSet — 输入数据集
Returns:
调用 linearSolve 函数,返回得到的 回归系数ws
“””
ws, X, Y = linearSolve(dataSet)
return ws

计算线性模型的误差值

def modelErr(dataSet):
“””
Desc:
在给定数据集上计算误差。
Args:
dataSet — 输入数据集
Returns:
调用 linearSolve 函数,返回 yHat 和 Y 之间的平方误差。
“””
ws, X, Y = linearSolve(dataSet)
yHat = X * ws
# print corrcoef(yHat, Y, rowvar=0)
return sum(power(Y – yHat, 2))

# helper function used in two places
def linearSolve(dataSet):
“””
Desc:
将数据集格式化成目标变量Y和自变量X,执行简单的线性回归,得到ws
Args:
dataSet — 输入数据
Returns:
ws — 执行线性回归的回归系数
X — 格式化自变量X
Y — 格式化目标变量Y
“””
m, n = shape(dataSet)
# 产生一个关于1的矩阵
X = mat(ones((m, n)))
Y = mat(ones((m, 1)))
# X的0列为1,常数项,用于计算平衡误差
X[:, 1: n] = dataSet[:, 0: n-1]
Y = dataSet[:, -1]

# 转置矩阵*矩阵
xTx = X.T * X
# 如果矩阵的逆不存在,会造成程序异常
if linalg.det(xTx) == 0.0:
    raise NameError('This matrix is singular, cannot do inverse,\ntry increasing the second value of ops')
# 最小二乘法求最优解:  w0*1+w1*x1=y
ws = xTx.I * (X.T * Y)
return ws, X, Y

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py
3.3、模型树 运行结果

模型树运行结果
4、树回归 项目案例
4.1、项目案例1: 树回归与标准回归的比较
4.1.1、项目概述

前面介绍了模型树、回归树和一般的回归方法,下面测试一下哪个模型最好。

这些模型将在某个数据上进行测试,该数据涉及人的智力水平和自行车的速度的关系。当然,数据是假的。
4.1.2、开发流程

收集数据:采用任意方法收集数据
准备数据:需要数值型数据,标称型数据应该映射成二值型数据
分析数据:绘出数据的二维可视化显示结果,以字典方式生成树
训练算法:模型树的构建
测试算法:使用测试数据上的R^2值来分析模型的效果
使用算法:使用训练出的树做预测,预测结果还可以用来做很多事情

收集数据: 采用任意方法收集数据

准备数据:需要数值型数据,标称型数据应该映射成二值型数据

数据存储格式:

3.000000 46.852122
23.000000 178.676107
0.000000 86.154024
6.000000 68.707614
15.000000 139.737693

分析数据:绘出数据的二维可视化显示结果,以字典方式生成树

骑自行车速度和智商之间的关系

训练算法:模型树的构建

用树回归进行预测的代码

回归树测试案例

为了和 modelTreeEval() 保持一致,保留两个输入参数

def regTreeEval(model, inDat):
“””
Desc:
对 回归树 进行预测
Args:
model — 指定模型,可选值为 回归树模型 或者 模型树模型,这里为回归树
inDat — 输入的测试数据
Returns:
float(model) — 将输入的模型数据转换为 浮点数 返回
“””
return float(model)

模型树测试案例

对输入数据进行格式化处理,在原数据矩阵上增加第0列,元素的值都是1,

也就是增加偏移值,和我们之前的简单线性回归是一个套路,增加一个偏移量

def modelTreeEval(model, inDat):
“””
Desc:
对 模型树 进行预测
Args:
model — 输入模型,可选值为 回归树模型 或者 模型树模型,这里为模型树模型
inDat — 输入的测试数据
Returns:
float(X * model) — 将测试数据乘以 回归系数 得到一个预测值 ,转化为 浮点数 返回
“””
n = shape(inDat)[1]
X = mat(ones((1, n+1)))
X[:, 1: n+1] = inDat
# print X, model
return float(X * model)

计算预测的结果

在给定树结构的情况下,对于单个数据点,该函数会给出一个预测值。

modelEval是对叶节点进行预测的函数引用,指定树的类型,以便在叶节点上调用合适的模型。

此函数自顶向下遍历整棵树,直到命中叶节点为止,一旦到达叶节点,它就会在输入数据上

调用modelEval()函数,该函数的默认值为regTreeEval()

def treeForeCast(tree, inData, modelEval=regTreeEval):
“””
Desc:
对特定模型的树进行预测,可以是 回归树 也可以是 模型树
Args:
tree — 已经训练好的树的模型
inData — 输入的测试数据
modelEval — 预测的树的模型类型,可选值为 regTreeEval(回归树) 或 modelTreeEval(模型树),默认为回归树
Returns:
返回预测值
“””
if not isTree(tree):
return modelEval(tree, inData)
if inData[tree[‘spInd’]] <= tree[‘spVal’]:
if isTree(tree[‘left’]):
return treeForeCast(tree[‘left’], inData, modelEval)
else:
return modelEval(tree[‘left’], inData)
else:
if isTree(tree[‘right’]):
return treeForeCast(tree[‘right’], inData, modelEval)
else:
return modelEval(tree[‘right’], inData)

预测结果

def createForeCast(tree, testData, modelEval=regTreeEval):
“””
Desc:
调用 treeForeCast ,对特定模型的树进行预测,可以是 回归树 也可以是 模型树
Args:
tree — 已经训练好的树的模型
inData — 输入的测试数据
modelEval — 预测的树的模型类型,可选值为 regTreeEval(回归树) 或 modelTreeEval(模型树),默认为回归树
Returns:
返回预测值矩阵
“””
m = len(testData)
yHat = mat(zeros((m, 1)))
# print yHat
for i in range(m):
yHat[i, 0] = treeForeCast(tree, mat(testData[i]), modelEval)
# print “yHat==>”, yHat[i, 0]
return yHat

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py

测试算法:使用测试数据上的R^2值来分析模型的效果

R^2 判定系数就是拟合优度判定系数,它体现了回归模型中自变量的变异在因变量的变异中所占的比例。如 R^2=0.99999 表示在因变量 y 的变异中有 99.999% 是由于变量 x 引起。当 R^2=1 时表示,所有观测点都落在拟合的直线或曲线上;当 R^2=0 时,表示自变量与因变量不存在直线或曲线关系。

所以我们看出, R^2 的值越接近 1.0 越好。

使用算法:使用训练出的树做预测,预测结果还可以用来做很多事情

5、附加 Python 中 GUI 的使用
5.1、使用 Python 的 Tkinter 库创建 GUI

如果能让用户不需要任何指令就可以按照他们自己的方式来分析数据,就不需要对数据做出过多解释。其中一个能同时支持数据呈现和用户交互的方式就是构建一个图形用户界面(GUI,Graphical User Interface),如图9-7所示。

GUI示例图
5.2、用 Tkinter 创建 GUI

Python 有很多 GUI 框架,其中一个易于使用的 Tkinter,是随 Python 的标准版编译版本发布的。Tkinter 可以在 Windows、Mac OS和大多数的 Linux 平台上使用。
5.3、集成 Matplotlib 和 Tkinter

MatPlotlib 的构建程序包含一个前端,也就是面向用户的一些代码,如 plot() 和 scatter() 方法等。事实上,它同时创建了一个后端,用于实现绘图和不同应用之间接口。

通过改变后端可以将图像绘制在PNG、PDF、SVG等格式的文件上。下面将设置后端为 TkAgg (Agg 是一个 C++ 的库,可以从图像创建光栅图)。TkAgg可以在所选GUI框架上调用Agg,把 Agg 呈现在画布上。我们可以在Tk的GUI上放置一个画布,并用 .grid()来调整布局。
5.4、用treeExplore 的GUI构建的模型树示例图

取得更好预测效果的GUI示例图

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/treeExplore.py
6、树回归 小结

数据集中经常包含一些复杂的相关关系,使得输入数据和目标变量之间呈现非线性关系。对这些复杂的关系建模,一种可行的方式是使用树来对预测值分段,包括分段常数或分段直线。一般采用树结构来对这种数据建模。相应地,若叶节点使用的模型是分段常数则称为回归树,若叶节点使用的模型师线性回归方程则称为模型树。

CART 算法可以用于构建二元树并处理离散型或连续型数据的切分。若使用不同的误差准则,就可以通过CART 算法构建模型树和回归树。该算法构建出的树会倾向于对数据过拟合。一棵过拟合的树常常十分复杂,剪枝技术的出现就是为了解决这个问题。两种剪枝方法分别是预剪枝(在树的构建过程中就进行剪枝)和后剪枝(当树构建完毕再进行剪枝),预剪枝更有效但需要用户定义一些参数。

Tkinter 是 Python 的一个 GUI 工具包。虽然并不是唯一的包,但它最常用。利用 Tkinter ,我们可以轻轻松松绘制各种部件并安排它们的位置。另外,可以为 Tkinter 构造一个特殊的部件来显示 Matplotlib 绘出的图。所以,Matplotlib 和 Tkinter 的集成可以构建出更强大的 GUI ,用户可以以更自然的方式来探索机器学习算法的奥妙。