Computation of a minimum attribute reduct of a decision table, which is known as an NP-hard nonlinearly constrained optimization problem, is equivalently transformed in this paper into an unconstrained binary optimization problem. An improved binary particle swarm optimization algorithm combined with some immunity mechanism is then proposed to solve the transformed optimization problem. Vaccination based on the discernibility matrix of the decision table is introduced for accelerating the search process in the algorithm. Experimental results on a number of data sets show that the proposed algorithm remarkably outperforms some recent global optimization techniques based algorithms for minimum attribute reduction in both quality of solution and computational complexity.