一種基于均值的多維樣本空間分類器的設計與實現?

張燕紅 王衛玲 王鳳芹 杜 晶

（1.海軍航空大學航空基礎學院計算機教研室 煙臺 264001）（2.煙臺市地理信息中心 煙臺 264003）

1 引言

分類算法是機器學習中的一個重點，是有監督的學習［1］。是一種利用一系列已知類別的樣本來對模型進行訓練，使其達到所要求的性能的過程。也就是說，先用一部分有種種特征的數據和每種數據歸屬的標識來訓練分類模型，當訓練完畢后，再讓計算機用這個分類模型來區分新的“沒見過”的、只有“特征”、沒有類別標識的樣本，完成該樣本的分類，達到預測的目的［2］。分類算法有很多種，如樸素貝葉斯、決策樹歸納、支持向量機SVM 等［5］。這些算法都有復雜的數學理論，沒有數學基礎的人很難理解，且算法復雜度較高。本文設計并實現了一種基于均值的多維樣本空間分類器，簡單易行，準確率高。

2 算法設計

本文假設N 維樣本空間，即樣本有N 個屬性，一些被標記為類別X，一些被標記為非類別X。

2.1 分類器的訓練

首先對每個訓練樣本，逐個考察其屬性數據。其次，將每個訓練樣本的同一個屬性數據組合起來構成一個決斷值，用于對測試樣本的單個屬性進行區分。對訓練樣本的各個屬性值，構建兩組平均值：第一組是訓練樣本中所有類別X 的每個屬性值的平均值；第二組是訓練樣本中所有非類別X 的每個屬性值的平均值。訓練完成后，得到了2N 個平均值，N個是類別X的、N個是非類別X的。

構建分類器的方法是：對每個訓練樣本屬性，計算該屬性的類別X 平均值和非類別X 平均值的中值，該中值就是類區分值，即決斷值或分離值。這樣，分類器將包含N 個區分值，每個屬性一個。分類器訓練過程如圖1所示。

圖1 分類器的訓練

2.2 分類器的測試

輸入測試樣本，用分類器對測試樣本進行分類。即測試樣本的每個屬性數據與分類器的各分離值進行比較，小于分離值的計為類別X，大于分離值的計為非類別X。然后根據類別X 和非類別X屬性的個數，由多數方決定最后的類別預測。分類器的測試過程如圖2所示。

圖2 分類器的測試

2.3 算法描述

基于上述說明，算法描述如下：

1）從訓練樣本文件中創建一個訓練集。

2）用訓練集中的數據為每個屬性生成分離值，并創建分類器。

3）從測試樣本文件中創建一個測試集。

4）用分類器對測試數據進行分類，同時記錄預測的精準度。

其中，第2）步創建分類器是算法核心，具體方法如下。

以訓練集為參數，對訓練集中的每個樣本數據：

1）如果該樣本為類別X 的，將其每個屬性數據加到對應的類別X 屬性累加和上，同時記錄類別X樣本的數量。

2）如果該樣本為非類別X 的，將其每個屬性數據加到對應的非類別X 屬性累加和上，同時記錄非類別X樣本的數量。

3）對N 個類別X 和N 個非類別X 屬性值，計算每個屬性的平均值。

4）對每個類別X 和非類別X 的屬性平均值，計算其中值，即為分離值。由這N個分離值構成分類器。

5）返回得到的分類器。

3 算法實現

本文采用的實驗數據樣本來自于美國加州大學埃爾文分校的機器學習庫（http：//archive.ics.uci.edu/ml）。其中有一個數據集描述的是從乳腺癌病人身上提取的腫瘤組織的屬性。該數據集中包含了699 位病人的腫瘤數據，每位病人的數據由腫瘤的9 個屬性構成，以及相應的最終診斷結果：良性腫瘤或惡性腫瘤。數據的格式為1 個病人ID 號、9個腫瘤特征數據、1 個最終檢查結果（如圖3 所示）。應用本文設計的分類器，即當有新病人來時，能根據其腫瘤活組織的特征，預測病人的腫瘤是良性還是惡性。

圖3 病人信息文件示例

本文實驗環境為Python 2.7，所有代碼均運行通過。按照算法描述，利用“自頂向下、逐步求精”和“分而治之”策略，列出算法的頂層設計。2.3 節中算法四個階段的操作，分別設計四個函數進行抽象：

1）函數make_training_set：以文件名為參數，返回訓練數據列表。

2）函數train_classifier：以訓練數據列表為參數，對分類器進行訓練，返回類分離值列表。

3）函數make_test_set：以文件名為參數，返回測試數據列表。

4）函數classify_test_set_list：以測試數據列表和類分離值列表為參數，對分類器進行測試，返回測試結果。

此外，函數report_results 用于報告分類器預測結果的精準度。

仔細考察make_test_set 函數的功能，發現除了數據文件名不同外，所有的功能都和make_train?ing_set 一樣，因此，可以在此基礎上再次抽象，將make_training_set 和make_test_set 函數抽象成一個函數make_data_set，其功能是：逐行讀入文件數據，為每個病人創建一個元組，并將元組存入數據列表中，最后返回該列表。

train_classifier 函數是程序的核心函數，其主要功能包括：

1）以訓練數據集列表為參數，該列表由函數make_data_set 函數返回。

2）對訓練集中的每個病人數據（以元組組織）。

（1）如果該病人診斷為良性的，將其每個屬性數據加到對應的良性屬性累加和上，同時記錄良性病人數量。

（2）如果該病人診斷為惡性的，將其每個屬性數據加到對應的惡性屬性累加和上，同時記錄惡性病人數量。

（3）最后將得到18 個屬性值的累加和，9 個是良性病人的，9 個是惡性病人的，以及兩種病人的數量。

3）對9 個良性和9 個惡性屬性值，計算每個屬性的平均值。

4）對每個良性和惡性的屬性平均值，計算其中值，即為分離值。由這9 個分離值構成分類器。

5）返回得到的分類器。

classify_test_set 函數讀入一組測試數據，首先將腫瘤屬性值逐項地與分離值進行比較，如果小于，則該項屬性預測為良性，否則該項屬性預測為惡性。然后根據惡性屬性和良性屬性的個數，由多數方決定最后的診斷預測。

main函數如下：

def main（）：

print（“Reading in training data...”）

training_file=“fullTrainData.txt”

training_set_list=make_data_set（training_file）

print（“Done reading training data. ”）

print（“Training classifier...”）

classifier_list=train_classifier（training_set_list）

print（“Done training classifier. ”）

print（“Reading in test data...”）

test_file=“fullTestData.txt”

test_set_list=make_data_set（test_file）

print（“Done reading test data. ”）

print（“Classifying records...”）

result_list = classify_test_set_list（test_set_list，classi?fier_list）

print（“Done classifying. ”）

report_results（result_list）

print（“Program finished.”）

4 實驗結果

測試數據集中共有348 名病人數據，經過本文設計的分類器進行預測，只有8 名不準確。精確度為97.7%，這個結果是令人滿意的。運行結果如圖4 所示。且算法隨樣本空間的維數線性增長，算法時間復雜度低。

圖4 Python運行結果

5 結語

本文設計了一種基于均值的多維樣本空間分類器，并以美國加州大學埃爾文分校的機器學習庫（http：//類別Xrchive.ics.uci.edu/ml）中的乳腺癌病人腫瘤組織屬性數據為樣本進行實驗，精確度為97.7%，實驗結果令人滿意。實驗表明該算法簡單易行，時間復雜度低，性能較高。