Embodiments of the present invention provide a method and an apparatus for generating a decision tree. The method includes generating an encoded rule set according to a rule set, generating a first weighted undirected graph, and calculating a weight of each side in the first weighted undirected graph. If a weight of a side with a maximum weight in the first weighted undirected graph is greater than a first threshold, a first operation is cyclically performed until a weight of a side with a maximum weight in a newly generated weighted undirected graph is less than or equal to the first threshold and a decision tree is generated for a rule subset corresponding to each vertex respectively in the newly generated weighted undirected graph.