一種降維新方法

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

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

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

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

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

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

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

1 降維及本征維

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

1.1 降維的定義

1.2 本征維

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

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

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

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

2 基于個體本征維的降維

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

2.1 HSV顏色模型

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

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

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

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

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

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

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

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

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

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

3 實驗驗證

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

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

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

4 結束語

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

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

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