粗糙擬陣及其在高維數(shù)據(jù)降維中的應(yīng)用研究.pdf

1、隨著大數(shù)據(jù)時(shí)代的來臨，大規(guī)模的非結(jié)構(gòu)化和半結(jié)構(gòu)化的數(shù)據(jù)存在于每個(gè)行業(yè)和每個(gè)領(lǐng)域，這就迫切要求人類對(duì)海量數(shù)據(jù)進(jìn)行挖掘和規(guī)則提取。數(shù)據(jù)量大、數(shù)據(jù)類型繁多、價(jià)格密度低和速度快時(shí)效高是大數(shù)據(jù)的四個(gè)重要特征，這就意味著傳統(tǒng)的方法和技術(shù)已無法應(yīng)對(duì)目前的大數(shù)據(jù)時(shí)代。正因?yàn)槿绱耍瑪?shù)據(jù)的降維顯得尤為重要，這一方面可以緩解甚至解決“維數(shù)災(zāi)難”，降低計(jì)算成本，減少過擬合風(fēng)險(xiǎn)，另一方面可以更好地認(rèn)識(shí)和理解數(shù)據(jù)特征間的聯(lián)系。
　　本文相對(duì)系統(tǒng)地研究了各類數(shù)

2、據(jù)類型的特征選擇，尤其是建立了離散型和連續(xù)型的特征選擇的專門模型和算法。特別地，本文還提出了次模函數(shù)的貪婪算法的評(píng)價(jià)體系，這對(duì)建立高效的貪婪算法有著重要的指導(dǎo)意義。同時(shí)，我們還將稀疏表示、核函數(shù)和非負(fù)矩陣分解等技巧運(yùn)用到特征選擇中，設(shè)計(jì)了多個(gè)高效的特征選擇算法。具體的創(chuàng)新性研究成果主要體現(xiàn)在如下四個(gè)方面：
　　(1)引入擬陣次模性來評(píng)估基于貪婪策略的特征選擇算法。很多高效的算法都是建立在連續(xù)平滑的目標(biāo)優(yōu)化函數(shù)之上的，而對(duì)于離散型數(shù)

3、據(jù)的特征選擇問題，這些算法往往是無效的，從而幾乎所有的離散型數(shù)據(jù)的特征選擇算法都是基于貪婪策略。眾所周知的是，貪婪算法得到的解往往不是整體最優(yōu)解，而是近似解或滿意解。這就造成了滿意解和整體最優(yōu)解之間的“灰色地帶”，而如何度量這種“灰色地帶”，即滿意解和最優(yōu)解之間的差異，是一個(gè)非常困難但非常重要的問題。為此，本文首先建立了粗糙集的擬陣結(jié)構(gòu)，再次借助擬陣次模性來刻畫貪婪算法對(duì)最優(yōu)解的逼近程度。特別地，本文還給出了幾類特殊的目標(biāo)優(yōu)化函數(shù)的的貪

4、婪算法的緊湊邊界。
　　(2)提出線性結(jié)構(gòu)保持的特征選擇算法。如何衡量數(shù)據(jù)的線性結(jié)構(gòu)一直是很困難的問題，而對(duì)于特征間具有良好相關(guān)性的數(shù)據(jù)，這一問題顯得異常重要。本文借助稀疏編碼來刻畫數(shù)據(jù)的線性相關(guān)性。進(jìn)一步地，考慮到稀疏表示過程中利用L1-范數(shù)來調(diào)節(jié)表示系數(shù)的稀疏性程度，這導(dǎo)致了目標(biāo)優(yōu)化函數(shù)的非平滑性。為此，本文通過給定系數(shù)矩范數(shù)的上界，將這類非平滑的優(yōu)化目標(biāo)函數(shù)轉(zhuǎn)變?yōu)槠交膬?yōu)化目標(biāo)函數(shù)。特別地，本文還通過鄰域來刻畫數(shù)據(jù)的局部線性

5、保持性，將稀疏編碼過程和特征選擇過程融入到一個(gè)框架中，提出鄰域嵌入的特征選擇算法。
　　(3)引入特征選擇算法的核函數(shù)技巧。核函數(shù)是一種重要的處理非線性數(shù)據(jù)的技巧，其基本思想是將原數(shù)據(jù)映射到高維乃至無窮維空間中進(jìn)行處理，而這一過程并不需要非線性變換函數(shù)的表達(dá)式和參數(shù)，從而有效地避免了“維數(shù)災(zāi)難”。也正是因?yàn)榉蔷€性變換函數(shù)是未知的，很多模型并不能嵌入核技巧。本文利用投影矩陣將特征選擇問題表示為矩陣分解問題，再利用核技巧實(shí)現(xiàn)對(duì)數(shù)據(jù)的非

6、線性處理。
　　(4)提出一種高階矩陣分解問題的近似算法。數(shù)據(jù)的高維性是大數(shù)據(jù)的一個(gè)重要特征。通過矩陣分解，可以實(shí)現(xiàn)對(duì)高維數(shù)據(jù)的降維、壓縮和歸類。然而，大部分的現(xiàn)存的矩陣分解方面的研究成果都是局限于二階的優(yōu)化問題，而實(shí)際生活中的眾多優(yōu)化問題往往可以形式化為高于二階簡稱高階的矩陣分解問題，如聚類問題和含有正交約束的各類優(yōu)化問題。本文將特征選擇問題形式化為四階的目標(biāo)優(yōu)化問題，繼而通過懲罰矩陣提出一套解決高階矩陣分解問題的近似算法并證明