数据挖掘分类算法综述外文翻译资料

本科毕业设计（论文）

外文翻译

数据挖掘分类算法综述

作者：Li Mindong；Chen Qingwei；Huang Panling；Zhou Jun；Gong Weike

国籍：中国

出处：国际会议数据库，2019第二届国际机电工程技术会议录(2019年会议)

中文译文：

摘要:分类算法是数据挖掘中的重要算法之一。常用的分类算法如决策树、贝叶斯网络、支持向量机、基于关联规则的分类算法和k近邻算法得到了广泛的应用。本文介绍了经典的分类算法，比较了各种算法的优缺点以及各种算法的最新研究进展。

关键词:数据挖掘；分类算法；综述

1. 介绍

分类算法一直是数据挖掘研究的热点之一。分类算法通过对数据训练集的分析发现分类规则，从而具有预测新的数据类型的能力。分类算法评估预测精度、分类速度、鲁棒性、可伸缩性和可解释性，根据各种算法的特点，他们分为决策树、贝叶斯分类、支持向量机、分类关联规则，再等等。它为开发人员和研究人员选择和研究分类算法提供了方便。

2. 决策树

2.1算法的介绍

决策树是一种基本的分类和回归方法。决策树模型是描述实例分类的树结构，如图1所示。从根节点开始，然后测试实例的一个特性，并根据测试结果将实例分配给它的子节点。

图 1 决策树模型图

2.2算法分析

决策树分类是基于特征对实例进行分类的过程。该模型具有可读性强、分类速度快等优点。首先，基于训练数据建立决策树模型，使损失函数最小化。然后，利用决策树模型对新数据进行分类。决策树分类得到了广泛的应用。Azad等人[1]提出了一种基于决策树和遗传算法的入侵检测系统。Wang[2]将决策树算法应用于车辆服务，提出了一种基于IOVS自选择决策树的VHO方法。降低了切换时间，保证了网络更新速度和车辆服务质量。

2.3 C4.5算法

最广泛使用的决策树是C4.5算法。C4.5算法是决策树算法ID3的改进版本，它消除了不可能的分支和过拟合分支，从而避免了过拟合问题，大大提高了计算速度。C4.5算法的主要优点是精度高、分类模型构建速度快，但对训练样本的数量和质量要求较高。A Cherfi[3]提出了一种新的决策树算法VFC4.5。与C4.5算法相比，VFC4.5算法在大多数情况下决策树更小，精度更高。L Chen[4]提出了一种C4.5-K的期货数据预测算法，提高了期货预测的能力。

3.关联分类

3.1算法的介绍

关联分类(CBA) [5]是一种基于关联规则发现的分类算法。该算法由构造分类器的两个步骤组成:第一步是发现所有关联分类规则(CAR)。第二步是从发现的CAR中选择高优先级规则，覆盖训练集。目前对这个过程的研究较多，因此算法在这一步中不需要对训练集进行过多的描述。Wang L[6]提出了一种基于定量关联规则树的新算法，将关联分类与基于规则的TS模糊推理相结合，生成用于分类和回归预测的规则树结构。

3.2算法分析

关联规则的发现基于经典的Apriori算法。CBA规则比决策树C4.5更精确，因为它发现了相对完整的规则。CBA具有较高的精度，但容易受到硬件内存的限制。CBA被广泛应用。Shao YX[7]等人提出了一种基于原子类关联规则挖掘(ACAR)的软件缺陷预测方法。Alwidian J[8]利用WCBA算法提出了一种基于统计测度的剪枝预测技术，准确预测乳腺癌。Aljuboori[9]提出了一种基于案例推理关联规则(CBRAR)的策略，提高了基于相似性的SBR分类频繁模式树FP-CAR算法的性能，消除了基于案例推理(CBR)错误检索的模糊性。

4. 贝叶斯分类

4.1算法的介绍

贝叶斯分类算法是一种基于概率和统计的分类算法，应用最广泛的是简单的朴素贝叶斯分类[10]。模型的描述如图2所示。

图 2 朴素贝叶斯分类模型

假设有一个变量集U={A，C}，其中A ={A1，A2，hellip;An}包含n个条件属性。C={C1，C2，hellip;Cn}包含m个类标签。朴素贝叶斯分类器模型假设所有条件属性Ai (i=1，2，hellip;，n)均为类变量C的子节点。当且仅当：P(Ci |X)gt;P(Cj|X)(1le;i，jle;m，jne;i)时，将一个样本X={a1，a2，hellip;，an}赋给Ci(1le;ile;m)。

根据贝叶斯定理:

朴素偏差分类模型的步骤:

1)对所需数据集进行预处理，包括属性值的离散化和缺失值的填充。

2)单一大小为S，类Ci的样本数为S_i，类Ci的属性A_k中的样本数为S_ik。

3)计算P(C_i)=S_i/S和P(A_k|e)=S_ik/S_i。

4)根据分类模型，得到待分类样本X的决策结果。

4.2算法分析

朴素贝叶斯分类算法具有以下优点:

1)计算简单。

2)算法具有较高的稳定性。当数据量很小时，它仍然有效。

3)适用于多类分类。

缺点是属性的独立假设在实际问题中可能不能很好地满足，分类效果难以达到实际期望。

朴素贝叶斯分类算法作为一种重要的数据分类方法，由于其具有坚实的理论基础，近年来在数据挖掘领域得到了广泛的研究。Wang XG[11]提出了一种基于MLRM(多元线性回归模型)的加权朴素贝叶斯分类算法，提高了分类精度，有效地提高了NBC(朴素贝叶斯分类算法)的性能。L Zhao[12]提出了一种条件熵匹配的半朴素贝叶斯分类器，能够有效地提高朴素贝叶斯分类器的性能。图像识别也采用贝叶斯方法。Ryan [13]提出了一种优化的朴素贝叶斯算法及其在人脸识别中的应用。

5. K-最近邻分类

5.1算法的介绍

K近邻(KNN)的主要思想是找到特征最相似的训练集，因此预测样本的类型就是最近邻样本的类型。KNN算法的实现如下：

1. 计算每个训练集的特征向量与特征向量之间的距离，计算简单。
2. 按距离对训练样本进行分类。
3. 按顺序取前K个样本，统计出现次数最多的样本的标签。
4. 最高频率标签被认为是被预测样本的标签。

5.2算法分析

K近邻算法的分类决策规则通常是多数投票，输入实例的类由输入实例的k近邻训练实例中的大多数类决定。大多数投票规则是:如果分类损失函数为0-1损失函数，分类函数为:

误分类的概率为:

对于一个给定的实例xisin;chi;，其最近邻的k训练实例点构成集合Nk(x)。如果覆盖Nk (x)的类别为c_j，则误分类率为：

简单的偏置分类算法具有以下优点:

1. 算法很简单。
2. 有效地避免了样本量的不平衡。简单的计算。
3. 测量精度较高。

然而，预测集的每个样本都需要计算其与每个训练样本的相似性。计算复杂度较大，特别是当训练集较大时，计算复杂度会严重影响算法的性能。

由于KNN算法的高精度，研究人员对K近邻算法进行了大量的研究。Zeng Y[14]在传统的ML-KNN算法的基础上，提出了IML-KNN算法，考虑了非分类样本的最近邻和K个近邻的影响。对多指标评价具有良好的分类效果。Xie Y[15]提出了一种改进的KNN方法，称为KNN ，用于对具有异构视图的复杂数据进行分类。Kutylowska M[16]采用非参数回归算法K近邻预测失效率。Zhang NA[17]提出了一种改进的KNN算法来克服类分布倾斜时的类重叠问题。

6. 支持向量机

6.1算法的介绍

支持向量机(SVM)[18]是在线性可分条件下，由最优分类曲面发展而来的一种算法。它具有较强的理论基础，可用于分类任务。超平面方程为:

w= (w1， w2，hellip;，wk)为超平面的法向量，表示平面的方向，b为位移，表示超平面到原点的距离。然后我们可以得到样本中点到超平面的距离为:

如果超平面可以将正样本和负样本分离，则得到:

不同类型的两个支持向量到超平面的距离为:

我们希望R是最大的，所以我们需要得到如下公式:

将拉格朗日乘子part;_ige;0相加，得到拉格朗日方程:

因此SVM模型为:

6.2算法分析

SVM算法的复杂度取决于支持向量的个数，而不是样本空间的维数，因此计算量不大，泛化精度较高。缺点是支持向量算法对参数调整和核函数选择敏感，在存储和计算上占用较多的内存和运行时间，不适用于大规模样本训练。HW Wang[19]采用改进的支持向量机有效地提高了分布的精度。Yeh JP等人[20]提出了模拟退火算法来减少支持向量机的数量，提高分类精度。F Zhu[21]提出了一种加权支持向量机(WOC-SVM)，它通过分配较低的权值来最小化噪声的影响。

7. 其他分类算法

除上述分类算法外，常用的还有遗传算法、神经网络等分类算法。遗传算法是现代智能计算的关键技术之一，它基于生物进化的思想，通过模拟自然进化过程来寻找最优解。神经网络是一组连接的I/O单元，其中每个连接都与一个权值相关联。神经网络算法对噪声数据具有较高的容忍度和较高的分类精度，使得神经网络在数据挖掘中具有良好的效果。但是处理大量的数据需要很长时间。

8. 总结与展望

分类是一项重要的数据挖掘技术。本文对各种算法进行了总结，总结了各种算法的最新发展和应用领域。事实上，在数据膨胀的时代，算法的性能更为重要，比如执行速度、输出结果的可扩展性和可理解性。因此，虽然每种算法都有自己的优点，但是一个在各个方面都具有良好特征的分类算法仍然值得进一步研究。

致谢

1. 项目资助单位:山东省重点研发项目(批准号:2017CXGC0810)。
2. 项目资助单位:山东省重点研发项目(批准号:2017CXGC0215)。
3. 项目资助单位:山东省重点研发项目(批准号:2017CXGC0903)。
4. 项目资助单位:山东省重点研发项目(批准号:2018CXGC0908)。
5. 项目资助单位:山东省重点研发项目(批准号:2018CXGC0215)。
6. 项目资助单位:山东省重点研发项目(批准号:2018CXGC1405)。
7. 鸣谢:本项目为山东省重点研发项目(批准号2018CXGC0808)。
8. 项目资助单位:山东省重点研发项目(批准号:2018CXGC0601)。

参考文献

1. V. Nath and J. Kumar Mandal, “Decision tree and genetic algorithm based intrusion detection system,” Second International Conference on Microelectronics, Computing amp; Communication Systems，Ranchi, pp.141-52, May 2017.
2. SG. Wang, CQ. Fan, C

   剩余内容已隐藏，支付完成后下载完整资料

   ---

   A Review of Classification Algorithms for Data Mining

   Li Mindong^1,a, Chen Qingwei^1,b, Huang Panling^1,c, Zhou Jun^1,d,*, Gong Weike²

   ¹Shandong University, Jinan, China

   ²Shandong Bosheng Power Technology CO.,LTD, Linyi, China

   ^a1102570384@qq.com, ^b858747715@qq.com, ^chfpl@sdu.edu.cn, ^dzhoujun@sdu.edu.cn

   Keywords: data mining; classification algorithm; review

   Abstract: Classification algorithm is one of the important algorithms in data mining. Common classification algorithms such as decision tree, Bayesian network, support vector machine, association rules based classification algorithm and K-nearest neighbor algorithm have been widely used. This paper introduces the classical classification algorithm, compares the advantages and disadvantages of each algorithm and the latest research progress of each algorithm.

   1. Introduction

   Classification algorithm has always been one of the hotspots in data mining research. Classification algorithm discovers classification rules through the analysis of data training sets, and thus has the ability to predict new data types. Classification algorithms are evaluated by predictive accuracy, classification speed, robustness, scalability, and interpretability In this paper, according to the characteristics of various algorithms, they are divided into decision tree, Bayesian classification, support vector machine, classification of association rules and K-nearest neighbor and so on. It is convenient for developers and researchers to select and study classification algorithms.

   2. Decision Tree

   2.1 Algorithm Introduction

   Decision tree is a basic classification and regression method. The decision tree model is a tree structure that describes the classification of instances, as shown in the following figure 1. Start from the root node, then test a feature of the instance, and assign the instance to its children according to the test results.

   Fig. 1. Decision tree model diagram.

   2.2 Algorithm Analysis

   Decision tree classification is the process of classifying instances based on features. The model has the advantages of readability and fast classification speed. First, the decision tree model is established based on the training data and minimizing the loss function. Then, the new data is classified by decision tree model. Decision tree classification is widely applied. Azad et al. [1]proposed an intrusion detection system based on decision tree and genetic algorithm. Wang [2] applied decision tree algorithm to vehicle service, and proposed a new VHO method based on IOVS

   self-selection decision tree. The switching time is reduced, and the network update rate and vehicle service quality are guaranteed.

   2.3 C4.5 Algorithm

   The most widely used decision tree is the C4.5 algorithm. C4.5 algorithm is an improved version of decision tree algorithm ID3, which eliminates impossible branches and over-fitting branches, thus avoiding the over-fitting problem and greatly improving the calculation speed. The main advantages of C4.5 algorithm are high accuracy and fast construction of classification model, but it requires high quantity and quality of training samples. A Cherfi [3] proposed a new decision tree algorithm VFC4.5. Compared with C4.5 algorithm, VFC4.5 algorithm results in smaller decision tree in most cases and has better precision. L Chen [4] proposed a C4.5-K algorithm for futures data, which improved the ability of futures prediction.

   3. Classification Based On Association

   3.1 Algorithm Introduction

   Classification based on association (CBA) [5] is a classification algorithm based on association rules discovery method. The algorithm consists of two steps to construct a classifier: the first step is to discover all classification association rules (CAR). The second step is to select high priority rules from the discovered CAR to overlay the training set. At present, there are many researches on this process, so the algorithm does not need to scan the training set too much in this step. Wang L [6] proposes a new algorithm based on quantitative association rules tree (CRQAR-tree), which combines association classification with rule-based TS fuzzy reasoning to generate rule tree structure for classification and regression prediction.

   3.2 Algorithm Analysis

   The discovery of association rules is based on classical algorithm Apriori. CBA rules is more accurate than decision tree C4.5 because it discovers relatively complete rules. CBA has high accuracy, but it is easy to be restricted by hardware memory. CBA is widely applied. Shao YX et al.

   [7] proposed a software defect prediction based on atomic class-association rule mining (ACAR). Alwidian J [8] used WCBA algorithm to propose a statistical measure based pruning and prediction technology, accurate prediction of breast cancer. Aljuboori [9] proposed a case-based reasoning association rule (CBRAR) strategy to improve the performance of similarity-based retrieval SBR classification frequent pattern tree FP-CAR algorithm, eliminating the ambiguity of case-based reasoning (CBR) error retrieval.

   4. Bayes Classification

   4.1 Algorithm Introduction

   Bayes classification algorithm is a kind of classification algorithm based on probability and statistics, and the most widely used is the simple Bias classifier [10]. The description of the model is shown in Figure 2.

   Fig. 2. naive Bayesian classification model

   Suppose there is a variable set U={A,C},among the

   剩余内容已隐藏，支付完成后下载完整资料

   ---

   资料编号：[273044]，资料为PDF文档或Word文档，PDF文档可免费转换为Word