一種降維新方法

摘 要：針對圖像數據的72維HSV顏色特征，對數據集的本征維概念進行了有意義的擴展，在此基礎上提出了一個新的降維機制。實驗證明，該降維算法是行之有效的。

關鍵詞：維度災難； 降維； 本征維

中圖分類號：TP301文獻標志碼：A

文章編號：1001—3695(2007)03—0089—02

科學技術的發展給人們帶來了各種類型的海量數據，如航天數據、生物數據、圖像數據以及金融市場交易數據等，這些數據的表象均是高維的。例如，對于N幅圖像來說，設每幅圖像具有D=m×n個像素點，那么每幅圖像都可看做D維空間的一個觀測。這種維數的膨脹即為通常所說的維度災難[1]，它無疑給數學和數據分析帶來了巨大的挑戰。為了從眾多的高維數據中獲取有意義的信息，很多研究者從不同的方面展開了許多有意義的研究，降維就是其中最為廣泛的研究之一。它通過探求嵌入在高維數據空間中本征低維流形的不同樣式，尋求事物的本質規律性。

與此同時，從理論方面看，目前對高維數據的研究主要涉及到高維數據的流形結構表示問題，包括高維數據的本征維數問題、高維數據的稀疏表示問題、高維極限結構以及隱變量和獨立參數表示。在這幾個方面中，本征維是反映高維數據內蘊特性的一個最重要的概念。為了保證降維后的數據能盡可能多地保留原始數據的重要信息，必然要求在降維的過程中能盡可能完整地保留原始高維數據的本征屬性。

現有的降維研究大多從整個目標數據集出發、定義并探求高維目標數據集的本征維[2]，卻往往忽略了數據集中單個個體的重要屬性，從而不可避免塊會導致一些重要個體信息的丟失。以此為出發點，本文對數據集的本征維概念進行了有意義的擴展，從考慮數據集合中單個個體的本征維出發，提出了一種新的降維機制。

1 降維及本征維

降維方法是一種在高維情形之下，對現實世界中的復雜現象進行建模、分析的有力工具。一般來說，可以認為數據集的本征維數總是比其真實維數（表象維數）要小得多。因此降維處理不僅可以獲得計算上的優勢，還可以增強數據的可理解性。

1.1 降維的定義

1.2 本征維

降維的目的是提取數據集某一方面的本征信息，以便對其進行進一步的分析、處理。若選取降維空間為d維歐式空間，那么降維問題就轉換為如何選擇合適的維數d（即數據集的本征維數）的問題。

所謂本征維，是指一個數據集所表示的空間對象的實際維度，而不管其所在空間的維數。從幾何角度來看，本征維數是D維空間中的采樣點可以近似嵌入的低維流形的維數d，且d

由此可知，數據集的本征維概念是一個相對模糊的概念。因為不同的數據在同一個數據集中也可能呈現出不同的特性，如果把所有的高維數據均表示在同一個固定的模式下，不可避免地會帶來大量信息的丟失。因此為了獲取高維數據更準確、更完整的降維結果，可以從數據集的單個個體入手，根據個體的本征維進行降維。這樣一方面達到了對高維數據進行降維的目的，另一方面也最大限度地保留了原始數據空間的整體和局部信息。

為此，本文對本征維的概念進行了有意義的擴展。設x為D維空間中的一個個體，其屬性集合f={f₁， f₂，…， f_D}，若f′={f₁， f₂，…， f_d}（d＜D，f′f）也能夠較為完整地描述x的特性，且f′是滿足條件的最小集，則稱d為個體x的本征維數，相應的維度集合即為x的本征維。

2 基于個體本征維的降維

如前所述，降維是獲取數據在更低維空間上的緊湊表示的一種有效手段。降維算法的性能與所處理的數據密切相關，它極大地依賴于目標數據本身的特性。本文主要以降維在多媒體信息處理中的應用為背景，針對圖像的HSV顏色特征，提出了一種基于個體本征維的降維新方法。

2.1 HSV顏色模型

HSV顏色模型是一種基于感知的顏色模型，它把彩色信號表示為三種屬性，即色調（Hue）、飽和度（Saturation）和亮度（Value），這種顏色模型用Munsell三維空間坐標系統表示。其中H表示從一個物體反射過來的或透過物體的光的波長，一般通過顏色名稱來進行辨別，并用角度-180—180°度量；飽和度S指顏色的深淺，它用百分比來度量，變化范圍從0—100%；亮度V是顏色的明暗度，也用百分比度量。

對于任何一幅圖像來說，通過相應的特征抽取處理以及顏色空間轉換之后，均可以得到其顏色的h、s和v值，然后對其HSV空間進行適當的量化并計算直方圖，即可將h、s和v這三個分量在一維矢量上（記作L）分布開來，并且L的取值范圍可以確定為[0，1，… ，71]。這樣就獲得了72柄的一維直方圖[3]。于是對于任意圖像I，都可有如下形式的72維HSV顏色特征：I=(Hsv₀，Hsv₁，…，Hsv₇₁)。由于量化之后，所有72維HSV特征值的和均等于1，那么其中每一維的取值代表了某一種顏色在相應圖像中所占的比例。 

2.2 基于HSV特征本征維的降維

所謂本征維就是能代表數據的本征特性的所有維度的集合。將這一概念從數據集擴展到單個個體，更能夠體現數據的本質特性。但是由于降維的過程與所處理的目標數據密切相關，那么本征維的概念，尤其是個體本征維的概念，與具體應用中的具體數據關系更加緊密。

對于圖像的72維HSV顏色特征來講，其中的每一維均代表了某一種顏色在圖像中所占的比例。這就意味著：如果某一維上的屬性值最大，那么這一維所對應的顏色在圖像中所占的比例將是最大的，即這種顏色就是相應圖像的主要顏色之一。把一維擴展到多個維，如果某些維上屬性值的和超過了80％或是更多，也就是說一幅圖像至少80％的顏色是由這些維決定的，那么就認為這些維構成了一幅圖像的本征維。80％這個閾值是根據人的感觀誤差而定的，若把該閾值設為90％或是更高，當然能保留原始圖像更多的顏色信息，但是并不是這個閾值越高，降維的效果就越好。首先，從直觀上看，這個閾值越大，本征維數自然越高，因此降維的效果越不明顯。把閾值設為80％，不僅保留了原始數據的重要信息，而且也達到了對數據降維的目的，這一點可以通過后面的實驗分析有更清楚的認識。

當然，對于一幅圖像的HSV特征來講，并不是說如果任何維上的屬性取值超過了80％，就認為這些維是其本征維，而是要先對這72個屬性值從大到小進行排序，然后由大到小順次累加。若前d個最大值之和超過了80％，d就是它的本征維數，相應的d個維就是其本征維。

據此，設特征數據庫的樣本數為N，對所有N個特征向量中的72維屬性值從大到小排序，若所有的前d個最大值的和平均超過了80％，那么數據庫中單個樣本的本征維數即為d。

需要注意的是，雖然數據庫中單個個體的本征維數是一樣的，但是這些維度所處的位置可以不同，因為不可能所有圖像特征值的前d個最大值均處在相同的維度。從這個意義上說，各個個體的降維是互不依賴、獨立進行的。這一降維機制不僅完整保留了原始數據的整體信息和局部信息，而且它們最終仍然能統一到同一個本征維數之中，這也給隨后的相應處理帶來了方便。

設d為目標數據庫中數據的本征維數，那么上述降維過程可描述為

其中，S72為所有圖像的HSV顏色特征原始的72維特征空間，sort算子表示對原始空間中的每一個特征數據的屬性值從大到小排序，從而得到排序后的空間S72以及排序后數據點的屬性值在原始72維空間中的位置信息Pos₇₂。針對排序后的數據空間，應用select算子，對每個數據均選取其前d個最大的屬性值，即得到子空間S_D以及相應的位置信息Pos_D。降維之后個體的本征維數d與子空間S_D的維數D之間滿足d72′和S_D中，還需要用位置信息Pos₇₂和S_D來共同描述相應的空間。

3 實驗驗證

為了驗證降維之后的數據仍然能準確描述原始數據的特征，降維算法的性能還需要通過具體的應用來體現。以基于內容的圖像示例檢索為例，針對包含1萬多幅圖像的數據庫，從檢索的查到率（Recall）（一般來說，查到率是指查到的相關圖像的數目與庫中實際相關數目的比值，但由于相關的概念是很模糊的，可以認為順序查找得到的結果都是與樣本圖像相關的圖像，因此把查到率重新定義為：查到率＝查到的圖像數/順序查找查到的圖像數目，和查詢相應時間（Time）這兩個方面，分析了降維算法的合理性。很明顯，查到率越高，降維過程中損失的原始數據的信息將越少；在保證查到率的前提下，查詢響應時間越短，則表明該降維算法對基于內容圖像檢索的性能提高越多。

同時，為了表明d對降維算法性能的影響，分別測試了d＝8和d＝30時的結果。其中基于內容檢索的相似度值取為60％。實驗結果如表1所示（順序查找查到的圖像數目為82）。

當d＝8時，樣本數據特征值的前八個最大值之和的平均代表了原始圖像86.951 6%的顏色信息，此時查詢響應時間也較短，且查到的圖像數目為81，僅漏掉了一個正確解；而當d＝30時，樣本數據特征值的前30個最大值代表了原始圖像99.298 6%的顏色信息，雖然此時查到率達到了100％，但其查詢相應時間卻是d＝8時的幾乎八倍多。因此，取d＝8，使數據特征的前八個最大值之和超過80％，降維之后的數據就足以準確描述原始的圖像數據，從而具有較高的降維性能。

4 結束語

針對圖像的72維HSV顏色特征，本文對數據集的本征維概念進行了有意義的擴展，提出了個體本征維的概念。實驗表明，本文提出的基于個體本征維的降維不僅實現簡單，而且最大限度地保留了原始高維數據的整體和局部信息，因此具有較高的性能。

今后的工作主要在于尋求該降維方法更完善的數學描述，并從更加通用的角度探討數據個體的本征維概念。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。