一種基於幾何結構調整用於降低數據非線性關係的方法與流程
2023-05-01 17:30:12 1
本發明屬於數據預處理技術領域，具體涉及一種基於幾何結構調整用於降低數據非線性關係的方法。
背景技術：
真實數據集中點與點之間總是存在著一些未知的非線性函數關係。這些非線性函數關係使得在數據集中很難發現這些點的共性，以及找到合適的計算規律，這是數據不容易處理的主要根源之一。真實數據往往又是高維的，而這種高維性引入了更多未知的非線性函數關係，從而進一步加劇了數據處理的複雜性。
現有的公用數據預處理方法主要是對數據進行簡單的淺層的統一性處理，以平衡不同維度對特徵的貢獻差異，所以都不能夠發現並有效處理數據中的非線性關係。例如數據歸一化，常用的方法有：(1)簡單縮放，對數據集的每一維度的值進行調整，使得最終的數據向量落在[0,1]或[-1,1]區間內；(2)逐樣本減均值，在每個樣本上減去數據的平均值；(3)特徵標準化，使得數據的每一個維度具有零均值和單位方差；這些簡單的預處理方法都不涉及數據本身的非線性關係。
更進一步的相對複雜的數據預處理方法，如PCA(主成分分析)/ZCA(白化)等，主要目的在於對數據屬性的初步過濾，以突現主要特徵；基於重構的白化模型和基於正交化ICA(獨立成分分析)的白化模型等皆是如此。如果白化所取維度比初始維度少，則這些方法可以同時看作是數據降維方法，整個過程也沒有專門考慮到對數據的非線性處理。
為了有效處理非線性數據集，目前的做法是採用某種非線性方法來顯式(或隱式)地獲得數據裡面的非線性關係，並通過某種規則將數據在另外一個更低維度的(特徵)空間表示出來。這些非線性方法及其變種非常多，常用的有：核主成分分析(KPCA)、等距映射(ISOMAP)、局部線性嵌入(LLE)、最大方差展開(MVU)等。但這些方法都面臨一個共同的問題，即新構建的特徵空間完全脫離了初始的數據空間，從而損失了很多有用信息，如初始坐標系統中刻度本身所包含的物理意義，數據在原空間中所具有的幾何特徵/信息等。
另外，這些方法都有較強的適用範圍要求。而目前仍然沒有好的方法指導如何將這些適用要求與數據集進行匹配選擇，因為這種要求也可能是隱性的，而且數據集本身的適用特徵判斷還主要依賴於操作人員的經驗。所以，這些方法的穩定性往往因操作人而異、因數據集而異。
技術實現要素：
針對現有技術所存在的上述技術問題，本發明提供了一種基於幾何結構調整用於降低數據非線性關係的方法，其以已經歸一化的數據集為輸入檢測數據集中存在的非線性幾何彎曲程度，並根據檢測到的幾何彎曲特徵，對該數據集作平坦化處理，從而使數據的後續處理更加容易。
一種基於幾何結構調整用於降低數據非線性關係的方法，其首先採用近鄰圖對數據集的空間幾何形狀進行建模；然後以近鄰圖中較長的一條最短路徑來定性表徵近鄰圖的彎曲結構(記作骨架線)；進而應用餘弦定理的思想完成數據點向骨架線的映射；最後通過骨架線沿著一定方向伸展成直線帶動整個數據集進行展開，從而降低數據的非線性關係。
所述數據集中的任一數據點只與其最接近的若干個數據點建立邊的連接，從而在坐標空間中構成一個無向的網狀圖；由於近鄰圖以所有數據點構成其頂點，所以近鄰圖的幾何形狀間接地反映了數據集的一種幾何狀態；故本發明採用KNN(K-Nearest Neighbors，K近鄰)算法構建數據集對應的近鄰圖。
所述最短路徑的定義為近鄰圖中任一兩頂點之間通過邊和點可通達的最短的一條路徑；本發明採用Dijkstra算法在近鄰圖上進行搜索得到一段空間折線，該空間折線為貫穿近鄰圖主體的一條最短路徑，且該空間折線的彎曲狀態體現了近鄰圖在坐標空間中的一個主要的彎曲狀態，因此被稱為骨架線；該骨架線並不一定是近鄰圖中最長的一條最短路徑，但卻是近鄰圖中若干最長的幾個最短路徑之一。
本發明利用歐氏空間中的餘弦定理公式將每個數據點映射到骨架線上，並作好標記：對於任一數據點，將其在骨架線上的映射位置定義為其在骨架線上的映射位置點與骨架線起點的骨架距離d且d＝(b2+c2-a2)/2c，其中：c為骨架線的長度，b為該數據點到骨架線起點最短路徑的長度，a為該數據點到骨架線終點最短路徑的長度。
本發明將數據集中均值點與原點的連線方向作為數據集的展開方向，首先使骨架線沿該方向伸展成一條直線段Ls；伸展過程中，骨架線上的數據點也隨之移動並仍然停留在直線段Ls上；然後將數據集中的其餘數據點沿該方向平移，使得平移後數據點在直線段Ls上的垂直投影正好對應其在骨架線上的映射位置。
非線性關係複雜的數據集，在其對應維度的笛卡兒坐標系下，其整體的幾何形狀必然複雜，其中最明顯的就是彎曲程度高。反之，整體幾何形狀平坦的數據集，其非線性關係則相對簡單，後續的計算能夠比較容易得到好的正確的結果。通過上述技術方案，空間中彎曲的近鄰圖得以展開、平坦化，從而產生一個幾何結構相對簡單的數據集；本發明基於近鄰圖通過最短路徑建模數據集的彎曲狀態，能很好地捕捉到數據集的非線性性並通過幾何展開進行消減，從而有效且可靠地降低數據集的非線性處理難度。
附圖說明
圖1為本發明數據非線性性的幾何表徵以及展開消減實施例的流程框圖。
圖2(a)～圖2(c)對應為本發明通過三次Dijkstra最短路徑算法從近鄰圖中找到骨架線的示意圖。
圖3(a)為初始SwissRoll數據集的示意圖。
圖3(b)為採用本發明處理後SwissRoll數據集的示意圖。
具體實施方式
為了更為具體地描述本發明，下面結合附圖及具體實施方式對本發明的技術方案進行詳細說明。
本實施例的輸入是歸一化的數據集(取名為DS)，但不限定歸一化方法以及是否需要執行歸一化操作。假設DS含N個點，每個點的坐標是維數為M的列向量。
本實施例藉助近鄰圖來體現數據集在坐標空間中的幾何形態。更具體地說，本實施方式採用KNN法構建近鄰圖。一般來說，KNN的參數K值過小，數據的幾何形狀會被刻畫得過於細緻，從而有使某些相鄰點在平移之後有加劇分離的傾向；K值過大，容易使幾何形狀表達得過於模糊，從而使複雜結構不能得到簡化。具體K值的確定，本實施方式採用自適應方式。設使整個數據集連通的最大K值為K'，我們取K＝min(1.5*K',5％*N)。如此，即可取得較大的K值，又能確保每個點不會與距離遠的點直接發生關聯。在選定K值下，如果數據集不能全連通，則依次將連通分量連接到最靠近的連通分量上，直至全連通。
本實施例在計算數據集中的點在骨架線上的映射位置時，利用了歐氏空間中的餘弦定理公式。設獲得的骨架線為Lg＝[g1,g2,…,gq]，映射位置以離起點g1的骨架距離表示，為負表示往骨架線的g1端延伸方向取值，超過整個長度則表示往gq端延伸方向取值。設Lg長度為c，DS中的點xi到骨架線起點g1的最短路徑距離為b，到其終點gq的最短路徑距離為a。則點xi在Lg上的映射位置點離起點g1的骨架距離為：di＝(b2+c2-a2)/2c，所有點的映射位置形成一個向量vd＝{d1,d2,…,dN}，骨架線上的兩點之間沿著骨架線所經過的長度值稱為骨架距離。採用餘弦公式的原因是，一是數據點與骨架線兩端點相連正好構成由三條(彎曲的)邊形成的封閉線，符合餘弦公式所需參數；二是相近的兩個點通過餘弦映射後落點也相近，具有局部保持性。
本實施例通過數據集DS均值點與原點連線方向(其中原點為始發點)作為DS的展開方向，記為ξ。Lg沿ξ的方向伸展成一條直線段Ls。相應地，在伸展中，Lg上的標記點也隨之移動並停留在Ls。在數學上，根據vd可以計算得到DS在Ls上的標記點集為PS2＝ξ(vd)t。同時，將DS直接向Ls垂直投影，得到當前的投影點集PS1＝ξξtDS。所以DS沿ξ方向的平移展開操作即為DS＝DS+PS2-PS1。
設Rn是n維歐氏空間，點坐標以列向量表示，過原點的直線參數方程為L：x＝vξ，其中v為實數，ξ為n維單位列向量。設空間中一點x0的垂直投影點為x*＝v0ξ，則向量(x0-v0ξ)與ξt的內積應該為0，即ξt(x0-v0ξ)＝0，從中解出v0＝ξtx0，所以x*＝ξv0＝ξξtx0。寫成數據集的形式就是PS1＝ξξtDS。
圖1所示了數據集非線性性的幾何表徵以及展開消減具體實施過程，輸入歸一化的數據集DS，具體為，DS＝{x1,x2,…,xN}。其中，xi(1≤i≤N)是M維向量。
如圖1所示，本發明方法實施例包括以下幾個步驟：
步驟101：以KNN算法根據DS構造近鄰圖G。其中參數K由算法自適應決定。如果G不連通，則將連通分量連接到其最接近的連通分量，直至G連通。具體如下：
1.1按深度優先(DFS)方法確定各個連通分量，如果只有一個連通分量，則停止；
1.2以兩個連通分量之間最短的點間直線距離作為連通分量距離，計算求得每個連通分量的最近連通分量；
1.3將連通分量連接到其最近的連通分量上，返回到步驟1.1。
步驟102：針對圖G，重複執行Dijkstra算法三次，分別求得距隨機選擇的某點的最遠一個點g1，始於g1的所有最短路徑和距離，骨架線Lg＝[g1,g2,…,gq]，以及始於gq的所有最短路徑和距離。圖2給出了相應的示意圖。具體方案為：
如圖2(a)所示，第一次執行Dijkstra算法從近鄰圖中隨機選取的一個點出發，找出離其最短路徑最長的一個點。該點是近鄰圖的一個邊緣點(記為g1)。註：如果一個點(記作B)到另外某一個點(記作A)的最短路徑，不包含於任何其它點到A的最短路徑中，則B是一個邊緣點。
如圖2(b)所示，第二次Dijkstra算法從g1出發，求得g1到其它各點的最短路徑和相應距離{b1,b2,…,bN}。取其最長的那條最短路徑為骨架線，得Lg＝[g1,g2,…,gq]，長度為c。
如圖2(c)所示，第三次Dijkstra算法從gq出發，求得gq到其它各點的最短路徑和相應距離{a1,a2,…,aN}。
步驟103：將DS整體平移，以使點g1正好落在原點上。相當於執行計算：對每個點xi∈DS，執行xi＝xi-g1。此行為主要是為了簡化後面的投影計算。
步驟104：對每個點xi∈DS，以它到Lg始末點的最短路徑距離{bi}和{ai}和Lg的長度值c分別計算它們映射到Lg的位置點距g1的骨架距離di。
步驟105：通過求解數據集均值點得到DS的展開方向向量ξ：
<![CDATA[ ξ = 1 N Σx i , ( x i D S , 1 ≤ i ≤ N ) ]]>
步驟106：過原點，以ξ為方向的展開線記作Ls。對每個點xi∈DS，在Ls上投影得si＝ξξtxi。結合在Ls上的標記點ei＝diξ。對DS中的每個點xi，作平移xi＝xi+(ei-si)。由於每個點都在局部性保持的前提下往遠端伸展，這樣，原來捲曲的網狀圖就自動展開成一個平坦的網狀圖，從而數據集的非線性性得以消減。
本發明針對一個SwissRoll數據集的非線性性消減的效果完整示範見圖3。SwissRoll數據集是在機器學習領域非常有名的人工非線性數據集，它主要用於檢驗非線性算法的性能。圖3(a)顯示的是初始的SwissRoll數據集，圖3(b)顯示的是經過本發明方法展開後的SwissRoll數據集。從圖3可以看來，降低數據非線性性的效果是十分明顯的。
上述的對實施例的描述是為便於本技術領域的普通技術人員能理解和應用本發明。熟悉本領域技術的人員顯然可以容易地對上述實施例做出各種修改，並把在此說明的一般原理應用到其他實施例中而不必經過創造性的勞動。因此，本發明不限於上述實施例，本領域技術人員根據本發明的揭示，對於本發明做出的改進和修改都應該在本發明的保護範圍之內。