張燕紅 王衛(wèi)玲 王鳳芹 杜 晶

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

1 引言

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

2 算法設計

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

2.1 分類器的訓練

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

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

圖1 分類器的訓練

2.2 分類器的測試

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

圖2 分類器的測試

2.3 算法描述

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

1）從訓練樣本文件中創(chuàng)建一個訓練集。

2）用訓練集中的數(shù)據(jù)為每個屬性生成分離值，并創(chuàng)建分類器。

3）從測試樣本文件中創(chuàng)建一個測試集。

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

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

以訓練集為參數(shù)，對訓練集中的每個樣本數(shù)據(jù)：

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

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

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

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

5）返回得到的分類器。

3 算法實現(xiàn)

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

圖3 病人信息文件示例

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

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

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

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

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

此外，函數(shù)report_results 用于報告分類器預測結(jié)果的精準度。

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

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

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

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

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

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

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

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

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

5）返回得到的分類器。

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

main函數(shù)如下：

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 實驗結(jié)果

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

圖4 Python運行結(jié)果

5 結(jié)語

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