Generally, when talking about attribute reduction of a decision table, it usually keeps the positive region unchanged based on the Pawlak’s rough sets theory. However, the needs may be different for different precision of the reduction in real life as well as the actual cost to obtain attribute values and personal preferences. Based on the risk of personal preference for the subjective aspect, the accuracy of reduction, the actual cost of obtaining attribute value, and the risk of interval misjudgment for the objective aspects, a novel attribute reduction algorithm is proposed. Then, the relationship between the reduction cost and the reduction accuracy is discussed. Based on the genetic algorithm, a heuristic method for searching the local optimal reduction subset is proposed. Simulation experiments show that the algorithm is feasible, and more realistic to deal with practical decision-making problems.