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

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

動作片中也會存在接吻鏡頭,愛情片中也會存在打斗場景,我們不能單純依靠是否存在打斗或者親吻來判斷影片的類型。

愛情片中的親吻鏡頭更多,動作片中的打斗場景也更頻繁,基于此類場景在某部電影中出現的次數可以用來進行電影分類。

那么如何基于電影中出現的親吻、打斗出現的次數,使用k-近鄰算法構造程序,自動劃分電影的題材類型。

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

存在一個樣本數據集合,也稱作訓練樣本集,并且樣本集中每個數據都存在標簽,即我們知道樣本集中每一數據與所屬分類的對應關系。

輸入沒有標簽的新數據后,將新數據的每個特征與樣本集中數據對應的特征進行比較,然后算法提取樣本集中特征最相似數據(最近鄰)的分類標簽。

一般來說,我們只選擇樣本數據集中前k個最相似的數據,通常k是不大于20的整數。最后,選擇k個最相似數據中出現次數最多的分類,作為新數據的分類。

動作，愛情，喜劇，災難…???

使用打斗和接吻鏡頭數分類電影

每部電影的打斗鏡頭數、接吻鏡頭數以及電影評估類型

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

得到了距離后，選擇前k個電影來判斷未知電影的類型

二維空間

多維空間

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

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

對未知類別屬性的數據集中的每個點依次執行以下操作:
(1) 計算已知類別數據集中的點與當前點之間的距離;
(2) 按照距離遞增次序排序;
(3) 選取與當前點距離最小的k個點;
(4) 確定前k個點所在類別的出現頻率;
(5) 返回前k個點出現頻率最高的類別作為當前點的預測分類。

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

    classCount = {}
    for i in range(k):
        # 獲取排前k個的標簽名；
        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

最差分類器的錯誤率是1.0

完整代碼

import numpy as np


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


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

    classCount = {}
    for i in range(k):
        # 獲取排前k個的標簽名；
        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)

效果展示