數(shù)據(jù)挖掘經(jīng)典分類聚類算法的研究綜述

姚奇峰 楊連賀

摘? 要：對(duì)于當(dāng)下的學(xué)生來說，數(shù)據(jù)挖掘是一門經(jīng)久不衰的學(xué)科，而對(duì)于從事數(shù)據(jù)挖掘的工作者來說，更是深刻地體會(huì)到了數(shù)據(jù)挖掘強(qiáng)有力的發(fā)展前景。數(shù)據(jù)挖掘這個(gè)領(lǐng)域應(yīng)用最多的就是算法，掌握算法的意義就抓住了數(shù)據(jù)挖掘的核心。如今，雖然數(shù)據(jù)挖掘技術(shù)的應(yīng)用相當(dāng)廣泛，但是就算法而言其本質(zhì)并未發(fā)生改變?，F(xiàn)今運(yùn)用的都是一些比較經(jīng)典的算法，如傳統(tǒng)的決策樹算法等，同時(shí)這些算法也是學(xué)習(xí)數(shù)據(jù)挖掘算法的根基。文中主要列舉相關(guān)算法并應(yīng)用相應(yīng)的實(shí)例加以佐證，指出其中的不足和需要改進(jìn)的地方，以此讓讀者更容易理解各種算法的原理和運(yùn)行流程。

關(guān)鍵詞：數(shù)據(jù)挖掘;決策樹算法;算法原理;算法改進(jìn)

中圖分類號(hào)：TP312? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）24-0086-03

Abstract：Data mining is an enduring subject for current students. For those who are worked in data mining，they have a deep understanding of the strong development prospects of data mining. Algorithms are the most widely used in the field of data mining. The people who grasp the meaning of algorithm then grasp the core of data mining. In the new era，although the application of data mining technology is quite extensive，its essence has not changed even in law. Nowadays，some classical algorithms are used，such as the traditional decision tree algorithm，but these algorithms are also the foundation of learning data mining algorithms. This paper mainly lists the related algorithms and proves them with corresponding examples，It also points out the shortcomings and the areas needing improvement，this will make it easier for readers to understand the principles and operating procedures of various algorithms.

Keywords：data mining;decision tree algorithms;algorithm principle;algorithm improvement

0? 引? 言

近年來，數(shù)據(jù)挖掘（Data Mining）這門綜合性很強(qiáng)的學(xué)科發(fā)展迅速，就其本身而言涉及很多領(lǐng)域的知識(shí)，如對(duì)于模式識(shí)別而言，在識(shí)別一組圖像、文字或者語言的時(shí)候，我們可以提取其中的相關(guān)特征來達(dá)到找出想要信息的目的。就機(jī)器學(xué)習(xí)這個(gè)領(lǐng)域來說，算法是它的內(nèi)在本質(zhì)，這與數(shù)據(jù)挖掘技術(shù)也是脫不了關(guān)系的。不僅如此，數(shù)據(jù)挖掘還涉及數(shù)據(jù)庫技術(shù)、統(tǒng)計(jì)學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)和可視化分析?？梢哉f數(shù)據(jù)挖掘技術(shù)與人們的生活密不可分。

1? 數(shù)據(jù)挖掘的定義及過程

就數(shù)據(jù)挖掘的定義而言，可以用一個(gè)例子加以說明：例如想對(duì)在某網(wǎng)絡(luò)平臺(tái)購買某一商品的人數(shù)進(jìn)行分析，首先應(yīng)該明白我們需要的是什么數(shù)據(jù)，有用的數(shù)據(jù)需要具備哪些特征，之后需要從大量信息中找出具備這些特征的信息。因此可以利用一些基本的輔助工具如Python編輯一些搜集信息的程序，在搜集信息之前可以設(shè)定被搜集信息的屬性，當(dāng)數(shù)據(jù)提取完畢之后需要對(duì)數(shù)據(jù)進(jìn)行一定的處理，因?yàn)樗鸭臄?shù)據(jù)難免會(huì)有各種問題，把無用的信息剔除，保留有用信息，進(jìn)而可以得到我們想要的信息。這個(gè)過程可以稱之為數(shù)據(jù)挖掘，它可以整合分析所得到的數(shù)據(jù)。

數(shù)據(jù)挖掘的過程主要包括以下幾個(gè)方面：（1）首先清楚客戶想要什么。在大量數(shù)據(jù)中搜集相關(guān)信息，認(rèn)清所要解決的問題;（2）建立一個(gè)統(tǒng)一的數(shù)據(jù)挖掘庫。在對(duì)信息收集時(shí)，不同信息的來源是不同的，難免要對(duì)數(shù)據(jù)進(jìn)行一些基本的操作，而把數(shù)據(jù)放在一個(gè)統(tǒng)一的數(shù)據(jù)庫中方便對(duì)數(shù)據(jù)的修改和維護(hù)運(yùn)用;（3）對(duì)收集的數(shù)據(jù)進(jìn)行壓縮處理。一般情況下，收集的數(shù)據(jù)都是比較多的，大量的數(shù)據(jù)會(huì)使程序的運(yùn)行效率降低，提高程序運(yùn)行效率的唯一辦法就是減小數(shù)據(jù)量，對(duì)數(shù)據(jù)進(jìn)行壓縮;（4）對(duì)所用的數(shù)據(jù)進(jìn)行清理。剔除不必要的信息，對(duì)空白數(shù)據(jù)進(jìn)行補(bǔ)全;（5）整理分析數(shù)據(jù)。在將數(shù)據(jù)變換為可用形式之后選擇合適的工具和算法對(duì)數(shù)據(jù)進(jìn)行處理得出有價(jià)值的信息;（6）對(duì)挖掘結(jié)果進(jìn)行評(píng)估。

2? 常用的數(shù)據(jù)挖掘算法

2.1? ID3算法

ID3算法采用信息增益作為屬性計(jì)算的一種方式，總會(huì)選擇結(jié)果相對(duì)較大的一個(gè)屬性，它是一種相對(duì)經(jīng)典的決策樹算法，同時(shí)也是一種遍歷選擇最優(yōu)的算法。ID3屬于分類算法的一種，因此在建立決策樹模型時(shí)該算法首先會(huì)計(jì)算各個(gè)屬性的信息增益，以此來作為屬性選擇的判斷條件。現(xiàn)有一個(gè)數(shù)據(jù)集用A表示，樣本集中存在多個(gè)屬性，但我們只需要其中的屬性B，所以在用ID3算法運(yùn)行此數(shù)據(jù)集時(shí)會(huì)以屬性B作為分割樣本的判斷條件，則按B屬性劃分后的信息增益為：

如表1所示，我們?yōu)檠芯可砀摺㈤L相、體型、收入與一個(gè)人是否受歡迎之間的關(guān)系，在學(xué)校周邊進(jìn)行隨機(jī)采訪，此次采訪只限男性，共采訪三十位隨機(jī)路人。針對(duì)此次采訪制作采訪結(jié)果表格，并把采訪到的數(shù)據(jù)存放其中制作成一個(gè)小數(shù)據(jù)集，現(xiàn)只截取部分?jǐn)?shù)據(jù)，用ID3算法來構(gòu)建其決策樹模型，并根據(jù)其決策樹模型畫出決策樹。

現(xiàn)根據(jù)身高、長相、收入、體型四個(gè)特征來判斷此人是否受歡迎，表1就是一個(gè)小型的數(shù)據(jù)集，我們使用ID3算法來構(gòu)建它的決策樹模型并以此來畫出此數(shù)據(jù)集的決策樹。實(shí)驗(yàn)運(yùn)行的環(huán)境為：Windows 7、Python 3.7、Intel i54210-U以及4G內(nèi)存。其決策樹模型為：

由以上實(shí)驗(yàn)可以看出雖然ID3算法會(huì)選擇信息增益相對(duì)較大的屬性，但信息增益有其本身的缺點(diǎn)，即會(huì)不經(jīng)易間選擇一些無用的信息，這使得其中有價(jià)值的信息大大減少，這種局限性也使得ID3這種算法只能用于分類。

2.2? C4.5算法

C4.5算法相對(duì)于ID3算法而言更實(shí)用一點(diǎn)，它應(yīng)用到分類的思想，同時(shí)也可以根據(jù)決策樹模型畫出決策樹。信息增益的計(jì)算是在ID3算法中最重要的應(yīng)用，而在C4.5算法中則不同，它更細(xì)化了選擇屬性的計(jì)算過程——采用信息增益率進(jìn)行選擇。同時(shí)，在其原始計(jì)算代碼中也多出了計(jì)算信息增益率的公式，這也使得C4.5算法克服了ID3算法中使用信息增益作為特征判斷條件時(shí)帶來諸多無價(jià)值信息的不足。信息增益率定義為：

在對(duì)缺失值的處理方面C4.5算法也有自己的方法，如k為樣本集A中的一個(gè)實(shí)例，在給定屬性的情況下，若在節(jié)點(diǎn)c中有8個(gè)為該屬性，剩下2個(gè)為非該屬性，則該屬性在樣本集占比為80%，于是實(shí)例的80%被分配到占比較多的一方，這就是C4.5處理缺失值的方法。

現(xiàn)有數(shù)據(jù)如表1，我們用C4.5算法根據(jù)身高、長相、收入、體型等特征來判斷他的受歡迎程度，并構(gòu)建決策樹模型。首先根據(jù)數(shù)據(jù)運(yùn)行出小數(shù)據(jù)集的決策樹模型：C4.5算法對(duì)ID3算法加以改進(jìn)有其自身的優(yōu)勢。就算法本身而言，C4.5的準(zhǔn)確率是相對(duì)較高的，但由于要對(duì)現(xiàn)有的數(shù)據(jù)集執(zhí)行多次命令，其花費(fèi)的時(shí)間也相對(duì)較多，所以此算法在效率上欠佳，同時(shí)由于其計(jì)算機(jī)制的問題，在樣本屬性的選擇上也會(huì)存在一定的誤差。

2.3? K-Means算法

K-Means（K-Means Clustering）算法是一種無監(jiān)督式的學(xué)習(xí)算法，同時(shí)也是一種使用廣泛，較為受歡迎的算法。所謂聚類就是把屬性相同或者類似的數(shù)據(jù)放在一起構(gòu)成一個(gè)簇?cái)?shù)據(jù)集合，若能達(dá)到集合內(nèi)差異性較低而集合間差異性較高的話就是一個(gè)好的聚類。K-Means算法的原理也相對(duì)較容易理解，首先隨機(jī)選取k個(gè)種子點(diǎn)作為原始的中心點(diǎn)，之后依次計(jì)算各個(gè)樣本點(diǎn)到種子點(diǎn)的歐氏距離，若該點(diǎn)到原始中心點(diǎn)的距離近，則該點(diǎn)屬于此原始中心點(diǎn)的數(shù)據(jù)集合，之后這個(gè)點(diǎn)移動(dòng)到數(shù)據(jù)集合的中心，同樣計(jì)算它到各點(diǎn)的歐氏距離，直到中心點(diǎn)不再移動(dòng)。K-Means算法可以直觀地反映出研究者所想要的信息，下面用一組數(shù)據(jù)加以說明。若把某一地區(qū)當(dāng)作一個(gè)二維平面圖建立坐標(biāo)系，以蜜蜂的所在區(qū)域研究該地區(qū)的蜜蜂分布情況，用K-Means算法對(duì)數(shù)據(jù)集進(jìn)行處理后得到的試驗(yàn)結(jié)果如圖3所示。

雖然K-Means算法的原理很容易被人理解，在某些簇間差異相對(duì)明顯的情況下效果較好，但是這種算法也存在明顯的缺點(diǎn)。K-Means算法的結(jié)果與最開始中心點(diǎn)的選擇關(guān)系密不可分，初始點(diǎn)的選擇不合適會(huì)導(dǎo)致最后的結(jié)果較差，因此需要做大量的工作來確定最開始中心點(diǎn)的取值。

3? 結(jié)? 論

經(jīng)過詳細(xì)介紹了三種常用的數(shù)據(jù)挖掘算法，旨在使學(xué)者更加容易地理解和學(xué)習(xí)，在此基礎(chǔ)上才能對(duì)各種數(shù)據(jù)挖掘算法有更深入的了解。首先，在ID3算法的試驗(yàn)中我們使用了四種屬性構(gòu)建了判斷一個(gè)人是否受歡迎的決策樹，同時(shí)也分析了ID3算法的不足之處。之后介紹了ID3的改進(jìn)算法C4.5，在相同的試驗(yàn)中采用C4.5算法去運(yùn)行相同的數(shù)據(jù)集，得出比ID3更確切的決策樹，同時(shí)也指出C4.5算法需要改進(jìn)的地方。最后使用K-Means算法聚類蜜蜂的分布情況。各試驗(yàn)步驟詳細(xì)原理清楚，不足之處在于在聚類蜜蜂的分布情況時(shí)建立的坐標(biāo)系精度不夠準(zhǔn)確，使最后的結(jié)果存在一定的誤差，在此基礎(chǔ)上尚可改進(jìn)。

參考文獻(xiàn)：

[1] 楊秀港.數(shù)據(jù)挖掘算法綜述 [J].科技經(jīng)濟(jì)導(dǎo)刊，2019，27（5）：166.

[2] 蔡萌萌，張巍巍，王泓霖.大數(shù)據(jù)時(shí)代的數(shù)據(jù)挖掘綜述 [J].價(jià)值工程，2019，38（5）：155-157.

[3] 王宇翔.大數(shù)據(jù)背景下的數(shù)據(jù)挖掘算法綜述 [J].通訊世界，2018（11）：21-22.

[4] 楊小平.數(shù)據(jù)挖掘三大經(jīng)典算法在交通領(lǐng)域的應(yīng)用綜述 [J].物聯(lián)網(wǎng)技術(shù)，2018，8（11）：42-44+48.

[5] 劉維.數(shù)據(jù)挖掘中聚類算法綜述 [J].江蘇商論，2018（7）：120-125.

[6] 王雅軒，頊聰.數(shù)據(jù)挖掘技術(shù)的綜述 [J].電子技術(shù)與軟件工程，2015（8）：204-205.

[7] 周麗英.面向軟件開發(fā)信息庫的數(shù)據(jù)挖掘綜述 [J].中國管理信息化，2016，19（12）：184.

[8] 梁辰，陳明浩.數(shù)據(jù)挖掘ID3分類算法研究綜述 [J].信息通信，2015（5）：26-28.

作者簡介：姚奇峰（1991-），男，漢族，河北邢臺(tái)人，碩士，研究方向：計(jì)算機(jī)技術(shù)，數(shù)據(jù)挖掘;楊連賀（1965-），男，漢族，天津人，教授，博士，博導(dǎo)，研究方向：數(shù)據(jù)挖掘。