Either using misuse detection or anomaly detection techniques to design intrusion detection systems, a large amount of traffic data is necessary to be collected in advance for analysis. However, the data always enclose uncertainties due to only limited intrusive information available and ambiguous information about computer users' activities. While designing intrusion detection systems, these uncertainties should be taken into consideration. Hence, we propose to incorporate fuzzy clustering technique and Dempster-Shafer theory into our intrusion detection design for their merits of resolving uncertainty problems caused by ambiguous and limited information during a decision process. Also, the k-nearest neighbors (k-NN) technique is applied to speed up the detection process. For verifying the detection accuracy of our classifier, User to Root and Remote to Local attacks of DARPA KDD99 Intrusion Detection Evaluation data set were used. We compared the results of our proposed approach with those of k-NN classifier, fuzzy k-NN classifier and evidence-theoretic k-NN classifier. It indicates that our approach has achieved higher detection rates than those of from the other three classifiers.