Feature　selection　in　large,　incomplete　decision　systems　is　a　challenging　problem.　To　avoid　exponential　computation　in　exhaustive　feature　selection　methods,　many　heuristic　feature　selection　algorithms　have　been　presented　in　rough　set　theory.　However,　these　algorithms　are　still　time-consuming　to　compute.　It　is　therefore　necessary　to　investigate　effective　and　efficient　heuristic　algorithms.　In　this　paper,　rough　entropy-based　uncertainty　measures　are　introduced　to　evaluate　the　roughness　and　accuracy　of　knowledge.　Moreover,　some　of　their　properties　are　derived　and　the　relationships　among　these　measures　are　established.　Furthermore,　compared　with　several　representative　reducts,　the　proposed　reduction　method　in　incomplete　decision　systems　can　provide　a　mathematical　quantitative　measure　of　knowledge　uncertainty.　Then,　a　heuristic　algorithm　with　low　computational　complexity　is　constructed　to　improve　computational　efficiency　of　feature　selection　in　incomplete　decision　systems.　Experimental　results　show　that　the　proposed　method　is　indeed　efficient,　and　outperforms　other　available　approaches　for　feature　selection　from　incomplete　and　complete　data　sets.　Crown　Copyright　(C)　2012　Published　by　Elsevier　B.V.　All　rights　reserved.