大數(shù)據(jù)挖掘中的數(shù)據(jù)分類算法綜述

尹廷鈞 李靈慧 周蕊

(戰(zhàn)略支援部隊(duì)信息工程大學(xué),河南鄭州 450002)

0 引言

數(shù)據(jù)分類算法是大數(shù)據(jù)挖掘的核心內(nèi)容,其主要作用是通過對海量無序數(shù)據(jù)進(jìn)行大量運(yùn)算,提取價(jià)值的知識和信息,分析出各類信息的特征,為研究者進(jìn)一步預(yù)測某一趨勢提供數(shù)據(jù)基礎(chǔ)。隨著數(shù)據(jù)挖掘技術(shù)的廣泛應(yīng)用,數(shù)據(jù)分類算法不斷涌現(xiàn)并逐步優(yōu)化完善,其中經(jīng)典的分類算法有決策樹分類算法、樸素貝葉斯算法、支持向量機(jī)分類算法、人工神經(jīng)網(wǎng)絡(luò)分類算法等。

1 大數(shù)據(jù)的特點(diǎn)及意義

大數(shù)據(jù)作為一種抽象的概念,簡單來說就是對海量數(shù)據(jù)信息進(jìn)行挖掘整合,這些數(shù)據(jù)類型多樣、數(shù)據(jù)量巨大、價(jià)值密度低、增長速度快,只有對這些其進(jìn)行合理的數(shù)據(jù)挖掘和數(shù)據(jù)分析才能發(fā)掘其背后的應(yīng)用價(jià)值。伴隨著各行業(yè)生產(chǎn)發(fā)展,每天都會有大量的數(shù)據(jù)產(chǎn)生,通過大數(shù)據(jù)技術(shù),這些信息在潛移默化中影響著人們當(dāng)前的生活乃至某一行業(yè)的發(fā)展。大數(shù)據(jù)的數(shù)據(jù)類型種類繁雜,數(shù)據(jù)容量巨大,可以分為結(jié)構(gòu)化的數(shù)據(jù)信息和非結(jié)構(gòu)化的數(shù)據(jù)信息以及半結(jié)構(gòu)化數(shù)據(jù)信息,如圖片、聲音、視頻等,這些生成的大量數(shù)據(jù)信息其單條信息價(jià)值很低,傳統(tǒng)的分析工具需要大量時(shí)間效率很低,必須輔以能夠?qū)ζ淇焖偬幚淼拇髷?shù)據(jù)技術(shù)。大數(shù)據(jù)能夠幫助其更好挖掘出數(shù)據(jù)價(jià)值意義所在,對行業(yè)當(dāng)前發(fā)展的現(xiàn)狀進(jìn)行分析,從而能夠更好的預(yù)測到未來發(fā)展趨勢,給日后管理工作開展提供依據(jù)。

2 大數(shù)據(jù)挖掘中的分類問題

大數(shù)據(jù)挖掘技術(shù)主要是從海量信息數(shù)據(jù)中按照某一指定的屬性對數(shù)據(jù)信息進(jìn)行采集、劃分,逐步獲取并積累一些有效信息的過程。數(shù)據(jù)挖掘技術(shù)作為大數(shù)據(jù)時(shí)代網(wǎng)絡(luò)信息技術(shù)發(fā)展的產(chǎn)物,主要涉及人工智能、數(shù)據(jù)庫、統(tǒng)計(jì)學(xué)等,所涉及研究內(nèi)容比較多,其中比較重要的一個(gè)研究分支就是分類。數(shù)據(jù)分類是進(jìn)行數(shù)據(jù)解析并取得正確分析結(jié)果的基礎(chǔ)。數(shù)據(jù)的分類過程一般包含兩步,第一步是通過一個(gè)已知類標(biāo)號的數(shù)據(jù)訓(xùn)練集來構(gòu)造模型,這一步常被稱作訓(xùn)練階段,可以理解為訓(xùn)練一種分類器;第二步是用該模型對某未知類標(biāo)號的對象進(jìn)行分類。由該過程我們可以知道,分類模型不僅要擬合已知數(shù)據(jù)集,更重要的是要能準(zhǔn)確預(yù)測未知對象。不同的分類算法有著適用于不同的應(yīng)用場景,分類算法的差異會模擬出不同分類器,將會直接影響到分類的精準(zhǔn)性,最終影響數(shù)據(jù)分析。因此對規(guī)模系統(tǒng)比較復(fù)雜或數(shù)據(jù)信息量比較大的數(shù)據(jù)實(shí)施深度分類,對分類算法進(jìn)行合理的選擇,都對任務(wù)完成產(chǎn)生重要的影響。當(dāng)前國內(nèi)和國外的計(jì)算機(jī)數(shù)據(jù)學(xué)領(lǐng)域在大數(shù)據(jù)挖掘技術(shù)中與之有關(guān)的分類算法研究主要匯集在下面兩方面:一類是把傳統(tǒng)化分類算法直接應(yīng)用在實(shí)際的案例中,或者把傳統(tǒng)的算法做出簡單的組合,再將其應(yīng)用在實(shí)際的案例中。另一類是把利用新技術(shù)新思想對傳統(tǒng)的分類算法進(jìn)行改進(jìn)升級。如何在實(shí)際應(yīng)用種選擇合適的分類算法,下面對幾種經(jīng)典分類算法進(jìn)行描述分析,總結(jié)出各種算法的特點(diǎn)、優(yōu)勢、缺點(diǎn)供大家參考。

3 數(shù)據(jù)挖掘中常用分類算法分析

當(dāng)前在大數(shù)據(jù)分析和數(shù)據(jù)挖掘階段經(jīng)典的分類算法主要有為決策樹、樸素貝葉斯、支持向量機(jī)(SVM)、神經(jīng)網(wǎng)絡(luò)分類算法等。

3.1 決策樹分類算法

決策樹(decision tree)分類算法是歸納學(xué)習(xí)算法中的一種,主要是指從一系列無規(guī)則、無順序的樣本數(shù)據(jù)信息中推理出“樹”型結(jié)構(gòu)來進(jìn)行預(yù)測的分類規(guī)則。決策樹分類算法能以直觀的方式展現(xiàn)整個(gè)決策過程中的不同時(shí)期決策類的問題和關(guān)鍵點(diǎn)。決策樹由根節(jié)點(diǎn)(root node)、內(nèi)部節(jié)點(diǎn)(internal node)、葉子節(jié)點(diǎn)(leaf node)及連接節(jié)點(diǎn)的有向邊構(gòu)成。根節(jié)點(diǎn)是唯一的,表示待分類的樣本集合;內(nèi)部節(jié)點(diǎn)表示特征屬性;葉子節(jié)點(diǎn)表示分類結(jié)果。算法決策過程從根節(jié)點(diǎn)開始,根據(jù)待分類集合中相應(yīng)的屬性值,由上而下選擇分支到達(dá)相應(yīng)節(jié)點(diǎn),重復(fù)此步驟直到到達(dá)葉子節(jié)點(diǎn),葉子節(jié)點(diǎn)存放的類別作為分類結(jié)果。例如某人到銀行申請貸款,銀行根據(jù)申請人年收入、房產(chǎn)情況、婚姻情況等條件進(jìn)行判斷劃分,從而是否批準(zhǔn)其貸款申請。這個(gè)過程我們可以采取決策樹的形式進(jìn)行表達(dá),如圖1所示。

圖1 決策樹分類算法流程示例Fig.1 Flow example of decision tree classification algorithm

目前決策樹算法種類比較多,典型算法有ID3、C4.5、CART算法等,其中C4.5是對ID3的優(yōu)化改進(jìn)。與其他類型分類的算法進(jìn)行對比分析,決策樹算法主要有下面的優(yōu)點(diǎn):第一,決策樹算法邏輯清晰、層次分明、直觀,其分類規(guī)則便于人們的理解和實(shí)現(xiàn),是一個(gè)相對友好的分類算法。第二,決策樹算法分類精度高,采用決策樹分類算法在數(shù)據(jù)的挖掘過程中,每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)分類規(guī)則,可以準(zhǔn)確將每個(gè)數(shù)據(jù)分類到葉節(jié)點(diǎn)。第二,決策樹算法運(yùn)行高效,用時(shí)較少。除此之外,決策樹的分類算法在應(yīng)用階段雖然說有著諸多的優(yōu)點(diǎn),但也會出現(xiàn)過度擬合等問題。在生成決策樹時(shí),當(dāng)完全依照訓(xùn)練集時(shí),如果訓(xùn)練集中有噪音樣本,在對訓(xùn)練集進(jìn)行擬合的同時(shí)也會對噪音擬合,從而使分類模型過于復(fù)雜,分支過多,有些分支時(shí)屬于訓(xùn)練樣本自身特有的,不具有代表性,從而在測試階段出現(xiàn)過度擬合的情況,導(dǎo)致模型的準(zhǔn)確性低[1]。我們需要根據(jù)選擇的分類算法進(jìn)行屬性離散化或預(yù)排序,盡可能的實(shí)現(xiàn)分類和學(xué)習(xí)。避免發(fā)生類別較多或較少,造成過度擬合的情況等情況影響預(yù)測精度。基于其決策樹優(yōu)劣分析,專家學(xué)者對其進(jìn)行改進(jìn),在形成決策樹和建設(shè)決策樹的過程中,通常采用剪枝的方式來減少噪聲對分類的影響。如果特征數(shù)量很多,需要在建立決策樹后基于全局考慮對沒有足夠分類能力的特征進(jìn)行剪枝,減少模型的復(fù)雜度,使決策樹具備更好的泛化能力。剪枝有兩種方法:一種稱為事先剪枝法,即在構(gòu)造樹的過程時(shí)提前停止。比如提前設(shè)置決策樹最大深度或者對樣本集中某以特征屬性預(yù)先設(shè)定約束條件等。另一種稱為事后剪枝法,即整個(gè)樹生成之后判斷某些分支是否需要變?yōu)楣?jié)點(diǎn)而進(jìn)行修剪[2]。剪枝要適度,既要避免出現(xiàn)過擬合,也要避免出現(xiàn)欠擬合的情況。

3.2 樸素貝葉斯算法

樸素貝葉斯算法屬于監(jiān)督學(xué)習(xí)中的常用算法,這個(gè)算法的操作和原理都是比較簡單的,主要是基于著名的貝葉斯公式:

通過先驗(yàn)概率與條件概率解決后驗(yàn)概率的問題[3]。假設(shè)樣本數(shù)據(jù)集的各特征屬性之間是相互獨(dú)立的,當(dāng)條件獨(dú)立性假設(shè)成立時(shí),已知訓(xùn)練樣本中的分類概率P(y1)、P(y2)…P(yn),通過計(jì)算已知分類的特征屬性的概率P(x1,x2...xn|y1),P(x1,x2...xn|y2)...P(x1,x2...xn|yn),進(jìn)而預(yù)測具備待特征屬性數(shù)據(jù)的分類,即比較P(y1|x1,x2...xn)、P(y2|x1,x2...xn)…P(yn|x1,x2...xn)其中概率最大的作為該對象的分類。公式最終可變成:

樸素貝葉斯分類算法操作特點(diǎn)主要有下面幾點(diǎn):第一,樸素貝葉斯算法邏輯思想十分簡單,有著較強(qiáng)的可操作性和可行性。第二,樸素貝葉斯算法較為穩(wěn)定,不會因數(shù)據(jù)自身呈現(xiàn)的特點(diǎn)不同而對分類結(jié)果產(chǎn)生較大影響。第三,樸素貝葉斯數(shù)據(jù)之間獨(dú)立性越強(qiáng),其分類結(jié)果越準(zhǔn)確。但我們需要注意的是該分類算法需要基于條件獨(dú)立性假設(shè)的前提,這是一個(gè)理想狀態(tài),在實(shí)際應(yīng)用中數(shù)據(jù)屬性間會存在聯(lián)系,從而降低了分類準(zhǔn)確性,因此該方法往往在效果上難以達(dá)到理論上的最大值。可以通過擴(kuò)大樣本訓(xùn)練集來獲得類別總體的概率分布和各類樣本的概率分布函數(shù)。另外在分類器測試階段,如果測試樣本中出現(xiàn)了訓(xùn)練集中沒有的特征屬性,那么不管如何計(jì)算所有類別的概率都會是0,這時(shí)候需要進(jìn)行平滑處理每個(gè)樣本值加1,計(jì)算概率時(shí)在分子加1,分母加N*1,這種方式我們成為稱為普拉斯平滑處理,實(shí)際的使用時(shí)可以用lambda(1≥lambda≥0)來代替簡單加1。另外一個(gè)我們可能遇到的問題是在求乘積時(shí),由于概率小于1,小于1的兩數(shù)相乘結(jié)果會更更小,甚至在四舍五入后直接變?yōu)? 出現(xiàn)下溢的情況,這時(shí)候需要對乘積結(jié)果取自然對數(shù)以解決此類問題。

3.3 基于神經(jīng)網(wǎng)絡(luò)的分類

神經(jīng)網(wǎng)絡(luò)是指人工神經(jīng)網(wǎng)絡(luò),以網(wǎng)絡(luò)拓?fù)渲R為基礎(chǔ)模擬人腦的結(jié)構(gòu)及功能形成一種有效運(yùn)算模型,主要包含輸入層、隱藏層、輸出層三部分。神經(jīng)網(wǎng)絡(luò)是由大量節(jié)點(diǎn)相互連接構(gòu)成,每個(gè)節(jié)點(diǎn)代表一種特定輸出函數(shù),每兩個(gè)節(jié)點(diǎn)間的連接都代表通過該連接信號的加權(quán)值,即權(quán)重。每層節(jié)點(diǎn)對輸入信息的加權(quán)求和并進(jìn)行非線性變換后輸出,其輸出值作為下一層的輸入值,以此類推直到最后分類節(jié)點(diǎn)[4]。常見的神經(jīng)網(wǎng)絡(luò)類別有單層神經(jīng)網(wǎng)絡(luò)、兩層神經(jīng)網(wǎng)絡(luò)、多層神經(jīng)網(wǎng)絡(luò)、卷積神經(jīng)網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)階段通過調(diào)整各連接權(quán)重來實(shí)現(xiàn)最終輸出值與真實(shí)值逐漸接近,最終達(dá)到準(zhǔn)確模型。神經(jīng)網(wǎng)絡(luò)訓(xùn)練完畢后對輸入信息進(jìn)行動態(tài)響應(yīng)進(jìn)而從輸出端得到分類結(jié)果。神經(jīng)網(wǎng)絡(luò)分類算法較多的,B P 神經(jīng)網(wǎng)絡(luò)、R B F神經(jīng)網(wǎng)絡(luò)、自組織特征映射神經(jīng)網(wǎng)絡(luò)、學(xué)習(xí)矢量化神經(jīng)網(wǎng)絡(luò),目前使用較廣泛的是BP神經(jīng)網(wǎng)絡(luò)。神經(jīng)網(wǎng)絡(luò)分類算法主要特點(diǎn)有:第一,神經(jīng)網(wǎng)絡(luò)具備很強(qiáng)的學(xué)習(xí)能力。第二,由于權(quán)值的作用,神經(jīng)網(wǎng)絡(luò)在有噪聲的環(huán)境具有更好的魯棒性。第三,人工神經(jīng)網(wǎng)絡(luò)分類算法對未經(jīng)訓(xùn)練的數(shù)據(jù)也具有較好的預(yù)測分類能力。第四,因?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)是非線性模型,能夠適應(yīng)各種復(fù)雜的數(shù)據(jù)關(guān)系。同時(shí)人工神經(jīng)網(wǎng)絡(luò)分類算法缺陷也比較突出,主要是神經(jīng)網(wǎng)絡(luò)自身的建立問題。建設(shè)出一個(gè)比較完整的神經(jīng)網(wǎng)絡(luò),學(xué)習(xí)過程較長,而且激活函數(shù)、優(yōu)化函數(shù)、損失函數(shù)的選擇與組合也會影響最終模型的準(zhǔn)確性,工作難度也比較大。有學(xué)者提出在提取神經(jīng)規(guī)則之前對網(wǎng)絡(luò)進(jìn)行剪枝以刪除對分類準(zhǔn)確性影響程度可忽略不計(jì)的神元和鏈枝,從而簡化神經(jīng)網(wǎng)絡(luò)。其次與決策樹分類算法相比神經(jīng)網(wǎng)絡(luò)可解釋性差,對于非技術(shù)用戶可能是較困難的事情。

3.4 基于統(tǒng)計(jì)學(xué)習(xí)理論的支持向量機(jī)分類算法

支持向量機(jī)(Support Vector Machines,SVM)是一種兩分類模型,其目標(biāo)是尋找一個(gè)滿足分類條件的最優(yōu)超平面,使得其能將兩類樣本分開,并且與兩類樣本的分類間隔最大。SVM是針對兩分類問題提出的,而在實(shí)際應(yīng)用中多類分類問題更為普遍。對于非線性分類問題,首先選擇合適的核函數(shù)將樣本空間映射到能線性可分的高維空間,然后利用最大化間隔的方法獲取間隔最大的分割線,得出支持向量,最后利用分割線和支持向量對新的樣本進(jìn)行分類預(yù)測[5]。典型的算法有選塊算法、分解算法、模糊支持向量機(jī)算法等。SVM算法的優(yōu)點(diǎn)有:第一SVM算法對特征相關(guān)性不敏感,不需要特征獨(dú)立性。第二SVM可以處理非線性數(shù)據(jù)集,可以用于處理文本分類、圖像檢測、人臉識別等問題。SVM算法缺點(diǎn)主要有:第一算SVM算法較為復(fù)雜,核函數(shù)參數(shù)選擇困難。第二當(dāng)樣本數(shù)據(jù)較大時(shí),需要較長的訓(xùn)練時(shí)間,效率較低。

4 結(jié)語

總的來說,經(jīng)過系統(tǒng)化研究數(shù)據(jù)挖掘分類算法的方式,有助于我們了解掌握決策樹分類算法、樸素貝葉斯分類算法、支持向量機(jī)分類算法、神經(jīng)網(wǎng)絡(luò)分類算法優(yōu)缺點(diǎn)、適用場景,有針對性的進(jìn)行缺點(diǎn)的優(yōu)化改進(jìn)。當(dāng)然現(xiàn)階段分類算法種類很多,需要我們不斷總結(jié)研究。