摘要：算法及工作原理近鄰算法采用測(cè)量不同特征值之間的距離方法進(jìn)行分類。最后選擇個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類作為新數(shù)據(jù)的分類。

眾所周知,電影可以按照題材分類,然而題材本身是如何定義的?由誰(shuí)來(lái)判定某部電影屬于哪個(gè)題材?也就是說(shuō)同一題材的電影具有哪些公共特征?這些都是在進(jìn)行電影分類時(shí)必須要考慮的問(wèn)題。

動(dòng)作片中也會(huì)存在接吻鏡頭,愛(ài)情片中也會(huì)存在打斗場(chǎng)景,我們不能單純依靠是否存在打斗或者親吻來(lái)判斷影片的類型。

愛(ài)情片中的親吻鏡頭更多,動(dòng)作片中的打斗場(chǎng)景也更頻繁,基于此類場(chǎng)景在某部電影中出現(xiàn)的次數(shù)可以用來(lái)進(jìn)行電影分類。

那么如何基于電影中出現(xiàn)的親吻、打斗出現(xiàn)的次數(shù),使用k-近鄰算法構(gòu)造程序,自動(dòng)劃分電影的題材類型。

k-近鄰(KNN)算法采用測(cè)量不同特征值之間的距離方法進(jìn)行分類。

存在一個(gè)樣本數(shù)據(jù)集合,也稱作訓(xùn)練樣本集,并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽,即我們知道樣本集中每一數(shù)據(jù)與所屬分類的對(duì)應(yīng)關(guān)系。

輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后,將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較,然后算法提取樣本集中特征最相似數(shù)據(jù)(最近鄰)的分類標(biāo)簽。

一般來(lái)說(shuō),我們只選擇樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù),通常k是不大于20的整數(shù)。最后,選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類,作為新數(shù)據(jù)的分類。

動(dòng)作，愛(ài)情，喜劇，災(zāi)難…???

使用打斗和接吻鏡頭數(shù)分類電影

每部電影的打斗鏡頭數(shù)、接吻鏡頭數(shù)以及電影評(píng)估類型

已知電影與未知電影的距離

得到了距離后，選擇前k個(gè)電影來(lái)判斷未知電影的類型

二維空間

多維空間

(1) 收集數(shù)據(jù):可以使用任何方法。
(2) 準(zhǔn)備數(shù)據(jù):距離計(jì)算所需要的數(shù)值,最好是結(jié)構(gòu)化的數(shù)據(jù)格式。
(3) 分析數(shù)據(jù):可以使用任何方法。
(4) 訓(xùn)練算法:此步驟不適用于k-近鄰算法。
(5) 測(cè)試算法:計(jì)算錯(cuò)誤率。
(6) 使用算法:首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果,然后運(yùn)行k-近鄰算法判定輸
入數(shù)據(jù)分別屬于哪個(gè)分類,最后應(yīng)用對(duì)計(jì)算出的分類執(zhí)行后續(xù)的處理。

import numpy as np
def createDataSet():
    """創(chuàng)建數(shù)據(jù)集"""
    # 每組數(shù)據(jù)包含打斗數(shù)和接吻數(shù)；
    group = np.array([[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]])
    # 每組數(shù)據(jù)對(duì)應(yīng)的標(biāo)簽類型；
    labels = ["Roman", "Roman", "Roman", "Action", "Action", "Action"]
    return group, labels

對(duì)未知類別屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行以下操作:
(1) 計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離;
(2) 按照距離遞增次序排序;
(3) 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn);
(4) 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率;
(5) 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類。

def classify(inx, dataSet, labels, k):
    """
    KNN分類算法實(shí)現(xiàn)
    :param inx:要預(yù)測(cè)電影的數(shù)據(jù), e.g.[18, 90]
    :param dataSet:傳入已知數(shù)據(jù)集，e.g. group 相當(dāng)于x
    :param labels:傳入標(biāo)簽，e.g. labels相當(dāng)于y
    :param k:KNN里面的k，也就是我們要選擇幾個(gè)近鄰
    :return:電影類新的排序
    """
    dataSetSize = dataSet.shape[0]  # (6,2) -- 6行2列 ===> 6 獲取行數(shù)
    # tile會(huì)重復(fù)inx， 把它重復(fù)成(dataSetSize, 1)型的矩陣
    # (x1 - y1), (x2 - y2)
    diffMat = np.tile(inx, (dataSetSize, 1)) - dataSet
    # 平方
    sqDiffMat = diffMat ** 2
    # 相加, axis=1行相加
    sqDistance = sqDiffMat.sum(axis=1)
    # 開(kāi)根號(hào)
    distance = sqDistance ** 0.5
    # 排序索引： 輸出的是序列號(hào)index， 而不是值
    sortedDistIndicies = distance.argsort()
    # print(sortedDistIndicies)

    classCount = {}
    for i in range(k):
        # 獲取排前k個(gè)的標(biāo)簽名；
        voteLabel = labels[sortedDistIndicies[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1

    sortedClassCount = sorted(classCount.items(),
                              key=lambda d: float(d[1]),
                              reverse=True)
    return sortedClassCount[0]

分類器并不會(huì)得到百分百正確的結(jié)果,我們可以使用多種方法檢測(cè)分類器的正確率。

為了測(cè)試分類器的效果,我們可以使用已知答案的數(shù)據(jù),當(dāng)然答案不能告訴分類器,檢驗(yàn)分類器給出的結(jié)果是否符合預(yù)期結(jié)果。

完美分類器的錯(cuò)誤率為0

最差分類器的錯(cuò)誤率是1.0

完整代碼

import numpy as np


def createDataSet():
    """創(chuàng)建數(shù)據(jù)集"""
    # 每組數(shù)據(jù)包含打斗數(shù)和接吻數(shù)；
    group = np.array([[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]])
    # 每組數(shù)據(jù)對(duì)應(yīng)的標(biāo)簽類型；
    labels = ["Roman", "Roman", "Roman", "Action", "Action", "Action"]
    return group, labels


def classify(inx, dataSet, labels, k):
    """
    KNN分類算法實(shí)現(xiàn)
    :param inx:要預(yù)測(cè)電影的數(shù)據(jù), e.g.[18, 90]
    :param dataSet:傳入已知數(shù)據(jù)集，e.g. group 相當(dāng)于x
    :param labels:傳入標(biāo)簽，e.g. labels相當(dāng)于y
    :param k:KNN里面的k，也就是我們要選擇幾個(gè)近鄰
    :return:電影類新的排序
    """
    dataSetSize = dataSet.shape[0]  # (6,2) -- 6行2列 ===> 6 獲取行數(shù)
    # tile會(huì)重復(fù)inx， 把它重復(fù)成(dataSetSize, 1)型的矩陣
    # (x1 - y1), (x2 - y2)
    diffMat = np.tile(inx, (dataSetSize, 1)) - dataSet
    # 平方
    sqDiffMat = diffMat ** 2
    # 相加, axis=1行相加
    sqDistance = sqDiffMat.sum(axis=1)
    # 開(kāi)根號(hào)
    distance = sqDistance ** 0.5
    # 排序索引： 輸出的是序列號(hào)index， 而不是值
    sortedDistIndicies = distance.argsort()
    # print(sortedDistIndicies)

    classCount = {}
    for i in range(k):
        # 獲取排前k個(gè)的標(biāo)簽名；
        voteLabel = labels[sortedDistIndicies[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1

    sortedClassCount = sorted(classCount.items(),
                              key=lambda d: float(d[1]),
                              reverse=True)
    return sortedClassCount[0][0]


if __name__ == "__main__":
    group, label = createDataSet()
    result = classify([3, 104], group, label, 5)
    print("[3, 104]的電影類型：",  result)

效果展示