Computer Science ›› 2022, Vol. 49 ›› Issue (5): 152-158.doi: 10.11896/jsjkx.210300302

• Database & Big Data & Data Science • Previous Articles     Next Articles

Efficient Neighborhood Covering Model Based on Triangle Inequality Checkand Local Strategy

CHEN Yu-si, AI Zhi-hua, ZHANG Qing-hua   

  1. Chongqing Key Laboratory of Computational Intelligence,Chongqing University of Posts and Telecommunications,Chongqing 400065,China
  • Received:2021-03-31 Revised:2021-10-24 Online:2022-05-15 Published:2022-05-06
  • About author:CHEN Yu-si,born in 1994,postgra-duate.His main research interests include rough sets,machine learning and uncertain information processing.
  • Supported by:
    National Natural Science Foundation of China(61876201).

Abstract: Neighborhood covering model is widely used in classification tasks for its simple mechanism and ability to handle complex data.However,the neighborhood covering model has the problem of low efficiency and lack of related research work.To solve this problem,triangle inequality between distances is introduced to improve the efficiency of constructing neighborhood.Meanwhile,local neighborhood covering is defined.The local strategy is used to improve the efficiency of constructing neighborhood covering.In summary,to improve the efficiency,traditional neighborhood covering model is improved from two perspectives,and a neighborhood covering model based on triangle inequality check and local strategy (TI-LNC) is proposed.In addition,current classification algorithms based on neighborhood covering models only classify samples based on neighborhood centers and neighborhood radius,and ignore the sample information in neighborhoods,which affects classification accuracy.To improve the classification accuracy of the neighborhood covering model,the consideration of sample information in the neighborhood is added,and a new classification algorithm based on TI-LNC is designed.The experimental results on 10 UCI data sets show that the proposed model which is reasonable and effective can achieve higher efficiency and better classification accuracy.

Key words: Neighborhood rough set, Neighborhood covering model, Local neighborhood covering, Triangle inequality check

CLC Number: 

  • TP391.9
[1]PAWLAK Z.Rough Set[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.
[2]HU Q H,YU D R,XIE Z X.Neighborhood Classifiers[J].Ex-pert Systems with Applications,2008,34(2):866-876.
[3]LIN T Y.Granular Computing on Binary Relations I:Data mi-ning and Neighborhood Systems[J].Rough Sets in Knowledge Discovery,1998,1:107-121.
[4]WANG Q,QIAN Y H,LIANG X Y,et al.Local Neighborhood Rough Set[J].Knowledge-Based Systems,2018,153:53-64.
[5]HU M,TSANG E C C,GUO Y T,et al.A Novel Approach to Attribute Reduction Based on Weighted Neighborhood Rough Sets[J].Knowledge-Based Systems,2021,220(5):106908.
[6]CHEN Y M,XUE Y,MA Y,et al.Measures of Uncertainty for Neighborhood Rough Sets[J].Knowledge-Based Systems,2017,120:226-235.
[7]XU S P,YANG X B,YU H L,et al.Neighborhood Collaborative Representation Based Classification Method[J].Computer Science,2017,44(9):234-238.
[8]HU Q H,YU D R,LIU J F,et al.Neighborhood Rough SetBased Heterogeneous Feature Subset Selection[J].Information Sciences,2008,178(18):3577-3594.
[9]HU Q H,PEDRYCZ W,YU D R,et al.Selecting Discrete and Continuous Features Based on Neighborhood Decision Error Minimization[J].IEEE Transactions on Systems,Man,and Cybernetics,2009,40(1):137-150.
[10]YAO P,LU Y H.Neighborhood Rough Set and SVM BasedHybrid Credit Scoring Classifier[J].Expert Systems with Applications,2011,38(9):11300-11304.
[11]CHEN H M,LI T R,CAI Y,et al.Parallel Attribute Reduction in Dominance-based Neighborhood Rough Set[J].Information Sciences,2016,373:351-368.
[12]XIA S Y,ZHANG H,LI W H,et al.GBNRS:A Novel Rough Set Algorithm for Fast Adaptive Attribute Reduction in Classification[J/OL].IEEE Transactions on Knowledge and Data Engineering.
[13]JIANG Z H,WANG Y B,XU G,et al.Multi-scale Based Acce-lerator for Attribute Reduction[J].Computer Science,2019,46(12):250-256.
[14]DU Y,HU Q H,ZHU P F,et al.Rule Learning for Classification based on Neighborhood Covering Reduction[J].Information Sciences,2011,181(24):5457-5467.
[15]ZHU P F,HU Q H,YU D R.Ensemble Learning Based on Randomized Attribute Selection and Neighborhood Covering Reduction[J].Acta Electronica Sinica,2012,40(2):273-279.
[16]ZHANG B W,MIN F,CIUCCI D.Representative-based Classification Through Covering-based Neighborhood Rough Sets[J].Applied Intelligence,2015,43(4):840-854.
[17]YUE X D,CHEN Y F,MIAO D Q,et al.Tri-partition Neighborhood Covering Reduction for Robust Classification[J].International Journal of Approximate Reasoning,2017,83:371-384.
[18]YUE X D,CHEN Y F,MIAO D Q,et al.Fuzzy Neighborhood Covering for Three-way Classification[J].Information Sciences,2020,507:795-808.
[19]YUE X D,ZHOU J,YAO Y Y,et al.Shadowed Neighborhoods Based on Fuzzy Rough Transformation for Three-way Classification[J].IEEE Transactions on Fuzzy Systems,2020,28(5):978-991.
[20]PAN Y W,PAN Z B,WANG Y K,et al.A New Fast Search Algorithm for Exact K-nearest Neighbors Based on Optimal Triangle-inequality-based Check Strategy[J].Knowledge-Based Systems,2019,189:105088.
[21]WANG X Y.A Fast Exact K-nearest Neighbors Algorithm for High Dimensional Search Using K-means Clustering and Triangle Inequality[C]//The 2011 International Joint Conference on Neural Networks.IEEE,2011:1293-1299.
[22]CHANG J Y,HE C X.K-means Algorithm Based on Triangle Inequality[J].Computer Engineering and Design,2007,28(21):5094-5096.
[23]WILSON D R,MARTINEZ T R.Improved Heterogeneous Dis-tance Functions[J].Journal of Artificial Intelligence Research,1997,6:1-34.
[24]ZHANG Z L,CAO Z Y,LI Y T.Research Based on Euclid Distance with Weights of K_means Algorithm[J].Journal of Zhengzhou University(Engineering Science),2010,31(1):89-92.
[1] SUN Lin, HUANG Miao-miao, XU Jiu-cheng. Weak Label Feature Selection Method Based on Neighborhood Rough Sets and Relief [J]. Computer Science, 2022, 49(4): 152-160.
[2] YANG Jie,WANG Guo-yin,LI Shuai. Neighborhood Knowledge Distance Measure Model Based on Boundary Regions [J]. Computer Science, 2020, 47(3): 61-66.
[3] RAO Meng,MIAO Duo-qian,LUO Sheng. Rough Uncertain Image Segmentation Method [J]. Computer Science, 2020, 47(2): 72-75.
[4] FAN Xin,CHEN Hong-mei. Stepwise Optimized Feature Selection Algorithm Based on Discernibility Matrix and mRMR [J]. Computer Science, 2020, 47(1): 87-95.
[5] JIANG Ze-hua, WANG Yi-bo, XU Gang, YANG Xi-bei, WANG Ping-xin. Multi-scale Based Accelerator for Attribute Reduction [J]. Computer Science, 2019, 46(12): 250-256.
[6] WANG Rong, LIU Zun-ren, JI Jun. Fast Attribute Reduction Algorithm Based on Importance of Voting Attribute [J]. Computer Science, 2018, 45(7): 197-201.
[7] SUN Lin, PAN Jun-fang, ZHANG Xiao-yu, WANG Wei and XU Jiu-cheng. Multi-label-specific Feature Selection Method Based on Neighborhood Rough Set [J]. Computer Science, 2018, 45(1): 173-178.
[8] HUI Jing-li, PAN Wei, WU Kang-kang and ZHOU Xiao-ying. Attribute Reduction Based on Asymmetric Variable Neighborhood Rough Set [J]. Computer Science, 2015, 42(6): 282-287.
[9] CHEN Tao,HONG Zeng-lin and DENG Fang-an. Hybrid Gene Selection Algorithm Based on Optimized Neighborhood Rough Set [J]. Computer Science, 2014, 41(10): 291-294.
[10] HU Qing-hua,ZHU Peng-fei and ZUO Ming. Gear Fault Diagnosis Based on Margin Distribution Ensemble Optimization [J]. Computer Science, 2013, 40(4): 204-208.
[11] . Quick Reduction Algorithm for High-dimensional Data Sets Based on Neighborhood Rough Set Model [J]. Computer Science, 2012, 39(10): 268-271.
[12] HAN Hu,DANG Jian-wu,REN En-en. Research of Support Vector Classifier Based on Neighborhood Rough Set [J]. Computer Science, 2010, 37(2): 229-231.
Full text



[1] ZHAO Xing-wang,LIANG Ji-ye,GUO Lan-jie. Collaborative Filtering Recommendation Algorithm Based on Space Transformation[J]. Computer Science, 2018, 45(7): 16 -21 .
[2] SUN Jin-guang, RONG Wen-zhao. Research on Regional Age Estimation Model[J]. Computer Science, 2018, 45(8): 41 -49 .
[3] LI Zhou-jun and LI Shui-hua. Survey on Web-based Question Answering[J]. Computer Science, 2017, 44(6): 1 -7 .
[4] ZHENG Pei-zhen, YUAN Chun-chun, LIU Chao, WU Ji, YANG Hai-yan and HU Ning. Traceability Model Oriented to Software Safety Requirement Analysis Process[J]. Computer Science, 2017, 44(4): 30 -34 .
[5] CHEN Guang-zhi,PAN Rong and LI Lei. Survey and Research Trends of Workflow Modeling Techniques[J]. Computer Science, 2014, 41(Z6): 11 -17 .
[6] WANG Jia-li, LI Hui-jia and JIA Chuan-liang. Study of Wireless Sensor Network Model Based on Novel Local World Networks[J]. Computer Science, 2015, 42(Z6): 279 -284 .
[7] LIN Tao, HUANG Ji-feng and GAO Jian-hua. Flame Detection Based on SIFT Algorithm and One Class Classifier with Undetermined Environment[J]. Computer Science, 2015, 42(Z6): 231 -235 .
[8] HU Yan-su, GAO Ang, WANG Zhi-jun and MU De-jun. GPU Application on the Phase-field Simulation[J]. Computer Science, 2015, 42(7): 19 -21 .
[9] HUANG Tao, HUANG Ren and ZHANG Kun. Improved Collaborative Filtering Recommendation Algorithm[J]. Computer Science, 2016, 43(Z6): 400 -403 .
[10] LI Xia,LI Zhan-huai,ZHANG Li-jun,CHEN Qun,LI Ning. MXDR, Distributed Information Retrieval for Multi-XML Document Based on Keywords[J]. Computer Science, 2011, 38(10): 152 -156 .