習(xí)題部分：參閱了網(wǎng)上大佬們的習(xí)題答案，然后再自己搞了一下沙峻，順便整理出來(lái)睦授。
????????????????????????????????????????????????????????????表1.1 西瓜數(shù)據(jù)集

編號(hào)??????色澤??????根蒂??????敲聲??????好瓜

1???????????青綠??????蜷縮??????濁響??????是
2???????????烏黑??????蜷縮??????濁響??????是
3???????????青綠??????硬挺??????清脆??????否
4???????????烏黑??????稍蜷?????沉悶?????否

1.1 ??表1.1中若只包含編號(hào)為1和4的兩個(gè)樣例，試給出相應(yīng)的版本空間摔寨。

與訓(xùn)練集一致的“假設(shè)集合”我們稱(chēng)之為版本空間去枷，首先要求出所有的假設(shè)空間，然后在搜索過(guò)程中可以不斷刪除與正例不一致的假設(shè)是复、和與反例一致的假設(shè)删顶，最終會(huì)得到與訓(xùn)練集一致的假設(shè)。由于我們選定了1淑廊、4兩個(gè)樣例逗余，于是屬性色澤有三種可能：*、青綠蒋纬、烏黑猎荠，根蒂有* 、蜷縮蜀备、稍蜷关摇，敲聲有* 、濁響碾阁、沉悶输虱。（通配符"*"：什么值都合使）
將假設(shè)空間用二進(jìn)制數(shù)表示出來(lái)，一個(gè)屬性對(duì)應(yīng)兩位二進(jìn)制數(shù)脂凶，例如：*為11宪睹，青綠為01愁茁，烏黑為10（從大佬那里學(xué)習(xí)到的）......于是假設(shè)空間如下：

二進(jìn)制轉(zhuǎn)十六進(jìn)制（方便代碼實(shí)現(xiàn)）如下：0x3f、0x3d亭病、0x3e鹅很、0x37、0x3b罪帖、0x1f促煮、0x2f、0x35整袁、0x36菠齿、0x39、0x3a坐昙、0x1d绳匀、0x1e、0x2d炸客、0x2e疾棵、0x17、0x1b嚷量、0x27陋桂、0x2b逆趣、0x15蝶溶、0x16、0x19宣渗、0x1a抖所、0x25、0x26痕囱、0x29田轧、0x2a
于是假設(shè)空間可以如此計(jì)算：3×3×3+1=28 其中一個(gè)假設(shè)為，即對(duì)應(yīng)此例是“好瓜”的概念不成立鞍恢，即“好瓜”不存在傻粘。但訓(xùn)練集包含的是正例，所以這種假設(shè)不可能出現(xiàn)其中帮掉，于是將其剔除而只對(duì)27個(gè)假設(shè)進(jìn)行討論弦悉。化作二進(jìn)制可以利用位運(yùn)算符和邏輯運(yùn)算符來(lái)判斷其是否符合版本空間的定義蟆炊，由此對(duì)樣例1和4進(jìn)行處理稽莉。樣例1的十六進(jìn)制數(shù)為0x15，樣例4的十六進(jìn)制數(shù)為0x2a涩搓。代碼如下：

a=[0x3f,0x3d,0x3e,0x37,0x3b,0x1f,0x2f,0x35,0x36,0x39,0x3a,0x1d,0x1e,0x2d,0x2e,  0x17,0x1b,0x27,0x2b,0x15,0x16,0x19,0x1a,0x25,0x26,0x29,0x2a]
b=[0x15,0x2a]
s=0
for i in a:
    if (i|b[1]) !=i and (i|b[0]) == i:
        s+=1
        print(a.index(i)+1)
print("共",s,"個(gè)假設(shè)")

結(jié)果是序號(hào)為2污秆、4劈猪、6、8良拼、12战得、16、20共 7 個(gè)假設(shè)庸推，分別對(duì)應(yīng)上表查看即可贡避。

1.2 與使用單個(gè)合取式來(lái)進(jìn)行假設(shè)表示相比，使用“析合范式”將使得假設(shè)空間具有更強(qiáng)的表示能力予弧。若使用最多包含k個(gè)合取式的析合范式來(lái)表達(dá)表1.1西瓜分類(lèi)問(wèn)題的假設(shè)空間刮吧，試估算有多少種可能的假設(shè)。

合取式（ conJunction）：用合取真值聯(lián)結(jié)詞“∧”將兩個(gè)或兩個(gè)以上的命題聯(lián)結(jié)起來(lái)而形成的命題形式掖蛤。（來(lái)自百科）
析合范式即多個(gè)合取式的析取杀捻。
此問(wèn)題可以參考大佬的做法：《機(jī)器學(xué)習(xí)》（周志華）第一章課后習(xí)題參考答案，但其是用C語(yǔ)言進(jìn)行計(jì)算實(shí)現(xiàn)的蚓庭。
對(duì)于本題致讥，需要去冗余。使用二進(jìn)制表示每個(gè)合取式器赞。共3×4×4=48個(gè)合取式垢袱，
其中不包含*的合取式有2×3×3=18個(gè)。這18個(gè)合取式(稱(chēng)為葉子合取式)可以組合成任意的析合范式港柜、合取式请契。于是我們可以用它們分別與48個(gè)基本的合取式進(jìn)行按位或運(yùn)算（符號(hào) | ，有1則1）夏醉，若運(yùn)算結(jié)果為對(duì)應(yīng)的48個(gè)基本合取式本身爽锥，則記為1，否則記為0畔柔，結(jié)果為48個(gè)18位的二進(jìn)制數(shù)氯夷，這些數(shù)便是析合范式的表示形式。
我們可以發(fā)現(xiàn)本題的假設(shè)空間足足有2¹⁸-1=262143辣么大靶擦！因?yàn)檫@是18位二進(jìn)制數(shù)所能表達(dá)的最大范圍腮考，析合范式不考慮空集，故減去了1玄捕。
以上是對(duì)于析合范式新定義的一種表達(dá)方式踩蔚。下面就是歷遍的問(wèn)題了。下面就參考上面鏈接的文章吧_{可能還未必看得懂}桩盲！
咳咳寂纪，我來(lái)梳理一遍解題思路：
1、首先有3×4×4=48種假設(shè)（合取式），然后題目要求從48種假設(shè)中取k種假設(shè)組合成一個(gè)新的假設(shè)捞蛋，這些新假設(shè)放在一起孝冒，就形成一個(gè)假設(shè)空間
2、但這種假設(shè)空間是有冗余的拟杉，于是我們要剔除通配庄涡，即*造成的冗余，所以映射出2×3×3=18種葉子合取式（有具體值搬设，不存在通配）穴店，對(duì)18種葉子假設(shè)進(jìn)行析取
3、最后拿穴，再對(duì)析取出的重復(fù)項(xiàng)進(jìn)行剔除泣洞，得到無(wú)冗余的假設(shè)空間

1.3???若數(shù)據(jù)包含噪聲，則假設(shè)空間中有可能不存在與所有訓(xùn)練樣本都一致的假設(shè)默色。在此情形下球凰，設(shè)計(jì)一種歸納偏好用于假設(shè)選擇。

有噪聲腿宰，所以就先去噪呕诉，那么如何去噪，方法挺多的吃度。就說(shuō)一種甩挫，若出現(xiàn)同屬性而標(biāo)記不同，可以認(rèn)為它屬于最接近它的幾個(gè)數(shù)據(jù)的屬性椿每，或者將它們?nèi)サ粢琳撸只蛘咧蝗サ舴蠢?/strong>