The proportionate increase in the size of the data with increase in space implies that clustering and hence outlier detection a very large data set becomes difficult and is a time consuming process. Sampling is one important technique to scale down the size of dataset and to improve the efficiency of clustering. After sampling, allocating unlabeled objects into proper clusters is impossible in the categorical domain. To address the problem, Chen employed a method called MARDL to allocate each unlabeled data point to the appropriate cluster based on NIR (Node Importance Representative) and NNIR (N-Nodeset Importance Representative) algorithms. This paper took off from Chen’s investigation and analyzed and proposed a method for outlier detection using NNIR by finding the resemblance between an unlabeled data point and a cluster. The cluster at which the unlabeled data point gives maximal resemblance is compared with the outlier threshold values to identify the data point appropriate cluster label or an outlier. This paper also proposed a method to find outlier threshold values for all the exiting clusters.