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

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

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

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

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

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

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