Network intrusion detection system is an important defense tool for network information security protection， and the complicated and lengthy network intrusion behavior features seriously affect the effectiveness of network intrusion detection. In order to solve the problem of rapid information growth and incomplete data in network intrusion detection， an incremental feature selection algorithm based on neighborhood valued tolerance condition entropy is proposed. Firstly， on the basis of neighborhood valued tolerance granular computing， combined with the remarkable characteristics of conditional entropy in characterizing the uncertainty of features and the correlation or dependency between features， the incremental updating mechanism of neighborhood valued tolerance conditional entropy is studied. Then， based on the update mechanism， an incremental feature selection algorithm for dynamic database is proposed. Finally， the experimental analysis shows that the proposed algorithm can effectively improve the computational efficiency of feature selection in incomplete information systems. The new algorithm has the advantages of low computational complexity and low false alarm rate in the application of network intrusion detection examples， which shows that it can provide effective and feasible concrete methods for network information security protection.