Automated and accurate detection of anomalous, terrorist documents is a desired capability among numerous nations all over the world. In this study, we have improved an algorithm [1], which deals with this detection challenge. The training part includes two stages: the first, building fuzzy lexicons and the second, constructing clusters of labeled documents using cluster analysis methodology. We assume having two collections of labeled normal and terrorist documents downloaded from normal and terrorist websites, respectively. Three separate, disjoint fuzzy lexicons and two separate sets of clusters are induced from these two collections. In this chapter, we propose a new approach for constructing the lexicons based on the ratio between keyphrase appearance in terrorist and normal documents. The keyphrases are divided into the following subsets: fuzzy normal – keyphrases that appear mainly in the normal documents, fuzzy terrorist – keyphrases that appear mainly in the terrorist documents, and common – keyphrases, which appear in both types of documents in similar frequency. In the detection stage, we combine an existing clustering-based classification method with the fuzzy lexicons. When classifying a new, incoming document, we count the amount of keyphrases in each fuzzy subset (fuzzy normal, fuzzy terrorist, and common). If the fuzzy normal subset is nonempty and the terrorist subset is empty or vice versa, the document is labeled as normal or terrorist, respectively. Otherwise the sizes of the two fuzzy subsets are compared using some threshold criteria. If a definite conclusion cannot be derived, the distances of the whole document vector from both sets of centroids are calculated to reach a final decision.