在分類時，高維度的資料通常需先經降維的前處理，以去除贅累之資訊，並提升分類的效能與速率。若資料分布在一非線性的流形結構(nonlinear manifold)上，線性降維通常難以在降維的過程中，保留原高維度中資料的分離度。局部線性內嵌法(Locally Linear Embedding, LLE)是一個非線性的降維方法，利用維持鄰近關係的結構，來獲得內嵌在高維度空間內的低維度流形分布。
通常在分類時，訓練樣本提供類別之間在特徵空間中的分離度等事前資訊。局部線性內嵌法是一個非監督式(unsupervised)的降維方法，並無利用這些類別資訊。因此，在降維的過程中加入事前資訊，或許能提升分類正確率。實際上，蒐集資料的樣本數通常不足，另外，多類別的資料也可能形成多個非線性的流形，這些原因均將導致資料無法均勻分布在流形結構上。由於這違反了局部線性內嵌法的假設，可能造成鄰近關係圖的不連結。另外，由於局部線性內嵌法降維過程中的一些條件限制，可能導致外圍比較疏離的資料樣本，被吸納至資料內部而無法保持該部分的原有結構。
在這篇研究中，我們提出了類別條件式局部線性內嵌法(Class-Conditional LLE, CLLE)，改善其在分類上的效能。藉由加入類別的資訊，變更局部線性內嵌法降維的準則。我們採用歐式距離及資料相似度兩種度量，目的是為了兼顧資料原有之幾何架構與類別分離度。除此之外，我們重新連結鄰近關係圖來解決不連結的問題；而主成分分析的加入則是用來改善外圍資料樣本可能會被錯納至資料內部的問題。
在實驗的部分，我們選擇了模擬資料跟實際資料測試，參與比較的降維法包括線性降維法及非線性降維法。線性降維法包括主成分分析及線性區別分析(LDA)；非線性降維法包括傳統局部線性內嵌法及統計型局部線性內嵌法(statistical LLE)。大部分的實驗結果顯示，我們提出的方法之分類正確率，都高於其他線性或非線性降維法。這表示在局部線性內嵌法中加入類別資訊，確實能提昇在分類上的效能。

The real-world data in a high dimensional space often contain redundant information, and the intrinsic dimensionality of the data may be low in geometry. Therefore, a dimensionality reduction method is required to apply to data before classification for efficient and effective performance. When data lie on a nonlinear manifold embedded in a high dimensional space, it is difficult to keep data separability for linear dimensionality reduction methods. The locally linear embedding (LLE) performs nonlinear dimensionality reduction on data by discovering a lower-dimensional nonlinear manifold embedded in a higher dimensional space.
For classification, there are usually training samples available for providing the prior knowledge about the data distribution and the class separability in the feature space. LLE is an unsupervised dimensionality reduction method. Incorporating class label information into process may improve the capability of the LLE in multi-class classification. Normally, real-world data are not well-sampled on multiple manifolds in the feature space, which violate the assumption of LLE. There may be gaps between samples within a class and gaps between different classes. Therefore, it may lead to the disconnected neighborhood problem and the sample absorption problem when LLE is used to reduce the dimensionality.
This study presents a class-conditional LLE (CLLE) that modifies the criterion for neighbor selection of the LLE for classification problems. The class statistics and Euclidean measure are both used to determine the neighborhood of a pixel to keep classes separability and preserve data distribution. In CLLE, novel neighborhood graph reconnection and weight computation based on PCA projection are also proposed to deal with neighborhood graph disconnection and sample absorption problems, respectively.
Experiments have been tested on simulated data, UCI data and multi-view hand shape data. Experimental results show that the application of CLLE to classification is superior to or comparable with other LLE-related methods and linear methods PCA and LDA. By incorporating class-prior knowledge into process, the CLLE is applicable to classification problems.

[1] S. C. W. Ong and S. Ranganath, “Automatic sign language analysis: a survey and the future beyond lexical meaning,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 6, pp. 873-891, June 2005.
[2] Y. Cui and J. Weng, “Appearance-based hand sign recognition from intensity image sequence,” Computer Vision and Image Understanding, vol. 78, no. 2, pp. 157-176, May 2000.
[3] K. Arbter, W. E. Snyder, H. Burkhardt and G. Hirzinger, “Application of affine-invariant Fourier descriptors to recognition of 3-D objects,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 7, pp. 640-647, July 1990.
[4] F. S. Chen, C. M. Fu and C. L. Hung, “Hand gesture recognition using a real-time tracking method and hidden Markov models,” Image and Vision Computing, vol. 21, no. 8, pp. 745-758, Aug. 2003.
[5] Y. Wu and T. S. Hung, “View-independent recognition of hand postures,” Proc. of IEEE Int’l. Conf. on Computer Vision and Pattern Recognition, vol. 2, pp. 88-94, June 2000.
[6] K. Fukunaga, Introduction to Statistical Pattern Recognition, second ed., New York: Academic Press, 1990.
[7] H. S. Seung and D. D. Lee, “The manifold ways of perception,” Science, vol. 290, pp. 2268-2269, Dec. 2000.
[8] S. T. Roweis and L. K. Saul, “Nonlinear dimensionality reduction by locally linear embedding,” Science, vol. 290, pp. 2323-2326, Dec. 2000.
[9] J. B. Tenenbaum, V. Silva and J. C. Langford, “A global geometric framework for nonlinear dimensionality reduction,” Science, vol. 290, pp. 2319-2323, Dec. 2000.
[10] D. Ridder, O. Kouropteva, O. Okun, M. Pietikäinen and R. P. W. Duin, “Supervised locally linear embedding,” Proc. of Joint Int’l Conf. on ICANN/ICONIP, pp. 333-341, 2003.

[11] Y.J. Gu, P.F. Hsieh, M.H. Yang, and C.H. Wu, "Multi-view Hand Shape Recognition sing Statistical LLE," Proceedings of the International Computer Symposium, vol. 3, pp.980-984, 2006.
[12] L. Yang, “Building Connected Neighborhood Graphs for Locally Linear Embedding,” 18th Int’l Conf. Pattern Recognition, vol. 4, pp.194-197, 2006.
[13] H. Chang and D.Y. Yeung, “Robust locally linear embedding,” Pattern Recognition, vol. 39, pp.1053-1065, 2006.
[14] M. Belkin and P. Niyogi, “Laplacian eigenmaps and spectral techniques for embedding and clustering,” Neural Information Processing Systems, pp. 585-591, 2001.
[15] L. Yang, “Distance-preserving projection of high-dimensional data for nonlinear dimensionality reduction,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1243-1246, Sep. 2004.
[16] L. K. Saul and S. T. Roweis, “Think globally, fit locally: unsupervised learning of low dimensional manifolds,” Journal of Machine Learning Research, vol. 4, pp. 119-155, 2003.
[17] D. Lian, J. Yang, Z. Zheng and Y. Chang, “A facial expression recognition system based on supervised locally linear embedding,” Pattern Recognition Letters, vol. 26, pp. 2374-2389, 2005.
[18] X. Geng, D. Zhan and Z. Zhou, “Supervised nonlinear dimensionality reduction for visualization and classification,” IEEE Trans. Systems, Man and Cybernetics—Part B:Cybernetics, vol. 35, no. 6, pp. 1098-1107, Dec. 2005.
[19] X. Jia and J. A. Richards, “Cluster-space representation for hyperspectral data classification,” IEEE Trans. Geoscience and Remote Sesing, vol. 40, no. 3, pp. 593-598, March 2002.
[20] X. Jia and J. A. Richards, “Fast k-NN classification using the cluster-space approach,” IEEE Geoscience and Remote Sesing Letters, vol. 2, no. 2, April 2002.
[21] L. Yang, “k-edge connected neighborhood graph for geodesic distance estimation and nonlinear data projection,” Proc. 17th Int’l Conf. Pattern Recognition, vol. 1, pp. 196-199, Aug. 2004.
[22] L. Yang, “Building k edge-disjoint spanning trees of minimum total length for isometric data embedding,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 27, no.10, pp. 1680-1683, Oct. 2005.
[23] P. Perona and M. Polito, “Grouping and dimensionality reduction by locally linear embedding,” Advances in Neural Information Processing Systems 14, pp. 1255-1264, 2002.
[24] S. L. Phung, A. Bouzerdoum and D. Chai, “Skin segmentation using color pixel classification: analysis and comparison,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 1, pp. 148-154, Jan. 2005.
[25] V. Vezhnevets, V. Sazonov and A. Andreeva, “A survey on pixel-based skin color detection techniques.” Proc. Graphicon-2003, Moscow, Russia, pp. 85-92, Sep.2003.
[26] M. H. Yang and N. Ahuja, “Gaussian mixture model for human skin color and its applications in image and video databases,” Conf. on Storage and Retrieval for Image and Video Database, vol. 3656, pp. 458-466, 1999.
[27] R. C. Gonzalez and R. E. Woods, Digital Image Processing, second ed., Addison-Wesley, 2002.