The　extended　belief　rule-based　(EBRB)　system　is　an　enhancement　of　the　traditional　belief　rule-based　(BRB)　system,　which　extends　the　belief　distribution　of　the　antecedent　attributes.　Compared　with　BRB　system,　EBRB　system　has　stronger　knowledge　expression　ability.　EBRB　system　uses　relational　data　to　generate　rules　based　on　traditional　belief　rule　base,　which　is　simple　and　effective.　However,　EBRB　system　needs　to　traverse　all　the　rules　in　the　rule　base　and　has　the　problems　of　inefficiency　and　inconsistency.　Although　the　existing　search　optimization　methods　can　solve　this　problem　to　some　extent,　they　generally　have　the　shortcomings　of　insufficient　generalization　ability.　In　view　of　this,　this　paper　proposes　a　new　rule　search　optimization　algorithm　based　on　K-means　clustering　tree　(KMT-EBRB).　By　combining　with　the　bagging　algorithm,　an　EBRB　system　based　on　random　clustering　forest　(RKMF-EBRB)　is　implemented.　To　evaluate　the　performance　of　the　developed　model,　this　paper　chooses　12　common　UCI　datasets　for　two　groups　of　experiments.　Firstly,　the　properties　of　EBRB　system　based　on　K-means　tree　and　K-means　forest　are　studied,　and　then　the　new　method　is　compared　with　existing　methods.　The　experimental　results　show　that　K-means　tree　can　improve　the　search　efficiency　of　EBRB　system,　while　random　K-means　clustering　forest　can　further　improve　the　accuracy　and　stability　of　EBRB　reasoning.