數(shù)據(jù)挖掘中特征提取的分析與應(yīng)用

1、數(shù)據(jù)挖掘中特征提取的分析與應(yīng)用摘要：數(shù)據(jù)挖掘中需要對(duì)數(shù)據(jù)進(jìn)行各種分析，在一切分析前需要做好數(shù)據(jù)預(yù)處理。然而經(jīng)過(guò)數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換后，數(shù)據(jù)集仍然會(huì)非常大！在海量的數(shù)據(jù)上直接進(jìn)行復(fù)雜的數(shù)據(jù)分析與挖掘?qū)⑿枰荛L(zhǎng)時(shí)間，使得這種分析不現(xiàn)實(shí)或不可行。數(shù)據(jù)歸約技術(shù)可以用來(lái)得到數(shù)據(jù)集的歸約表示，它小得多，但仍接近于保持原數(shù)據(jù)的完整性。這樣，在歸約后的數(shù)據(jù)集上挖掘?qū)⒏行?，并產(chǎn)生相同或幾乎相同的分析結(jié)果。通過(guò)這種方法從大量特征中提取出最具有代表性的特征根據(jù)需要分析有用的信息。隨著社會(huì)的發(fā)展，傳統(tǒng)的基于信物或口令的安全系統(tǒng)顯得越來(lái)越脆弱，不能夠滿(mǎn)足現(xiàn)代安全系統(tǒng)的需要。基于特征提取的指紋識(shí)別隨之產(chǎn)生，在眾

2、多的指紋屬性中提取端點(diǎn)和分叉點(diǎn)兩大明顯特征，進(jìn)行數(shù)據(jù)挖掘與分析。關(guān)鍵詞：數(shù)據(jù)挖掘；數(shù)據(jù)預(yù)處理；數(shù)據(jù)歸約；維歸約；特征提??；指紋識(shí)別前言：數(shù)據(jù)挖掘中需要對(duì)數(shù)據(jù)進(jìn)行各種分析，在一切分析前需要做好數(shù)據(jù)預(yù)處理。然而經(jīng)過(guò)數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換處理后，數(shù)據(jù)集仍然會(huì)非常大！在海量的數(shù)據(jù)上直接進(jìn)行復(fù)雜的數(shù)據(jù)分析與挖掘?qū)⑿枰荛L(zhǎng)時(shí)間，使得這種分析不現(xiàn)實(shí)或不可行。此時(shí)數(shù)據(jù)歸約技術(shù)顯得尤為重要，通過(guò)數(shù)據(jù)歸約技術(shù)的數(shù)據(jù)立方體聚集、維歸約、數(shù)據(jù)壓縮、數(shù)值壓縮、離散化和概念分層產(chǎn)生策略將數(shù)據(jù)集歸約表示，保持原數(shù)據(jù)的完整性。這樣，在歸約后的數(shù)據(jù)集上挖掘?qū)⒏行?，并產(chǎn)生相同或幾乎相同的分析結(jié)果。通過(guò)這種方法從大量特征中

3、提取出最具有代表性的特征根據(jù)需要分析有用的信息。數(shù)據(jù)挖掘中的特征提取被廣泛應(yīng)用，其中指紋識(shí)別則是最典型的應(yīng)用。數(shù)據(jù)挖掘中的特征提取的分析與應(yīng)用經(jīng)過(guò)數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)變換預(yù)處理后，數(shù)據(jù)量仍然會(huì)很大，直接進(jìn)行分析，肯定會(huì)降低挖掘過(guò)程的速度和效率。而通過(guò)數(shù)據(jù)歸約的數(shù)據(jù)立方體聚集、維歸約、數(shù)據(jù)壓縮、數(shù)值壓縮等策略可以壓縮數(shù)據(jù)集，而又不損害數(shù)據(jù)挖掘的結(jié)果。簡(jiǎn)而言之，數(shù)據(jù)歸約是通過(guò)聚集、刪除冗余特性或聚類(lèi)的方法來(lái)壓縮數(shù)據(jù)。數(shù)據(jù)立方體聚集是作用于數(shù)據(jù)立方體中的數(shù)據(jù)；維歸約可以檢測(cè)并刪除不相關(guān)、弱相關(guān)或冗余的屬性或維；數(shù)據(jù)壓縮使用編碼機(jī)制壓縮數(shù)據(jù)集；數(shù)值壓縮用替代的、較小的數(shù)據(jù)表示替換或估計(jì)數(shù)據(jù)。本文就

4、維歸約的特征提取進(jìn)行詳盡的分析與應(yīng)用說(shuō)明，首先介紹維歸約的概念。一、維歸約用于數(shù)據(jù)分析的數(shù)據(jù)可能包含數(shù)以百計(jì)的屬性，其中大部分屬性與挖掘任務(wù)不相關(guān)，是冗余的。盡管領(lǐng)域?qū)＜铱梢蕴暨x出有用的屬性，但這可能是一項(xiàng)困難而費(fèi)時(shí)的任務(wù)，特別是當(dāng)數(shù)據(jù)的行為不清楚的時(shí)候更是如此。遺漏相關(guān)屬性或留下不相關(guān)屬性是有害的，可能會(huì)減慢挖掘進(jìn)程。維歸約則是通過(guò)刪除不相關(guān)的屬性或維減少數(shù)據(jù)量。通常使用屬性子集的選擇方法，即特征提取。二、特征提取的概念特征提取是通過(guò)映射的方法，將高維的屬性空間壓縮為低維的屬性空間，得到最小的屬性集，使得數(shù)據(jù)類(lèi)的概念分布盡可能地接近使用所有屬性的原分布。得到的數(shù)據(jù)挖掘結(jié)果與所有特征參加的數(shù)據(jù)

5、挖掘結(jié)果相近或完全一致。對(duì)于d個(gè)屬性來(lái)說(shuō)，有2d個(gè)可能的子集。三、特征提取的分析通過(guò)窮舉搜索找出屬性的最佳子集可能是不現(xiàn)實(shí)的，特別是當(dāng)d和數(shù)據(jù)類(lèi)的數(shù)目增加時(shí)，因此，對(duì)于特征提取通常是使用壓縮搜索空間的啟發(fā)式算法。特征提取的基本啟發(fā)式方法包括以下四種：(1)逐步向前選擇：該過(guò)程由空屬性集作為歸約集開(kāi)始，確定原屬性集中最好的屬性，并將它添加到歸約集中。在其后的每一次迭代，將剩下的原屬性集中的最好的屬性添加到該集合中。如圖1左(2)逐步向后刪除：該過(guò)程由整個(gè)屬性集開(kāi)始。在每一步中，刪除尚在屬性集中最差的屬性。如圖1中(3)逐步向前選擇和逐步向后刪除的組合：可以將逐步向前選擇和逐步向后刪除方法結(jié)合在一

6、起，每一步選擇一個(gè)最好的屬性，并在剩余屬性中刪除一個(gè)最差的屬性。(4)決策樹(shù)歸納：決策樹(shù)歸納構(gòu)造一個(gè)類(lèi)似于流程圖的結(jié)構(gòu)，其中每個(gè)內(nèi)部(非樹(shù)葉)結(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試，每個(gè)分枝對(duì)應(yīng)于測(cè)試的一個(gè)結(jié)果；每個(gè)外部(樹(shù)葉)結(jié)點(diǎn)表示一個(gè)類(lèi)預(yù)測(cè)。在每個(gè)結(jié)點(diǎn)上，算法選擇“最好”的屬性，將數(shù)據(jù)劃分成類(lèi)。如圖1右向前選齊mi才決袋樹(shù)內(nèi)納制始值性集：Eh七大八H州始化網(wǎng)的集：JnH1iT1.九.Ll=歸妁后的牖性第，“.II'，_1,士初始屬性集，4卜月*月4.4Q:制嫡屬性集：G，.4-II-4.人一14p.小.4*.%&J二；.山.小,名才=>|H的后的屬性集*；I1卜卜，日：圖1屬性子

7、集選擇(特征提取)的貪心(啟發(fā)式)方法四、特征提取在指紋識(shí)別技術(shù)上的應(yīng)用與分析基于特征提取的特性，具被廣泛應(yīng)用于各種領(lǐng)域。在現(xiàn)實(shí)生活中經(jīng)常要對(duì)人的身份進(jìn)行識(shí)別，例如登飛機(jī)時(shí)要識(shí)別登機(jī)者的身份，在銀行取錢(qián)時(shí)要核實(shí)取錢(qián)者是否是指定賬戶(hù)的合法擁有者，使用計(jì)算機(jī)時(shí)要檢查操作者的權(quán)限等等。隨著國(guó)民經(jīng)濟(jì)和社會(huì)信息化的飛速發(fā)展，金融機(jī)構(gòu)、政府機(jī)關(guān)、企業(yè)以及個(gè)人之間通過(guò)互聯(lián)網(wǎng)日益緊密地聯(lián)系在一起，一方面為信息的共享提供了條件，另一方面也為心懷叵測(cè)的人試圖非法獲取他人信息提供了機(jī)會(huì)。因此，如何自動(dòng)、準(zhǔn)確和高效地識(shí)別人的身份是信息安全領(lǐng)域的重要問(wèn)題。而指紋具有唯一性和穩(wěn)定性，因此被人們用來(lái)當(dāng)作鑒別一個(gè)人身份的主要

8、依據(jù)。然而如何在成千上萬(wàn)的指紋數(shù)據(jù)庫(kù)中準(zhǔn)確找出代表某一個(gè)人的指紋，進(jìn)行數(shù)據(jù)挖掘，這就需要用到指紋識(shí)別技術(shù)了。相對(duì)于其它生物特征鑒定技術(shù)，指紋識(shí)別是一種理想的身份鑒別技術(shù)。1、指紋的類(lèi)型目前我國(guó)指紋的分類(lèi)主要有以下兩種：(1)基于指紋管理需要的十指指紋管理分類(lèi)法：該分類(lèi)方法將指紋分為弓、箕、斗三種類(lèi)型，并將箕型紋分為反箕和正箕以及中心點(diǎn)、外角點(diǎn)和追跡線的計(jì)線法。(2)計(jì)算機(jī)指紋管理的分類(lèi)：指紋自動(dòng)識(shí)別系統(tǒng)一般把指紋紋型分為弓、左箕、右箕、斗和雜型五大類(lèi)，其分類(lèi)的規(guī)則與十指指紋分析法基本一致，其代號(hào)為：A、弓型紋；R左箕型紋；C、右箕型紋；D斗型紋；E、雜型紋。2、指紋圖像的采集傳統(tǒng)的指紋采集方法

9、為油墨轉(zhuǎn)印法；活體指紋采集法直接從手指上獲取數(shù)字指紋圖像。3、指紋圖像的預(yù)處理對(duì)于一幅指紋采集頭采集的原始圖像，為了使后續(xù)特征提取的操作能夠正常有效的進(jìn)行，必須對(duì)原始指紋圖像進(jìn)行一定的處理。通常這樣的處理過(guò)程包括歸一化、圖像增強(qiáng)、二值化和細(xì)化等過(guò)程。如圖2所示預(yù)處理圖2指紋圖像處理步驟4、指紋圖像的特征選取因?yàn)槊總€(gè)人的指紋多種多樣，在指紋識(shí)別技術(shù)中，指紋特征提取是其中一個(gè)非常重要的部分。這其中包括了提取什么樣的特征、用什么樣的方法提取特征、提取到的特征是不是能夠代表該指紋特點(diǎn)的真實(shí)特征等三個(gè)問(wèn)題。指紋圖像中存在兩種類(lèi)型的特征：全局特征和局部特征。全局特征通常用于指紋的分類(lèi)，局部特征通常用于指紋

10、的比對(duì)?；诰植刻卣?，根據(jù)指紋學(xué)所述，國(guó)際鑒定協(xié)會(huì)標(biāo)準(zhǔn)委員會(huì)確定的特征細(xì)節(jié)點(diǎn)有以下五種：（1）紋線端點(diǎn)（2）紋線分叉（3）短線（4）眼線（5）點(diǎn)奧斯特布曾建議指紋特征細(xì)節(jié)點(diǎn)除上述五種外再加上以下五種：（6）三角（7）橋形（8）雙叉（9）三叉（10）馬刺形指紋特征中還有一個(gè)非常重要的特征點(diǎn)（11）中心點(diǎn)，如圖3所示為特征點(diǎn)細(xì)節(jié)的舉例圖3指紋特征點(diǎn)據(jù)統(tǒng)計(jì)，這幾類(lèi)特征點(diǎn)占特征點(diǎn)的比率如圖4所示。從表中可以發(fā)現(xiàn)，端點(diǎn)和分叉點(diǎn)占特征點(diǎn)91%而交叉形、橋形以及環(huán)形三類(lèi)總共只占9流右。這一方面說(shuō)明了幾乎所有的指紋都有端點(diǎn)和分叉點(diǎn)，而且數(shù)量豐富；另一方面也反映了不是所有的指紋都有橋形、環(huán)形等特征點(diǎn)，而且即使有

11、數(shù)量也比較少。由此可知，端點(diǎn)和分叉點(diǎn)又占了很大的比例，所以一般只研究端點(diǎn)和分叉點(diǎn)的特性。特征點(diǎn)類(lèi)型特征示意圖所占比例端點(diǎn);68.2%分叉點(diǎn)23.8%橋型3.7%交叉型一3.2%環(huán)型1.1%圖4特征點(diǎn)類(lèi)型及所占比例目前大部分指紋識(shí)別系統(tǒng)使用的局部特征都是美國(guó)聯(lián)邦調(diào)查局（FBI）提出的細(xì)節(jié)點(diǎn)匹配模型，它利用末梢點(diǎn)（紋線端點(diǎn)）與分叉點(diǎn)（紋線分叉）（如圖5）這兩種特征來(lái)鑒定指紋，思路是先進(jìn)行細(xì)節(jié)特征提取，將指紋圖像中所有的末梢點(diǎn)和分叉點(diǎn)找出來(lái)，然后對(duì)所有的細(xì)節(jié)特征點(diǎn)進(jìn)行后處理，以判斷它們是否有效。(a)末梢點(diǎn)(b)分叉點(diǎn)圖5末梢點(diǎn)與分叉點(diǎn)目前對(duì)指紋特征點(diǎn)提取的算法多種多樣，各有不同，如基于直接從指紋灰

12、度圖像的特征提取算法、基于細(xì)化的圖像特征提取算法、基于紋線方向?yàn)V波的指紋特征提取算法、基于二值化的指紋特征提取算法等等。但總體上，最常用的特征點(diǎn)提取算法有兩類(lèi)：一是從灰度圖像直接提取特征點(diǎn)；二是對(duì)預(yù)處理細(xì)化后的圖像進(jìn)行提取特征點(diǎn)?；谏鲜鰯?shù)據(jù)挖掘中的特征提取在指紋識(shí)別分析技術(shù)上的應(yīng)用，可以看出，經(jīng)過(guò)一系列的特征提取后，將原本多種指紋屬性降到最少，卻依然具有代表性。不僅更加準(zhǔn)確的完成識(shí)別，而且可以明顯大大降低了工作量。顯而易見(jiàn)，特征提取在數(shù)據(jù)挖掘中的重要性，以及不可忽視性。結(jié)論：在海量的數(shù)據(jù)上直接進(jìn)行復(fù)雜的數(shù)據(jù)分析與挖掘?qū)⑿枰荛L(zhǎng)時(shí)間，使得這種分析不現(xiàn)實(shí)或不可行。所以需要進(jìn)行數(shù)據(jù)歸約，此時(shí)特稱(chēng)提

13、取就顯得尤為重要了。經(jīng)過(guò)提取后的數(shù)據(jù)集在進(jìn)行數(shù)據(jù)挖掘后的結(jié)果不僅與所有特征參加的數(shù)據(jù)挖掘結(jié)果相近或完全一致，而且大大減少了工作量，因此它被廣泛運(yùn)用于現(xiàn)實(shí)生活。隨著社會(huì)的發(fā)展，傳統(tǒng)的基于信物或口令的安全系統(tǒng)顯得越來(lái)越脆弱，不能夠滿(mǎn)足現(xiàn)代安全系統(tǒng)的需要?；谔卣魈崛〉闹讣y識(shí)別隨之產(chǎn)生，在眾多的指紋屬性中提取端點(diǎn)和分叉點(diǎn)兩大明顯特征，進(jìn)行數(shù)據(jù)挖掘與分析。參考文獻(xiàn)：JiaweiHan、Michelinekamber著范明、孟小峰等譯.數(shù)據(jù)挖掘概念和技術(shù).：機(jī)械工業(yè)出版社，2001年2011年劉云霞.數(shù)據(jù)預(yù)處理一一數(shù)據(jù)歸約的統(tǒng)計(jì)方法研究及應(yīng)用：廈門(mén)大學(xué)出版社,李昊傅曦編著.物聯(lián)網(wǎng)一一指紋識(shí)別系統(tǒng)算法及實(shí)現(xiàn)(VisualC+):人