孫健

摘 要：隨著計(jì)算機(jī)科學(xué)技術(shù)快速發(fā)展，人們對于信息價(jià)值的認(rèn)識逐漸提高。在此背景下，數(shù)據(jù)挖掘?qū)τ谌藗儚暮Ａ繑?shù)據(jù)信息流中提取價(jià)值信息有著十分重要的作用。而在KDD處理整個(gè)過程中，特征選擇尤為關(guān)鍵，通常特征選擇方式包含過濾、包裝兩種。本文就特征選擇算法的搜索方向及策略、評價(jià)方法、停止標(biāo)準(zhǔn)對特征選擇兩種模式以及幾種具有代表性的特征選擇算法，對數(shù)據(jù)挖掘特征以及相關(guān)技術(shù)進(jìn)行了一定程度的研究。

關(guān)鍵詞：數(shù)據(jù)挖掘 特征選擇 知識發(fā)現(xiàn) 算法 信息處理

中圖分類號：TP3 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2018）11（a）-00-02

隨著社會(huì)和經(jīng)濟(jì)的快速進(jìn)步，計(jì)算機(jī)科學(xué)技術(shù)發(fā)展日新月異，當(dāng)前，人們已然進(jìn)入到大數(shù)據(jù)時(shí)代。當(dāng)前，在海量的數(shù)據(jù)信息洪流中，如何提取、發(fā)現(xiàn)有價(jià)值的數(shù)據(jù)信息顯得尤為關(guān)鍵，數(shù)據(jù)挖掘就是在這種背景下產(chǎn)生的。在數(shù)據(jù)挖掘中，特征選擇是一個(gè)極為重要的研究方向，其能夠從原始特征集合中選擇最優(yōu)的特征子集，進(jìn)而提高數(shù)據(jù)質(zhì)量以及挖掘效率。因此，對數(shù)據(jù)挖掘特征選擇及其算法進(jìn)行研究充滿了必要性。

1 特征選擇概述

所謂特征選擇，其指的是在為特定應(yīng)用不丟失數(shù)據(jù)原始價(jià)值的前提下選擇最優(yōu)的屬性子集，去除不相關(guān)的或是冗余的過程。由于數(shù)據(jù)分析過程中數(shù)據(jù)特征千變?nèi)f化，很多特征和數(shù)據(jù)挖掘任務(wù)不相關(guān)，通過特征選擇能夠有效提高數(shù)據(jù)質(zhì)量，提高數(shù)據(jù)挖掘效率，并使得挖掘出的規(guī)則更容易被人們理解。在知識發(fā)現(xiàn)（KDD）過程中，特征選擇極為重要，其為后期數(shù)據(jù)信息的預(yù)處理、挖掘以及后處理有著十分關(guān)鍵的意義[1]。

2 特征選擇種類

特征選擇種類主要分為包裝（Wrapper）算法以及過濾（Filter）算法，其中Wrapper算法一般情況下和一種特定分類算法包裝在一起，在初始化中其設(shè)定目標(biāo)特征集和為空集，然后根據(jù)選定的特征評價(jià)標(biāo)準(zhǔn)在每一步中選擇原始特征評價(jià)最優(yōu)的特征，并把其增加到目標(biāo)集合里。在后面的每一次迭代中，其把原始特征集余下的特征里的最優(yōu)特征增加到目標(biāo)集合里，一直到最終獲取滿意的目標(biāo)特征集合。而Filter算法在初始化中將目標(biāo)特征集合設(shè)定為整個(gè)特殊集，然后根據(jù)選定的特征評價(jià)標(biāo)準(zhǔn)在每一步中不斷去除評價(jià)最壞的特征，一直到最終目標(biāo)特征集合符合要求后結(jié)束。通常來講，Wrapper算法分類精度相對較高，但是相比于Filter算法，其計(jì)算過程較長，因此不太適用于大規(guī)模的數(shù)據(jù)信息處理。而Filter算法則忽視了所選特征子集在分類算法上性能表現(xiàn)會(huì)造成分類性能降低[2]。

3 特征選擇算法研究

隨著數(shù)據(jù)信息規(guī)模急劇提升，當(dāng)前，人們在進(jìn)行數(shù)據(jù)挖掘時(shí)必須通過特征選擇算法約減數(shù)據(jù)規(guī)?；蛘吒淖償?shù)據(jù)結(jié)構(gòu)，進(jìn)而提高數(shù)據(jù)挖掘效率或者提高分類能力。當(dāng)前，特征選擇算法已經(jīng)廣泛應(yīng)用于網(wǎng)絡(luò)安全信息挖掘、商業(yè)金融、生物醫(yī)學(xué)以及文本識別等領(lǐng)域，并取得顯著成果。一般情況下，特征選擇算法在特征子集空間中進(jìn)行搜索時(shí)，其主要考慮以下幾點(diǎn)：搜索方向、搜索策略、評價(jià)方法、停止標(biāo)準(zhǔn)，以下筆者將就這4個(gè)方面對特征算法中比較有代表性的ABB算法、Relief算法以及LVW算法進(jìn)行一定程度研究，并分析每種算法的特征[3]。

3.1 ABB算法

ABB算法在搜索方向上是采用后向搜到，即深度優(yōu)化；在評價(jià)方法上采用一致性方法；搜索策略上其采用完全搜索，即在搜索中采用啟發(fā)性信息；在停止標(biāo)準(zhǔn)上，當(dāng)無法再找到符合一致性要求的更優(yōu)屬性子集時(shí)即停止算法。ABB算法在進(jìn)行過程中，其不斷推展搜索規(guī)模，同時(shí)，其又對搜索空間不斷進(jìn)行裁剪，由于其搜索策略采用完全搜索，一致性搜到單調(diào)性能夠大幅度降低搜索屬性子集的搜索范圍。ABB算法雖然沒有對全集當(dāng)中的所有子集進(jìn)行搜索，但是其能夠保證沒有評價(jià)的子集是不符合搜到要求的，因此，其屬于完全搜索[4]。

3.2 Relief算法

Relief算法主要用來處理屬性關(guān)聯(lián)的問題，其能夠以統(tǒng)計(jì)相關(guān)性為基礎(chǔ)選擇屬性，并采樣實(shí)例集合，計(jì)算所有屬性的權(quán)重。Relief算法理念在于其將相關(guān)屬性視為相鄰的類型不同的實(shí)例間取值不同的屬性。針對數(shù)據(jù)集中實(shí)例M，通過發(fā)現(xiàn)與其相近的類別相同的實(shí)力L和類別不同的實(shí)例N。在理想狀態(tài)下，相關(guān)屬性應(yīng)與M里的取值和L里的取值相同，但是不同于N里面的取值。在算法實(shí)際運(yùn)行中，計(jì)算單一屬性在M、L、N之間的距離能夠獲取該屬性的相關(guān)性。在隨機(jī)選取的實(shí)例中，每一個(gè)屬性的距離值分別累加到和條件屬性維數(shù)一樣的權(quán)重向量里。當(dāng)權(quán)重值高于門限值的即為相關(guān)屬性，其中，門限值的決定采用區(qū)間估計(jì)統(tǒng)計(jì)方法。隨機(jī)抽樣的尺寸可以發(fā)生變化，而且尺寸越大最后獲取的結(jié)果可靠性越高。在處理離散和連續(xù)的數(shù)據(jù)時(shí)通常采用Relief算法，但是在解決冗余數(shù)據(jù)任務(wù)時(shí)Relief算法很難起到作用，因此Relief算法選擇的特征子集并非為最優(yōu)特征子集。后來隨著Relief不斷得到擴(kuò)展，其當(dāng)前能夠解決多類型、不完整和有噪聲的數(shù)據(jù)信息挖掘任務(wù)[5]。

3.3 LVW算法

LVW算法屬于一種十分典型的包裝特征選擇方法，其沒有固定的搜索方向，也沒有專門的搜索策略；在評價(jià)方法上其采用正確性評價(jià)，也就是通過單一機(jī)器學(xué)習(xí)算法或者分類器對屬性子集進(jìn)行評價(jià)；在停止標(biāo)準(zhǔn)上，當(dāng)預(yù)先設(shè)置的循環(huán)次數(shù)結(jié)束后即停止算法[3]。相比于過濾式特征選擇，包裝式特征選擇會(huì)直接將最終采用的學(xué)習(xí)器的性能作為特征子集的評價(jià)標(biāo)準(zhǔn)，也就是說，包裝式特征選擇的最終目標(biāo)在于為學(xué)習(xí)器選擇最有利于其性能的特征子集。在具體運(yùn)行過程中，LVW算法以拉斯維加斯方法框架為基礎(chǔ)，假設(shè)數(shù)據(jù)集為E，特征集為B，那么該算法每次在特征集B里隨機(jī)產(chǎn)生一個(gè)特征子集B'，之后采用交叉驗(yàn)證的方式，對學(xué)習(xí)器在特征子集B'的誤差進(jìn)行估計(jì)，當(dāng)誤差小于之前獲取的最小誤差時(shí)，或者當(dāng)與之前獲取的最小誤差相當(dāng)?shù)荁'里所涵蓋的特征數(shù)更少，那么將B'進(jìn)行保留。因?yàn)長VW算法每次對子集B'進(jìn)行評價(jià)時(shí)，都必須重新訓(xùn)練學(xué)習(xí)器，計(jì)算開銷相對較大，所以其必須設(shè)置參數(shù)T對停止條件進(jìn)行控制。不過如果特征數(shù)很多，即∣B∣較大，而且參數(shù)T也很大時(shí)，算法可能出現(xiàn)運(yùn)行長時(shí)間不能停止的情況[6]。

4 結(jié)語

隨著計(jì)算機(jī)科學(xué)技術(shù)的快速發(fā)展以及經(jīng)濟(jì)的快速進(jìn)步，各行各業(yè)企業(yè)存儲(chǔ)數(shù)據(jù)量急劇上升。在海量的數(shù)據(jù)背后隱藏著大量有價(jià)值的信息，通過發(fā)現(xiàn)、挖掘、分析這些數(shù)據(jù)能夠?yàn)槠髽I(yè)管理者做出精準(zhǔn)決策提供強(qiáng)而有力的支持。而在知識發(fā)現(xiàn)中，特征選擇極為關(guān)鍵，只有全面進(jìn)行數(shù)據(jù)的抽取、轉(zhuǎn)換、抽樣、離散以及去除噪聲，才能得到較好的特征選擇效果。

參考文獻(xiàn)

[1] 趙宇，黃思明，陳銳.數(shù)據(jù)分類中的特征選擇算法研究[J].中國管理科學(xué)，2013，21（6）：38-46.

[2] 劉海燕.基于信息論的特征選擇算法研究[D].復(fù)旦大學(xué)，2012.

[3] 李紅.數(shù)據(jù)挖掘中特征選擇與聚類算法研究[D].大連理工大學(xué)，2010.

[4] 毛勇，周曉波，夏錚，等.特征選擇算法研究綜述[J].模式識別與人工智能，2007，20（2）：211-218.

[5] 彭佳紅，沈岳，張林峰.數(shù)據(jù)挖掘中的特征選擇及其算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2005（5）：1176-1178.

[6] 張隆.基于信息論的特征選擇和分類算法研究[D].西南農(nóng)業(yè)大學(xué)，2005.