张燕红 王卫玲 王凤芹 杜 晶

（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%，实验结果令人满意。实验表明该算法简单易行，时间复杂度低，性能较高。