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

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

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

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

4、。本文就維歸約的特征提取進(jìn)行詳盡的分析與應(yīng)用說明，首先介紹維歸約的概念。一、維歸約用于數(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)屬性是有害的，可能會減慢挖掘進(jìn)程。維歸約則是通過刪除不相關(guān)的屬性或維減少數(shù)據(jù)量。通常使用屬性子集的選擇方法，即特征提取。二、特征提取的概念特征提取是通過映射的方法，將高維的屬性空間壓縮為低維的屬性空間，得到最小的屬性集，使得數(shù)據(jù)類的概念分布盡可能地接近使用所有屬性的原分布。得到的數(shù)據(jù)挖掘結(jié)果與所有特征參

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

6、結(jié)合在一起，每一步選擇一個(gè)最好的屬性，并在剩余屬性中刪除一個(gè)最差的屬性。(4)決策樹歸納：決策樹歸納構(gòu)造一個(gè)類似于流程圖的結(jié)構(gòu)，其中每個(gè)內(nèi)部（非樹葉）結(jié)點(diǎn)表示一個(gè)屬性上的測試，每個(gè)分枝對應(yīng)于測試的一個(gè)結(jié)果；每個(gè)外部（樹葉）結(jié)點(diǎn)表示一個(gè)類預(yù)測。在每個(gè)結(jié)點(diǎn)上，算法選擇“最好”的屬性，將數(shù)據(jù)劃分成類。如圖1右 圖1 屬性子集選擇（特征提取）的貪心（啟發(fā)式）方法四、特征提取在指紋識別技術(shù)上的應(yīng)用與分析基于特征提取的特性，其被廣泛應(yīng)用于各種領(lǐng)域。在現(xiàn)實(shí)生活中經(jīng)常要對人的身份進(jìn)行識別，例如登飛機(jī)時(shí)要識別登機(jī)者的身份，在銀行取錢時(shí)要核實(shí)取錢者是否是指定賬戶的合法擁有者，使用計(jì)算機(jī)時(shí)要檢查操作者的權(quán)限等等。隨

7、著國民經(jīng)濟(jì)和社會信息化的飛速發(fā)展，金融機(jī)構(gòu)、政府機(jī)關(guān)、企業(yè)以及個(gè)人之間通過互聯(lián)網(wǎng)日益緊密地聯(lián)系在一起，一方面為信息的共享提供了條件，另一方面也為心懷叵測的人試圖非法獲取他人信息提供了機(jī)會。因此，如何自動、準(zhǔn)確和高效地識別人的身份是信息安全領(lǐng)域的重要問題。而指紋具有唯一性和穩(wěn)定性，因此被人們用來當(dāng)作鑒別一個(gè)人身份的主要依據(jù)。然而如何在成千上萬的指紋數(shù)據(jù)庫中準(zhǔn)確找出代表某一個(gè)人的指紋，進(jìn)行數(shù)據(jù)挖掘，這就需要用到指紋識別技術(shù)了。相對于其它生物特征鑒定技術(shù)，指紋識別是一種理想的身份鑒別技術(shù)。1、 指紋的類型目前我國指紋的分類主要有以下兩種：（1）基于指紋管理需要的十指指紋管理分類法：該分類方法將指紋分

8、為弓、箕、斗三種類型，并將箕型紋分為反箕和正箕以及中心點(diǎn)、外角點(diǎn)和追跡線的計(jì)線法。（2）計(jì)算機(jī)指紋管理的分類：指紋自動識別系統(tǒng)一般把指紋紋型分為弓、左箕、右箕、斗和雜型五大類，其分類的規(guī)則與十指指紋分析法基本一致,其代號為：A、弓型紋；B、左箕型紋；C、右箕型紋；D、斗型紋；E、雜型紋。2、指紋圖像的采集傳統(tǒng)的指紋采集方法為油墨轉(zhuǎn)印法；活體指紋采集法直接從手指上獲取數(shù)字指紋圖像。3、指紋圖像的預(yù)處理對于一幅指紋采集頭采集的原始圖像，為了使后續(xù)特征提取的操作能夠正常有效的進(jìn)行，必須對原始指紋圖像進(jìn)行一定的處理。通常這樣的處理過程包括歸一化、圖像增強(qiáng)、二值化和細(xì)化等過程。如圖2所示圖2 指紋圖像處

9、理步驟4、指紋圖像的特征選取因?yàn)槊總€(gè)人的指紋多種多樣，在指紋識別技術(shù)中，指紋特征提取是其中一個(gè)非常重要的部分。這其中包括了提取什么樣的特征、用什么樣的方法提取特征、提取到的特征是不是能夠代表該指紋特點(diǎn)的真實(shí)特征等三個(gè)問題。指紋圖像中存在兩種類型的特征：全局特征和局部特征。全局特征通常用于指紋的分類，局部特征通常用于指紋的比對?；诰植刻卣?，根據(jù)指紋學(xué)所述，國際鑒定協(xié)會標(biāo)準(zhǔn)委員會確定的特征細(xì)節(jié)點(diǎn)有以下五種：（1）紋線端點(diǎn)（2）紋線分叉（3）短線（4）眼線（5）點(diǎn)奧斯特布曾建議指紋特征細(xì)節(jié)點(diǎn)除上述五種外再加上以下五種：（6）三角（7）橋形（8）雙叉（9）三叉（10）馬刺形指紋特征中還有一個(gè)非常重要

10、的特征點(diǎn)（11）中心點(diǎn)，如圖3所示為特征點(diǎn)細(xì)節(jié)的舉例圖3 指紋特征點(diǎn)據(jù)統(tǒng)計(jì)，這幾類特征點(diǎn)占特征點(diǎn)的比率如圖4所示。從表中可以發(fā)現(xiàn)，端點(diǎn)和分叉點(diǎn)占特征點(diǎn)91%，而交叉形、橋形以及環(huán)形三類總共只占9%左右。這一方面說明了幾乎所有的指紋都有端點(diǎn)和分叉點(diǎn)，而且數(shù)量豐富；另一方面也反映了不是所有的指紋都有橋形、環(huán)形等特征點(diǎn)，而且即使有數(shù)量也比較少。由此可知，端點(diǎn)和分叉點(diǎn)又占了很大的比例，所以一般只研究端點(diǎn)和分叉點(diǎn)的特性。圖4 特征點(diǎn)類型及所占比例目前大部分指紋識別系統(tǒng)使用的局部特征都是美國聯(lián)邦調(diào)查局（FBI）提出的細(xì)節(jié)點(diǎn)匹配模型，它利用末梢點(diǎn)（紋線端點(diǎn)）與分叉點(diǎn)（紋線分叉）（如圖5）這兩種特征來鑒定指紋

11、，思路是先進(jìn)行細(xì)節(jié)特征提取，將指紋圖像中所有的末梢點(diǎn)和分叉點(diǎn)找出來，然后對所有的細(xì)節(jié)特征點(diǎn)進(jìn)行后處理，以判斷它們是否有效。圖5 末梢點(diǎn)與分叉點(diǎn)目前對指紋特征點(diǎn)提取的算法多種多樣，各有不同，如基于直接從指紋灰度圖像的特征提取算法、基于細(xì)化的圖像特征提取算法、基于紋線方向?yàn)V波的指紋特征提取算法、基于二值化的指紋特征提取算法等等。但總體上，最常用的特征點(diǎn)提取算法有兩類：一是從灰度圖像直接提取特征點(diǎn)；二是對預(yù)處理細(xì)化后的圖像進(jìn)行提取特征點(diǎn)?；谏鲜鰯?shù)據(jù)挖掘中的特征提取在指紋識別分析技術(shù)上的應(yīng)用，可以看出，經(jīng)過一系列的特征提取后，將原本多種指紋屬性降到最少，卻依然具有代表性。不僅更加準(zhǔn)確的完成識別，而且

12、可以明顯大大降低了工作量。顯而易見，特征提取在數(shù)據(jù)挖掘中的重要性，以及不可忽視性。結(jié)論：在海量的數(shù)據(jù)上直接進(jìn)行復(fù)雜的數(shù)據(jù)分析與挖掘?qū)⑿枰荛L時(shí)間，使得這種分析不現(xiàn)實(shí)或不可行。所以需要進(jìn)行數(shù)據(jù)歸約，此時(shí)特稱提取就顯得尤為重要了。經(jīng)過提取后的數(shù)據(jù)集在進(jìn)行數(shù)據(jù)挖掘后的結(jié)果不僅與所有特征參加的數(shù)據(jù)挖掘結(jié)果相近或完全一致，而且大大減少了工作量，因此它被廣泛運(yùn)用于現(xiàn)實(shí)生活。隨著社會的發(fā)展，傳統(tǒng)的基于信物或口令的安全系統(tǒng)顯得越來越脆弱，不能夠滿足現(xiàn)代安全系統(tǒng)的需要?；谔卣魈崛〉闹讣y識別隨之產(chǎn)生，在眾多的指紋屬性中提取端點(diǎn)和分叉點(diǎn)兩大明顯特征，進(jìn)行數(shù)據(jù)挖掘與分析。參考文獻(xiàn)：Jiawei Han、Micheline kamber