The medicine data are Boolean ones in many situations, and the scale development based on them has not been solved soundly, especially the items weight problem. The methods combining GA and k-NN algorithm is often introduced to cope with the problem. But the present improved k-NN algorithm do not adapt to the weight determination of scale’s items. A new improve methods named the LO-DFWS-based k-NN algorithm is put forward and presented to reduce the heavy time cost problem of the traditional k-NN, especially for the Boolean data in the paper. The availability of it is demonstrated by the theoretical analysis of the time complexity. And actual data test confirms that the speed is advanced by 2-4 times. The results also show that the new algorithm has a good anti-nose property.