基于P系统的共享近邻聚类算法及其面部图像处理应用
|
摘要
共享近邻聚类(SNN)是一种基于图的聚类算法,能够在不预设聚类数目的前提下,很好得区分彼此相似的邻近簇。然而SNN因计算开销太大,不适于处理大数据量、高属性维数据。P系统是一种并行分布式生物计算模型,具有与图灵机等价的强大计算能力。本文将SNN与P系统相结合,设计了一种含有多促进剂和多抑制剂的类细胞P系统,提出了基于该系统的膜聚类算法,称为共享近邻膜聚类算法(SNN-P)。最后,用Olivetti Face数据集验证了SNN-P在人脸识别中的有效性。理论分析表明SNN-P相比于传统聚类算法具有极低的时间复杂度,实验结果表明SNN-P对面部图像具有良好的识别能力。
Shared Nearest Neighbor( SNN) is a clustering algorithm based on graph theory,which can distinguish similar neighboring clusters without presetting cluster numbers. However,SNN is not suitable for processing large data sets and high dimensional data sets due to its high computational cost. As a powerful distributed parallel computing device,P system has the computing power equivalent to Turing machine. In this paper,SNN and P system are combined to design a cell-like P systems with multi-promoters and multi-inhibitors. Based on this system,a novel membrane clustering algorithm named Shared Nearest Neighbor Clustering Algorithm Based on P System( SNN-P) is proposed.In addition,the Olivetti Face dataset is used to illustrate the effectiveness of SNN-P in face recognition. The theoretical analysis shows that SNN-P has a very low time complexity compared with traditional clustering algorithm. Experimental results show that SNN-P has a good ability in facial image recognition.
Shared Nearest Neighbor( SNN) is a clustering algorithm based on graph theory,which can distinguish similar neighboring clusters without presetting cluster numbers. However,SNN is not suitable for processing large data sets and high dimensional data sets due to its high computational cost. As a powerful distributed parallel computing device,P system has the computing power equivalent to Turing machine. In this paper,SNN and P system are combined to design a cell-like P systems with multi-promoters and multi-inhibitors. Based on this system,a novel membrane clustering algorithm named Shared Nearest Neighbor Clustering Algorithm Based on P System( SNN-P) is proposed.In addition,the Olivetti Face dataset is used to illustrate the effectiveness of SNN-P in face recognition. The theoretical analysis shows that SNN-P has a very low time complexity compared with traditional clustering algorithm. Experimental results show that SNN-P has a good ability in facial image recognition.
引文
[1]HRUSCHKA E R,FREITAS A A.A Survey of Evolutionary Algorithms for Clustering.[J].IEEE Transactions on Systems Man&Cybernetics Part C Applications&Reviews,2009,39(2):133-155.
[2]KIM S E,JEON J J,EOM I K.Image contrast enhancement using entropy scaling in wavelet domain[J].Signal Processing,2016,127:1-11.
[3]PˇAUN,Gh.Computing with membranes[J].Journal of Computer and System Sciences,2000,61(1):108-143.
[4]ZHANG X,PAN L,Pˇaun,A.On the universality of axon P systems[J].IEEE Transactions on Neural Networks and Learning Systems,2015,26(11):2816-2829.
[5]SONG B,PAN L,P'erez-Jim'enez,M J.Tissue P systems with protein on cells[J].Fundamenta Informaticae,2016,144(1):77-107.
[6]PENG H,WANG J,P'EREZ-Jim'enez,M J,Riscos-N'u~nez,A.An unsupervised learning algorithm for membrane computing[J].Information Sciences,2015,304:80-91.
[7]PAN,L,Pˇaun,Gh,Song,B.Flat maximal parallelism in P systems with promoters[J].Theoretical Computer Science,2016,623:83-91.
[8]MARTINEZ-del-Amor M A,GARCIA-Quismondo M,MACIAS-Ramos L F,et al,Simulating P systems on GPUdevices:a survey[J],Fundamenta Informaticae,2015,136(3):269-284.
[9]LIU X,XUE J,A Cluster Splitting Technique by Hopfield Networks and P Systems on Simplices[J],Neural Processing Letters,2017,24(1)1-24.
[10]YUAN W,ZHANG G,PEREZ-Jiménez M J,et al,P systems based computing polynomials:design and formal verification[J],Natural Computing,2016,15(4):591-596.
[11]ZHANG G,RONG H,CHENG,J,Qin Y.A populationmembrane-system-inspired evolutionary algorithm for distribution network reconfiguration[J].Chinese Journal of E-lectronics,2014,23(3):437-441.
[12]ZENG X,XU L,LIU X,Pan L.On languages generated by spiking neural P systems with weights[J].Information Sciences,2014,278(10):423-433.
[13]WANG J,SHI,P.,PENG,H.Membrane computing model for IIR filter design[J].Information Sciences,2016,329:164-176.
[14]ALTMAN N S.An Introduction to Kernel and NearestNeighbor Nonparametric Regression[J].The American Statistician,1992,46(3):175-185.
[15]陈梅.面向复杂数据的聚类算法研究[D].兰州:兰州大学计算机应用技术,2016.
[16]JARVIS R A,PATRICK E A.Clustering using a similarity measure based on shared near neighbors[J].IEEE Transactions on Computers,1973,11(22):1025-1034.
[17]SONG B,M J Pérez-Jiménez,L.Pan,Computational efficiency and universality of timed P systems with membrane creation[J],Soft Computing,2015,19(11),3043-3053.
[18]SONG T,ZHENG P,WONG M L D,Wang X Design of logic gates using spiking neural P systems with homogeneous neurons and astrocytes-like control[J].Information Sciences,2016,372:380-391.
[19]PAN L,PˇAUN,G.On parallel array P systems automata,Universality,Computation[J].Springer International Publishing,2015:171-181.
[20]PENG H,WANG J,REZ-Jim,et al.Optimal multi-level thresholding with membrane computing[J].Digital Signal Processing,2015,37(1):53-64.
[21]SINGH G,Deep K,A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku[J],Applied Soft Computing,2016,45:27-39.
[22]SAMARIA F S,ANDY C Harter.Parameteri-sation of a stochastic model for human face identification[C]//In Applications of Computer Vision,1994.,Proceedings of the Second IEEE Workshop on,pages 138-142.IEEE,1994.
[23]MEHUL P Sampat,ZHOU Wang,SHALINI Gupta,ALANConrad Bovik,MIA K Markey.Complex wavelet structural similarity:A new image similarity index[J].Image Processing,IEEE Transactions on,18(11):2385-2401,2009.
[24]ALEX Rodriguez,ALESSANDRO Laio.Clustering by fast search and find of density peaks[J].Science,344(6191):1492-1496,2014.
[2]KIM S E,JEON J J,EOM I K.Image contrast enhancement using entropy scaling in wavelet domain[J].Signal Processing,2016,127:1-11.
[3]PˇAUN,Gh.Computing with membranes[J].Journal of Computer and System Sciences,2000,61(1):108-143.
[4]ZHANG X,PAN L,Pˇaun,A.On the universality of axon P systems[J].IEEE Transactions on Neural Networks and Learning Systems,2015,26(11):2816-2829.
[5]SONG B,PAN L,P'erez-Jim'enez,M J.Tissue P systems with protein on cells[J].Fundamenta Informaticae,2016,144(1):77-107.
[6]PENG H,WANG J,P'EREZ-Jim'enez,M J,Riscos-N'u~nez,A.An unsupervised learning algorithm for membrane computing[J].Information Sciences,2015,304:80-91.
[7]PAN,L,Pˇaun,Gh,Song,B.Flat maximal parallelism in P systems with promoters[J].Theoretical Computer Science,2016,623:83-91.
[8]MARTINEZ-del-Amor M A,GARCIA-Quismondo M,MACIAS-Ramos L F,et al,Simulating P systems on GPUdevices:a survey[J],Fundamenta Informaticae,2015,136(3):269-284.
[9]LIU X,XUE J,A Cluster Splitting Technique by Hopfield Networks and P Systems on Simplices[J],Neural Processing Letters,2017,24(1)1-24.
[10]YUAN W,ZHANG G,PEREZ-Jiménez M J,et al,P systems based computing polynomials:design and formal verification[J],Natural Computing,2016,15(4):591-596.
[11]ZHANG G,RONG H,CHENG,J,Qin Y.A populationmembrane-system-inspired evolutionary algorithm for distribution network reconfiguration[J].Chinese Journal of E-lectronics,2014,23(3):437-441.
[12]ZENG X,XU L,LIU X,Pan L.On languages generated by spiking neural P systems with weights[J].Information Sciences,2014,278(10):423-433.
[13]WANG J,SHI,P.,PENG,H.Membrane computing model for IIR filter design[J].Information Sciences,2016,329:164-176.
[14]ALTMAN N S.An Introduction to Kernel and NearestNeighbor Nonparametric Regression[J].The American Statistician,1992,46(3):175-185.
[15]陈梅.面向复杂数据的聚类算法研究[D].兰州:兰州大学计算机应用技术,2016.
[16]JARVIS R A,PATRICK E A.Clustering using a similarity measure based on shared near neighbors[J].IEEE Transactions on Computers,1973,11(22):1025-1034.
[17]SONG B,M J Pérez-Jiménez,L.Pan,Computational efficiency and universality of timed P systems with membrane creation[J],Soft Computing,2015,19(11),3043-3053.
[18]SONG T,ZHENG P,WONG M L D,Wang X Design of logic gates using spiking neural P systems with homogeneous neurons and astrocytes-like control[J].Information Sciences,2016,372:380-391.
[19]PAN L,PˇAUN,G.On parallel array P systems automata,Universality,Computation[J].Springer International Publishing,2015:171-181.
[20]PENG H,WANG J,REZ-Jim,et al.Optimal multi-level thresholding with membrane computing[J].Digital Signal Processing,2015,37(1):53-64.
[21]SINGH G,Deep K,A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku[J],Applied Soft Computing,2016,45:27-39.
[22]SAMARIA F S,ANDY C Harter.Parameteri-sation of a stochastic model for human face identification[C]//In Applications of Computer Vision,1994.,Proceedings of the Second IEEE Workshop on,pages 138-142.IEEE,1994.
[23]MEHUL P Sampat,ZHOU Wang,SHALINI Gupta,ALANConrad Bovik,MIA K Markey.Complex wavelet structural similarity:A new image similarity index[J].Image Processing,IEEE Transactions on,18(11):2385-2401,2009.
[24]ALEX Rodriguez,ALESSANDRO Laio.Clustering by fast search and find of density peaks[J].Science,344(6191):1492-1496,2014.