The outcome of data classification is affected not only by the goodness of the classifier, but also by the complexity of the data itself. As a result, quantifying the complexity of the data itself can serve as a reference point for evaluating categorization models. Current approaches to quantifying data complexity overlook the significance of local data complexity in favor of a global viewpoint. In this research, we present a KNN-based data classification complexity measure with dynamic optimisation k-value (C²M_kNN) that gives greater weight to border sample classification difficulty. First, using dynamic optimization, the best k-value for k-Nearest-Neighbors is determined for each dataset. The samples that have a significant impact on classification complexity are next filtered by the kNN algorithm, and the classification complexity of the data is finally assessed. Based on created and real datasets, C²M_kNN performs better in experiments than 11 traditional data categorization complexity metrics.