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