Research on Vague soft clustering algorithm based on MapReduce

Wei Wang, Junsheng Wu, Zhu Zhi-xiang2017 · DOI

Abstract

Traditional clustering algorithms based on Vague soft sets struggle with the computational demands of massive datasets. This paper proposes a parallelized Vague soft clustering algorithm leveraging the MapReduce framework. By distributing the calculation of similarity measures and matrix partitioning across a cluster, the algorithm achieves significant improvements in both processing speed and clustering accuracy. Experimental results on a dataset of one million records demonstrate a 7.7x speedup and superior precision compared to serial implementations.

Introduction: The Challenge of Ambiguity at Scale

In modern data mining, capturing the nuance of real-world information is critical. Unlike crisp sets, Vague sets account for both support and opposition to a concept, while soft sets provide a framework for handling parameter-based uncertainty. Their combination, Vague soft sets, is highly effective for decision-making in complex environments.

However, the primary bottleneck in Vague soft clustering is the construction of a similarity matrix. This requires calculating the relationship between every pair of data points, leading to quadratic computational complexity. As datasets grow into the millions, traditional serial algorithms become impractical. This research addresses this scalability gap by parallelizing the process using MapReduce.

Methodology: Parallelizing Similarity

The proposed algorithm utilizes the MapReduce programming model to decompose the clustering task into manageable, distributed chunks. The process is divided into two primary stages:

1. Digital Characteristic Calculation

The first MapReduce job processes the raw Vague soft sets to extract five essential metrics for each data point: true membership, false membership, degree of hesitation, core value, and interval center. These metrics simplify the subsequent similarity calculations.

2. Similarity and Matrix Partitioning

To avoid the "all-to-all" communication overhead typical of similarity matrix construction, the researchers implemented an inverted index strategy. A second MapReduce process calculates the weighted absolute differences between the digital characteristics of data pairs.

The MapReduce architecture used to distribute the clustering workload across master and worker nodes.

The algorithm then performs clustering by iteratively merging data points based on a descending similarity threshold. This allows the clusters to "grow" in parallel across the distributed nodes, effectively dividing project resources.

Experimental Setup and Datasets

The algorithm was rigorously tested using real-world data from a public opinion monitoring platform. This platform tracks micro-blogging activity (similar to Weibo or Twitter) across 200 servers monitoring 150,000 sites. The researchers evaluated five subsets of this data, ranging from 3,000 to 1,000,000 records, to observe how the algorithm scales.

Key Results and Insights

The experiments revealed several critical performance characteristics:

  • Scalability and Speedup: On the largest dataset (1 million records), the parallel algorithm achieved a speedup ratio of 7.737. Interestingly, for very small datasets (under 10,000 records), the traditional serial algorithm was faster due to the initialization overhead of the MapReduce framework.
  • Clustering Accuracy: The MapReduce-based approach significantly outperformed the traditional method in accuracy. For the 1-million-record test, the new algorithm maintained a precision (PRE) of 0.66 and a recall (REC) of 0.75, compared to 0.53 and 0.68 for the serial version, respectively.
  • Handling Complexity: The parallel design proved more robust at identifying irregular or non-spherical clusters, which often pose challenges for traditional Vague soft clustering methods.

Limitations and Future Directions

While the proposed algorithm offers a significant leap in performance for large-scale data, certain limitations remain. The "small data penalty" suggests that the system should ideally include a heuristic to switch between serial and parallel modes based on input size. Furthermore, the clustering results are sensitive to the chosen similarity threshold, suggesting a need for automated threshold optimization in future iterations. Finally, moving from batch processing to real-time streaming analysis remains a key objective for monitoring high-velocity social media data.

Conclusion

By integrating Vague soft set theory with the MapReduce framework, this research provides a scalable solution for complex data clustering. The ability to maintain high accuracy while achieving substantial speedups makes this approach well-suited for the demands of modern big data analytics.

Summary updated

Abstract

Aiming at the problems that traditional clustering algorithm based on Vague soft sets is difficult to deal with massive data, a parallel Vague soft clustering algorithm based on MapReduce is proposed. The algorithm calculate the similarity measure between Vague soft sets based on Map function and Reduce function of the MapReduce programming framework, and Vague similarity matrix is established as the basis for clustering at the same time. Secondly, the Vague matrix is partitioned according to the similarity matrix based on the idea of matrix partition, and we process the block matrix and merge the results based on MapReduce. Finally, the data items is clustered based on the similarity threshold. The contrast experiment between traditional Vague soft clustering algorithm and the new algorithm shows that the proposed algorithm has higher accuracy, it can not only achieve better speedup in large-scale data calculation but also divide project resources effectively and accurately.
BibTeX
@misc{wang2017research,
  author = {Wei Wang and Junsheng Wu and Zhu Zhi-xiang},
  title = {{Research on Vague soft clustering algorithm based on MapReduce}},
  year = {2017},
  doi = {10.2991/iccia-17.2017.54},
}
Figure