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

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

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

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

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

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

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