2019/11/12 Caesar
前言
??今天開始，我將扎進(jìn)機(jī)器學(xué)習(xí)的大坑。選擇一個(gè)經(jīng)典、容易理解的機(jī)器學(xué)習(xí)算法--- K近鄰算法來熱身，我將用 K近鄰算法來做一個(gè)常見的應(yīng)用，給豆瓣文章分類。現(xiàn)在開始：
1.1場景
想象自己是這幅圖中的綠色圓圈，我是誰？我是什么？k近鄰算法解答這個(gè)問題的依據(jù)是：，圖中所有圖形到綠色圓圈的距離，選出距離最短的k個(gè)，然后統(tǒng)計(jì)這k個(gè)圖形的所屬類別，投票出類占比最高的那個(gè)類別，就是綠色圓圈的類別。
1.2基本概念
k近鄰算法實(shí)現(xiàn)簡單，缺點(diǎn)是當(dāng)訓(xùn)練樣本數(shù)大、特征向量維數(shù)高時(shí)計(jì)算復(fù)雜度很大。算法復(fù)雜度主要在于，每次預(yù)測時(shí)要計(jì)算待預(yù)測樣本和每個(gè)測試樣本之間的距離，而且要對距離進(jìn)行排序找到最近的
k個(gè)樣本。因此我們有一種解決方案，用 k-d樹來實(shí)現(xiàn)快速的近鄰樣本查找。
k近鄰算法的實(shí)現(xiàn)依賴樣本之間的距離值，因此，我們必須給出定義距離的計(jì)算方式。我們常用的距離函數(shù)是歐式距離，
但是，我們還需做點(diǎn)改動(dòng)，也就是將應(yīng)用歐式距離的特征向量的每個(gè)分量進(jìn)行歸一化，目的是減少因?yàn)樘卣髦档某叨确秶煌鶐淼母蓴_，否則數(shù)值小的特征向量會被數(shù)值大的特征向量淹沒。舉個(gè)栗子，特征向量包含兩個(gè)分量，分別為身高和肺活量，但是正常成年人的身高是 150 cm ~ 200 cm ，肺活量為 2000 ~ 9000 ml。如果不做歸一化，直接揉在一起計(jì)算，那么身高帶來的個(gè)體差異將蕩然無存。
1.3算法流程
接下來我們嘮嘮，工程師是怎么一步步實(shí)現(xiàn)這個(gè)k近鄰算法。
1.計(jì)算測試樣本到訓(xùn)練集所有樣本之間的距離；
2.將所有距離進(jìn)行遠(yuǎn)近排序，選出與測試樣本最近的k個(gè)樣本，即鄰居；
3.統(tǒng)計(jì)這k個(gè)的樣本類別的頻率；
4.取這k個(gè)樣本中最高頻率的樣本類別為類別結(jié)果，完成kNN算法實(shí)驗(yàn)。
1.4算法實(shí)現(xiàn)
Python在手，擼它！
1.數(shù)據(jù)準(zhǔn)備
#數(shù)據(jù)
def createDataSet():
group = np.array([[1, 1.1], [1, 1], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B'] return group, labels
2.計(jì)算各訓(xùn)練樣本到測試樣本的歐式距離
# knn classify
def classify(inX,dataSet,labels,k):
m, n = dataSet.shape
distance = []
for i in range(m):
tmp = np.sqrt(np.sum(np.square(inX-dataSet[i])))
distance.append(tmp)
sortedDist = sorted(distance)
classCount = {}
for i in range(k):
voteLabel = labels[distance.index(sortedDist[i])]
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 # 默認(rèn)0：map
sortedClass = sorted(classCount.items(), key=lambda d: d[1], reverse=True)
return sortedClass[0][0]
3.測試
if __name__ == '__main__':
dataSet, labels = createDataSet()
r = classify([0,0.2], dataSet, labels, 1)
print(r)
1.5案例分析
假設(shè)我們已經(jīng)有了一些豆瓣帖子，并知道他們是哪些類型的，比如旅游相關(guān)的，租房相關(guān)的。這個(gè)時(shí)候有個(gè)新的帖子，我們的任務(wù)是利用kNN算法判斷它屬于哪一類。做法：只要計(jì)算它與其它帖子的距離，然后選出 k 個(gè)最近的帖子樣本，就可以知道這個(gè)帖子應(yīng)該分到哪個(gè)類中。
1.5案例實(shí)現(xiàn)
1.數(shù)據(jù)處理
首先我們需要將文本內(nèi)容向量化，這里用到了 jieba 分詞。
def cut_word(content):
tags = jieba.analyse.extract_tags(content, withWeight=True, topK=20)
return tags
def merge_tags(*tags):
tag_dict_list = []
v_list = []
for tag in tags:
tag_dict_list.append({i[0]: i[1] for i in tag})
merged_tag = []
for i in tag_dict_list:
merged_tag.extend(i.keys())
merged_tag = set(merged_tag)
for tag_dict in tag_dict_list:
v = []
for i in merged_tag:
if i in tag_dict:
v.append(tag_dict[i])
else:
v.append(0) v_list.append(v)
return v_list
2.kNN算法
這里....當(dāng)然不必重復(fù)造輪子啦！用我們前面實(shí)現(xiàn)的kNN分類器即可。
def classify(inX, dataSet, labels, k):
"""
定義knn算法分類器函數(shù)
:param inX: 測試數(shù)據(jù)
:param dataSet: 訓(xùn)練數(shù)據(jù)
:param labels: 分類類別
:param k: k值
:return: 所屬分類
"""
m, n = dataSet.shape # shape（m, n）m列n個(gè)特征
# 計(jì)算測試數(shù)據(jù)到每個(gè)點(diǎn)的歐式距離
distances = []
for i in range(m):
sum = 0
for j in range(n):
sum += (inX[j] - dataSet[i][j]) ** 2
distances.append(sum ** 0.5)
sortDist = sorted(distances)
# k個(gè)最近的值所屬的類別
classCount = {}
for i in range(k):
voteLabel = labels[distances.index(sortDist[i])] #初始化首下標(biāo)值
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 #默認(rèn)0：map
sortedClass = sorted(classCount.items(), key = lambda d:d[1], reverse=True)
return sortedClass[0][0]
3.測試
# 租房相關(guān)
content1 = u"""
可月付 無中介 方莊地鐵附近 芳城園一區(qū)單間出租
我的房子在方莊地鐵附近的芳城園一區(qū)，正規(guī)小區(qū)樓房，
三家合住，現(xiàn)出租一間主臥和一間帶小陽臺次臥，室內(nèi)家電齊全，
冰箱，洗衣機(jī)等都有，可洗澡上網(wǎng)，做飯都可以，小區(qū)交通便利，四通八達(dá)，
希望入住的是附近正常上班的朋友
"""
content2 = u"""
可月付 無中介 方莊地鐵附近 芳城園一區(qū)主臥次臥出租
我的房子在方莊地鐵附近的芳城園一區(qū)，正規(guī)小區(qū)樓房，
三家合住，現(xiàn)出租一間主臥和一間帶小陽臺次臥，室內(nèi)家電齊全，
冰箱，洗衣機(jī)等都有，可洗澡上網(wǎng)，做飯都可以，小區(qū)交通便利，四通八達(dá)，
希望入住的是附近正常上班的朋友
"""
content3 = u"""方莊地鐵附近 芳城園一區(qū)次臥出租
我的房子在方莊地鐵附近的芳城園一區(qū)，正規(guī)小區(qū)樓房，
三家合住，現(xiàn)出租一間主臥和一間帶小陽臺次臥，室內(nèi)家電齊全，
冰箱，洗衣機(jī)等都有，可洗澡上網(wǎng)，做飯都可以，小區(qū)交通便利，四通八達(dá)，
希望入住的是附近正常上班的朋友
"""
test_content4 = u"""二環(huán)玉蜓橋旁下月27號后可入住二居
方莊方古園一區(qū)5號樓下月27日到期出租，
我是房主無中介費(fèi) ，新一年租6000元每月押一付三，主次臥可分開住。
距地鐵5號線蒲黃榆站5分鐘路程。房屋60平正向，另有看守固定車位。
"""
# 旅游相關(guān)
content5 = u"""世界盡頭和冷酷仙境 去南極大部分都是從烏斯懷亞出發(fā)，
這是南美大陸的最南端，所以也被稱為世界盡頭。在這里，有很多東西都已經(jīng)到了終點(diǎn)：
世界最盡頭的郵局；世界最盡頭的徒步線路；還有傳說中“泛美公路”的終點(diǎn)，
這條路從阿拉斯加一路向南開過來，17848公里，開到這里居然也到頭了，沒路了…然而，
世界盡頭也可以是起點(diǎn)，這里距離南極大陸只有不到1000公里的距離，世界盡頭之后就是冷酷仙境。
"""
content6 = u"""走 走停停，看看世界上其中一條最美麗最浪漫的海岸線：那不勒斯灣到amalfi 海岸。
歐洲 最美是小鎮(zhèn)，意大利南部小鎮(zhèn)與北部山區(qū)小鎮(zhèn)完全不一樣的風(fēng)格但又一樣是浪漫和美麗的世 外桃源。
這個(gè)海岸線之所以美，原因跟托斯卡納的山區(qū)一樣， 建筑與自然的完美融合。海、 山與小屋群形成了一副美麗的風(fēng)景畫。
沿著鐵路和公路，陸路從那不勒斯走到Amalfi。
"""
content7 = u"""仙本娜是一個(gè)幾乎由潛水業(yè)支撐的小鎮(zhèn)，走幾步路就是潛店，
來自世界各地的游客每個(gè)人都在說著潛水。不大，但是比起馬布就豐富多了，
有旅館，酒吧，咖啡店，飯店，小賣部，還有一個(gè)大超市。到了仙本娜，
去一間叫龍門客棧（DRAGON ING）的旅館CHECK IN。這是一件建在水上的樹皮旅館，
不論室內(nèi)室外的墻面全部是樹皮，很有原始的風(fēng)味，房間內(nèi)有冷風(fēng)機(jī)，價(jià)格也不貴，66馬幣，
一個(gè)大床，有電視機(jī)，帶衛(wèi)生間。從馬布搬過來，覺得這個(gè)環(huán)境真是天堂。旅館由水上的很多長廊組成，
連成一條網(wǎng)，我?guī)缀趺月贰? """
test_content8 = """ 環(huán)游世界當(dāng)然不能真地把旅行都拋掉啦，偉大的古文明和異國文化是環(huán)游世界的其中一個(gè)重要目的。
美洲的瑪雅文明，非洲的埃及文明，亞洲的印度文明，一個(gè)個(gè)從人類起源就可以追溯的古文明。
一個(gè)個(gè)讓人目定口呆的世界文化遺產(chǎn)。感受人類的力量同時(shí)感受時(shí)間的偉大和殘酷。 還有令人陶醉的異國文化，去捷克感受的波西米亞文化，
到倫敦西區(qū)和紐約百老匯看歌舞劇等等，品味澳大利亞的葡萄酒蘇格蘭的威士忌墨西哥的龍舌蘭。有時(shí)候，小資也是一種情調(diào)?。?
"""
tag1 = cut_word(content1)
tag2 = cut_word(content2)
tag3 = cut_word(content3)
tag4 = cut_word(test_content4)
tag5 = cut_word(content5)
tag6 = cut_word(content6)
tag7 = cut_word(content7)
tag8 = cut_word(test_content8)
v = [tag1, tag2, tag3, tag4, tag5, tag6, tag7, tag8]
data = merge_tags(*v)
v4 = data.pop(3)
v8 = data.pop()
dataSet = array(data)
labels = array(['租房', '租房', '租房', '旅游', '旅游', '旅游'])
k = 3
v4 = array(v4)
outputLabel = kNNClassify(v4, dataSet, labels, k)
print "Your input is: v4 and classified to class: ", outputLabel
v8 = array(v8)
outputLabel = kNNClassify(v8, dataSet, labels, k)
print "Your input is: v8 and classified to class: ", outputLabel
