# An Ensemble Extreme Learning Machine for Data Stream Classification
## 3 The Basic Principles of CELM
### The Method of Dimensionality Reduction for Data Stream  
Dimensionality reduction is important for data stream classification. It can reduce the dimension of the data and improve the efficiency of the algorithm. In this paper, LLE method [43] is used to handle data stream. Let a data block be \(\mathbf{B}_{i}=\{\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{N}\}\), for a data point \(\mathbf{x}_{i}\), \(i=1,2,\cdots,N\), LLE ([[https://cs.nyu.edu/~roweis/lle/](https://cs.nyu.edu/~roweis/lle/)]([https://cs.nyu.edu/~roweis/lle/](https://cs.nyu.edu/~roweis/lle/))) finds \(k\) neighborhood points of \(\mathbf{x}_{i}\) to reconstruct \(\mathbf{x}_{i}\). The objective function of the optimization problem is as follows:  
\[ \begin{array}{ll}\min~{}J(\mathbf{w})=\sum_{i=1}^{N}\left\|\mathbf{x}_{i}-\sum_{j=1} ^{k}w_{ij}\mathbf{x}_{j}\right\|_{2}^{2}\\ s.t.~{}~{}\sum_{j=1}^{k}w_{ij}=1\end{array}  \tag{11}\]  
where \(w_{ij}\) is the weight of the neighborhood sample \(\mathbf{x}_{j}\). If \(\mathbf{x}_{j}\) is not the neighborhood of \(\mathbf{x}_{i}\), \(w_{ij}=0\). From Equation (11), it follows:  
\[ \begin{array}{ll}J(\mathbf{w})&=\sum_{i=1}^{N}\left\|1\cdot\mathbf{x}_{i}-\sum_{j=1 }^{k}w_{ij}\mathbf{x}_{j}\right\|_{2}^{2}=\sum_{i=1}^{N}\left\|\sum_{j=1}^{k}w_{ij }\mathbf{x}_{i}-\sum_{j=1}^{k}w_{ij}\mathbf{x}_{j}\right\|_{2}^{2}\\ &=\sum_{i=1}^{N}\left\|\sum_{j=1}^{k}w_{ij}(\mathbf{x}_{i}-\mathbf{x}_{j})\right\|_{2 }^{2}=\sum_{i=1}^{N}\left\|(\mathbf{x}_{i}-\mathbf{x}_{j})\mathbf{W}_{i}\right\|_{2}^{2}\\ &=\sum_{i=1}^{N}W_{i}^{T}(\mathbf{x}_{i}-\mathbf{x}_{j})^{T}(\mathbf{x}_{i}-\mathbf{x}_{j})\mathbf{ W}_{i}\end{array}  \tag{12}\]  
where \(\mathbf{W}_{i}=[w_{i1},w_{i2},\cdots,w_{ik}]^{T}\). Let \(\mathbf{Z}_{i}=(\mathbf{x}_{i}-\mathbf{x}_{j})^{T}(\mathbf{x}_{i}-\mathbf{x}_{j})\), so it will have  
\[J(\mathbf{w})=\sum_{i=1}^{N}\mathbf{W}_{i}^{T}\mathbf{Z}_{i}\mathbf{W}_{i}~{}~{}\text{and}~{}~ {}\sum_{j=1}^{k}w_{ij}=\mathbf{W}_{i}^{T}\mathbf{1}_{k}=1 \tag{13}\]  
where \(\mathbf{1}_{k}\) is a vector in which all elements are 1. The optimization function of Equation (13) can be expressed as  
\[L=\sum_{i=1}^{N}\mathbf{W}_{i}^{T}\mathbf{Z}_{i}\mathbf{W}_{i}+\lambda(\mathbf{W}_{i}^{T}\mathbf{1} _{k}-1)\Rightarrow\frac{\partial L}{\partial\mathbf{W}_{i}}=2\mathbf{Z}_{i}\mathbf{W}_{i} +\lambda\mathbf{1}_{k}=0 \tag{14}\]From Equations (13) and (14), it will obtain  
\[\mathbf{W}_{i}=\frac{\mathbf{Z}_{i}^{-1}\mathbf{1}_{k}}{\mathbf{1}_{k}^{T}\mathbf{Z}_{i}^{-1}\mathbf{1}_{k}} \tag{15}\]  
For \(\mathbf{B}_{i}=\{\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{N}\}\), the projection of \(\mathbf{B}_{i}\) in low dimension space is \(\{\mathbf{y}_{1},\mathbf{y}_{2},\cdots,\mathbf{y}_{N}\}\). The objection of dimension reduction is to make the following loss function is minimized. \[ \begin{split}\min&\sum_{i=1}^{N}\left\|\mathbf{y}_{i}- \sum_{j=1}^{k}w_{ij}y_{j}\right\|_{2}^{2}\\ s.t.&\sum_{i=1}^{N}\mathbf{y}_{i}=0\;\;\text{and}\; \frac{1}{N}\sum_{i=1}^{N}\mathbf{y}_{i}\mathbf{y}_{i}^{T}=\mathbf{I}\end{split}  \tag{16}\]  
Equation (16) can be changed as  
\[ \begin{split} J(\mathbf{Y})&=\sum_{i=1}^{N}\left\|\mathbf{y} _{i}-\sum_{j=1}^{k}w_{ij}y_{j}\right\|_{2}^{2}=\sum_{i=1}^{N}\|\mathbf{Y}\mathbf{I}_{i}- \mathbf{Y}\mathbf{W}_{i}\|_{2}^{2}\\ &=tr(\mathbf{Y}^{T}(\mathbf{I}-\mathbf{W})^{T}(\mathbf{I}-\mathbf{W})\mathbf{Y})\end{split}  \tag{17}\]  
Let \(\mathbf{M}=(\mathbf{I}-\mathbf{W})^{T}(\mathbf{I}-\mathbf{W})\), so the objective function of the optimization problem is  
\[ \begin{split}\min&\;J(\mathbf{Y})=tr(\mathbf{Y}^{T}\mathbf{M} \mathbf{Y})\\ s.t.&\mathbf{Y}^{T}\mathbf{Y}=\mathbf{NI}\end{split}