跳到主要內容

Framework Of Creating Depend Sets Given Matrix Data

日常生活中,我們常常拿到的資料是一筆筆的。假如有 $n$ 筆資料,$p$ 種屬性,$n \times p$ 矩陣
-------------------------------------------------------------------------
例如 : $(5+1) \times 5$ 資料矩陣
其中第一行(column)為 id 代表第幾筆 !!
有5個給定屬性集依序為
(1)12羅馬字$S^{R} = \{ I ,II , III , .... XII \}$  
(2)小寫英文字母  $\tau = \{a,b,c,d,e,f.....z\}$
(3)大寫字母  $\Gamma = \{A,B,C,D,E,....Z\}$
(4)比例值 $[0,1]$
(5)負數 $\mathbb{Z}^{-}$
$$\left[\begin{array}{c|cccc}
1&III &  c &  C &  0.1 & -9   \\
2&IV &  a &  C &  0.2 &  -999 \\
3&II &  a &  A &  0.5 &  -9999 \\
4&III &  b &  A &  0.5 & -999\\
5&IV &  c &  B &  0.7 & -99 \\
\end{array}\right]$$

這時你會有一連串 Q & A ~~
(Q1) 當 負數為 -99 的資料哪幾筆??
(Q2) 這筆資料總共有哪些大寫英文字母??
(Q3) 當 大寫英文字母為 $A$   且比例值為 $0.5$其他屬性有哪些種 ??
....
而你問的每個問題事實上都是一個收集的概念 !!
像 (Q1) 你會希望印出的是 $\{ 5 \}$ 或是  $(IV, c, B,0.7)$
像 (Q2) 你會希望印出的是 $\{ A,B,C \}$
像 (Q3) 你會希望印出的是 $ \{(II,a ,-9999),(III,b,-999)\}$

當資料大的時候 $n , p $ 很大,你一定會看到花掉....,就算是電腦還要寫搜尋演算法 !!
---------------------------------------------------------------------------
該怎麼有效率的製造不同的集合,並印出想要的結果,從不同角度看同一筆資料呢?? ,尤其在線性規劃(linear programming)領域,加入限制式需要使用集合的概念,於是筆者發展了一套集合符號系統,來表示其資料!!(有用到筆者的一對多函數的概念,Depend Sets,詳細想法可按這) 以數學語言來說,給定一個資料我們可以寫成 $\text{Given } \mathcal{R}$
$$ (i_1,i_2,i_3,....i_p) \in  \mathcal{R} \subseteq   U_1 \times U_2 \times U_3 \times ... \times U_p$$
其中 $U_k , k=1,2,...p$ 是我們大多從生活經驗,自己定義出來的 universal set (support) ,他可能是實數集或是整數集也可能是名目資料集 !! ,而 $(i_1,i_2,i_3,....i_p)$ 代表一筆筆資料的值,而現實上我們是拿到像  $\mathcal{R}$ 這樣的集合,而通常資料都是 sparse 也就是  $ n =\displaystyle{|\mathcal{R}|  << \prod^{p}_{k=1}|U_k|}$ 

[額外聯想]
從動態規劃(Dynamic Programming) 圖論(Graph Theory)表示的觀點來看$\displaystyle{\prod^{p}_{k=1}U_k}$ 可以想成有 $p$個 Stage 構成的 State Space (Nodes),而每個 Stage 之間的 State Space 間的 Arcs 形成 complete bipartite graph ,$\mathcal{R}$ 可以想成一條條長度為$p$的路徑(Path)資料
--------------------------------------------------------------------------
[經典的二維矩陣的例子] 
$10000 \times 10000$ 實數矩陣 $A = [a_{ij}]$ , 可以想成函數: $A :  U_I \times U_J  \Longrightarrow \mathbb{R}$,$I,J,\mathbb{R}$就是上文提到的 universal sets,其中 $U_I = \{1,2,3,4.....10000\}$,$U_J = \{1,2,3,4,....10000\}$ ,可以寫成$(i,j,a_{ij}) \in U_I \times U_J \times \mathbb{R}$ ,很明顯矩陣 $A$ 存的值如果想成集合 $S_A=\{a_{ij}\}$,則 $|S_A| \leq n^2$, $S_A \subset \mathbb{R}$ ,  $(i,j,a_{ij}) \in I \times J \times S_A$,但是當我們考慮存稀疏矩陣(Sparse Matrix),如果有 $99.99\%$ 以上的元素都是$0$的話,也就是 $\mathcal{R} = \{(i,j,a_{ij}) : a_{ij} \neq 0 \} \subseteq  I \times J \times S_A$ ,即$|\mathcal{R}| \approx 10^4  $, 但必須先收集 $E = \{(i,j) : a_{ij} \neq 0 \}$,而事實上更細一點我們還可以收集 $I := \{i : (i,j) \in E \}$ ,
$J := \{j : (i,j) \in E \}$ ,
$\text{Given } j  \quad ,  I_j := \{i : (i,j)\in E \}$ ,
$\text{Given } i \quad ,  J_i := \{j : (i,j)\in E \}$ ,
所以我們可以有以下的式子:
$$  E = I \times J_i  = I_j \times J  \subseteq U_{I}\times U_{J} $$
而 $U_I \times U_J$  在演算法語言稱為 adjacency matrix,$ I \times J_i$ 或   $I_j \times J$ 稱為 adjacency list
[註: Sparse Matrix 不存 $0$ 元素的原因是因為矩陣在做乘法運算的時候,$0$ 乘以任何數還是 $0$ ,而且$0$ 加任何數都是不變,等於有它沒它計算都沒差,例如 : $(1+0) (0+2) = 1 \cdot 0 + 1 \cdot 2 + 0 \cdot 0 + 0 \cdot 2 = 1 \cdot 2 = 2 $ 代表沒必要浪費時間算三個運算 !! ]

[註: 在C++程式語言實作上,$E$ 可以用 pair<$T_1$,$T_2$> ,$I,J$ 可以用 set<$T_1$> , $I_j$ , $J_i$ 可以用 map<$T_1$,set<$T_2$> > ,而 $a_{ij}$ 可以使用 map<$T_3$,double>,其中 $T_1$,$T_2$,$T_3$ 是型別,詳細可參考 pair , set , map !!]


至於為何要收集細節的集合? ,因為在演算法我們通常要去掃矩陣作一些事!!,For 迴圈需要它!!
虛擬碼如下 :
+++++++++++++++++++++++++++
[掃 $U_I \times U_J$]
這是最簡單的寫法
但時間(time complexity)跟空間複雜度(space complexity)都為 $O(U_I \times U_J)$
精確來說 :
For 迴圈上限有 $|U_I| \cdot |U_J| = 10^8$ iterations ,
空間需要有 $|U_I| + |U_J| + \underbrace{3|U_I|\times|U_J|}_{(i,j,(a_{ij}))}$

For $i \in U_I$
$\qquad$ For $j \in U_J$
$\qquad$$\qquad$ If ($a_{ij}\neq 0$) Do something !!
$\qquad$ EndFor
EndFor
+++++++++++++++++++++++++++
以下是比較有效率的寫法,
時間複雜度精確來說 iterations都是
$$\displaystyle{|E| = \sum_{i\in I}|J_i| = \sum_{j\in J}|I_j| = 10^4} $$
但空間複雜度不同!!
+++++++++++++++++++++++++++
[掃 $E$]
空間複雜度為 $ \underbrace{3|E|}_{(i,j,(a_{ij}))}$
For $(i,j) \in E$
$\qquad$ Do something !!
EndFor
+++++++++++++++++++++++++++

+++++++++++++++++++++++++++
[掃 $I \times J_i$]
空間複雜度為 $\displaystyle{|I|+\sum_{i\in I}|J_i|= |I| + |E|} $

For $i \in I$
$\qquad$ For $j \in J_i$
$\qquad$$\qquad$  Do something !!
$\qquad$ EndFor
EndFor
+++++++++++++++++++++++++++

+++++++++++++++++++++++++++
[掃 $J\times I_j$]
空間複雜度為 $\displaystyle{|J|+\sum_{j\in J}|I_j| = |J| +|E|}$

For $j \in J$
$\qquad$ For $i \in I_j$
$\qquad$$\qquad$  Do something !!
$\qquad$ EndFor
EndFor
+++++++++++++++++++++++++++

註: 掃$E$ 的例子,如求解最短路徑(Shortest Path) 的 Bellman - Ford
註: 掃 $I \times J_i$ 的例子,如製作以下的限制式,相當於 $Ax \leq b$ 的 sparse 版本
$$  \forall i \in I , \sum_{j\in J_i}  a_{ij}x_j \leq b_i $$
註: 掃 $J \times I_j$ 的例子,如以下的限制式,相當於 $ y^{T}A \geq c^{T}$ 的 sparse 版本
$$  \forall j \in J , \sum_{i\in I_j}  y_ia_{ij} \leq c_j $$
額外知識 : $Ax \leq b$ 跟 $ y^{T}A \geq c^{T}$ 的關係可以參考  Duality of Linear Programming
註: 事實上我們可以把 $E$ 寫作 $IJ_{\emptyset}$
-------------------------------------------------------------------------
根據以上的例子,為了For 迴圈,我們需要定義一群集合 !!
回顧 : $$ (i_1,i_2,i_3,....i_p) \in  \mathcal{R} \subseteq   U_1 \times U_2 \times U_3 \times ... \times U_p$$
定義:  IndexSet of  $\mathcal{R} \quad \quad  \mathcal{I} := \mathcal{I}(\mathcal{R}) := \{ i_1 , i_2 , i_3 , ... , i_p \}$
選取任意兩個子集  $\mathcal{I}_1 , \mathcal{I}_2 \subset \mathcal{I} $
[註: $\mathcal{I}_1$ 可以看成是有序的向量]
可以定義
$$ \mathcal{I}_1| \mathcal{I}_2 := \{ \mathcal{I}_1  : (i_1 , i_2 , i_3 , ... , i_p) \in \mathcal{R} , \text{Given } \mathcal{I}_{2} \}   $$
筆者稱 :
$\mathcal{I}_1$ 為 vector of collect indexes of $\mathcal{I}$
$\mathcal{I}_2$ 為 set of given indexes of $\mathcal{I}$
在實作上我們只要有個完成程序 $Routine()$
$$  \mathcal{I}_1| \mathcal{I}_2 = Routine( \mathcal{R},\mathcal{I}_1,\mathcal{I}_2 )$$
---------------------------------------------------------------------
例如 :  $\mathcal{I} := \{i,j,k,l\}$ ,給定 $\mathcal{R}$ 使得 $$(i,j,k,l) \in U_I \times U_J \times U_K \times U_L$$
則 $I :=  (i) | \emptyset = \{ i : (i,j,k,l) \in \mathcal{R} \}$
則 $J :=  (j) | \emptyset = \{ j : (i,j,k,l) \in \mathcal{R} \}$
則 $K :=  (k) | \emptyset = \{ k : (i,j,k,l) \in \mathcal{R} \}$
則 $L :=  (l) | \emptyset = \{ l : (i,j,k,l) \in \mathcal{R} \}$
我們可以縮小宇集到
$$(i,j,k,l) \in \mathcal{R} \subset I \times J \times K \times L$$
則 $IJ_{\emptyset} :=  (i,j) | \emptyset = \{ (i,j) : (i,j,k,l) \in \mathcal{R} \}$
則 $JI_{\emptyset} :=  (j,i) | \emptyset = \{ (j,i) : (i,j,k,l) \in \mathcal{R} \}$ (可以換順序!!)
則 $J_{i} :=  (j) | \{i\} = \{ j : (i,j,k,l) \in \mathcal{R} \text{ given } i  \}$
則 $I_{ij} := (i) | \{i,j\} = \{ i : (i,j,k,l) \in \mathcal{R} \text{ given } i,j  \} $
則 $IJK_{l} :=  (i,j,k) | \{l\} = \{ (i,j,k) : (i,j,k,l) \in \mathcal{R} \text{ given } l  \}$
則 $IJKL_{\emptyset} := (i,j,k,l) | \emptyset = \mathcal{R}$

另外我們要掃 $ \mathcal{R}$ 等同於掃 hierarchy structure $$\mathcal{R} = I \times J_i \times K_{ij} \times L_{ijk} = I_j \times J  \times K_{ijl} \times  L_{ij} =  ... = ... =   $$
等價於四層 For 迴圈
For  $i \in I$
$\qquad$For $j \in J_i$
$\qquad$$\qquad$For $k \in K_{ij}$
$\qquad$$\qquad$$\qquad$For $l \in L_{ijk}$
                                              [Do something about $(i,j,k,l)$]
$\qquad$$\qquad$$\qquad$EndFor
$\qquad$$\qquad$EndFor
$\qquad$EndFor
EndFor

等價於四層 For 迴圈
For $j \in J$
$\qquad$For  $i \in I_j$
$\qquad$$\qquad$For $l \in L_{ij}$
$\qquad$$\qquad$$\qquad$For $k \in K_{ijl}$
                                             [Do something about $(i,j,k,l)$]
$\qquad$$\qquad$$\qquad$EndFor
$\qquad$$\qquad$EndFor
$\qquad$EndFor
EndFor

總共有 4! = 24種掃法!!
----------------------------------------------------------------------
但是如果很多 index 很多呢 $|\mathcal{I}|$ 很大,太多 For 迴圈呢??   期待下回分曉 !!

[小結]
這篇算是筆者在寫資料預轉換(Data Transform)上自行研究的方法,充分應用推廣數學集合的概念,事實上給一個資料,我們可以從不同角度看資料,而精確的符號也已經可以定義出來,這些集合可以拿來當 for 迴圈使用,計算複雜度也可以利用這些集合清楚了解,至於如何C++實作上的建議,解決多層 for 迴圈問題,實作計算多重 summation , takemin , takemax,日後會寫一篇~~

[以上純為學術經驗交流知識分享,如有錯誤或建議可留言~~] 
by Plus & Minus 2017.08

留言

這個網誌中的熱門文章

Linear Regression By Using Linear Programming

當拿到一筆資料準備玩統計,往往會想要做線性迴歸( Linear Regression ),找出一個模型( mathematical model )來解釋變數間的關係,一般都是使用平方距離,但是如果我們採用絕對值距離呢?? 而剛好在工業工程( Industrial Engineering ),作業研究( Operation Research ) 領域,發展成熟的線性規劃( Linear Programming ) 恰好可以來解決,是一個跨領域的應用 !! 已經存在有許多商業或open source 軟體,如: Gurobi , Cplex , Xpress , Mosek , SCIP  可以輕易求解大型的線性規劃問題。而不僅如此也可以利用整數規劃( Integer Programming )來做特徵選擇 ( Feature Selection ),甚至可以偵測離群值( Detect Outlier ) !! 本文只介紹最小絕對值和,關於 Feature Selection , Detect Outlier 可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。 [Data Fitting Problem] 給定$n$筆實數型訓練資料 (training data) $\{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p}$ , $y^{k} \in \mathbb{R}$ , 我們目標是想要找到一個函數 $f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R}$ 使得  $\forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y$ , 精確來說: $$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\approx \left\{

Chain Rule & Identity Function Trick

本文為筆者學習微積分,函數概念與Chain Rule 的時候,遇到的一些概念大坑。本文一一澄清一些個人看法,並分享 Chain Rule 廣義的樣子,以及對於遞迴系統該如何計算...等等看法。 [坑1 : 變數/值符號的認識] 一切從 $y = f(x)$ 開始,我們習慣把 Input 變數用"括號"刮起來,Output y 代表值,f 代表函數。或是可以想成這樣:   $$ x \overset{f}{\longrightarrow} y $$ 這種表示法概念上很嚴謹,但缺點是你必須要用三個符號 $x$,$y$,$f$ 而在微分方程領域出現這種寫法 $y = y(x)$  (把 $f$ 換成 $y$) ,這種寫法就頗簡潔,Chain Rule 通常都是這類表示法。缺點是心裡要能確實明白在哪個場合 $y$ 到底是給定的"值"還是"函數"(註: 通常大多代表函數 $y$,值的話通常會這樣寫 $y(x_{0})$,$y_{0}$) ============================================================== [Bonus] $y=y(x)$這種表示法還有一個好處,如果允許 $f$ 是一對多,那麼 $y(x)$ 就是 $y \text{ is depend on } x$ 的意思,如果你喜歡用集合論來表示可以先定義$f$ 的定義域/對應域 $$ f : X \rightarrow Y$$ 然後 $y(x)$ 可以寫成這樣 $y \in Y_{x}$,其中值域為 $$ f(X):=\bigcup_{x \in X}Y_{x} \subseteq Y$$ ============================================================== [坑2 : Input 的變數到底是哪些] 這邊舉兩個例子提醒: (Ex1) 代換法會重新改變函數的 Input 例如 : $y = f(x) = x+1$ , $ z = g(y) = 2y$  可以代換一下,寫成 $z = g[f(x)] = 2(x+1)$ 如果你用簡記你會發現 $y(x) , z(y) , z(y(x)) \equiv z

Probability Model Of Bingo Game

本文介紹經典的"賓果 Bingo" 遊戲,機率與期望值的解析計算公式的計算概念,相關的數學建模....等等 [遊戲情境] 總共有 $n$ 個相異的號碼彩球,號碼集為 $S:=\{1,2,3,....n\}$,今玩家可以花$1$元,買$1$張賓果卡 ($5 \times 5$) 位置座標集 $Z$, $|Z|=25$,然後從$S$ 隨機均勻選擇 $25$個相異的號碼並排列到一個佇列(queue),而開球只會開前 $m$ 顆球,$25 \leq m\leq n$,而給定獎項圖形集 $\color{red}{p \in P := \{Bingo,王,十,一_1,一_2,...,一_5  \}}$ (可自行設計) ,以及已知賠率表向量 $odds_{P}$。開完球後,把Bingo 卡上的中獎的號碼圈起來形成"中獎圖形" ===================================================== 其中獎項圖形 : "$Bingo$" 代表$25$個號碼全中 "十"代表第 $3$ 列(row)  第 $3$ 行 (column) 有中 (共$9$個號碼) "王"代表第 $1$ , $3$ , $5$ 列(row)  第 $3$ 行 (column) 有中 (共$17$個號碼) "$一_k$" 代表第 $k$ 列有中 (共$5$個號碼) ===================================================== 若中獎圖形有涵蓋獎項圖形大致會獲得,賠率 $odds_{p} \times 1 $ 元,但有些合理規則: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $[ 規則 1 ]$ 若獎項圖形 $p_1,p_2$ 有完全重疊$(p_1 \subseteq p_2)$,則以大圖形 $odds_{p_2}$ 賠率算 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $$\color{green}{ 重要假設: 合理的