Progressive partition-based granular computing and complexity measures

Abstract

Granular computing has received much interest over the past few decades due to its effectiveness and practicality in managing complexity. While it is intuitively believed that complexities in granular computing are linked to granularities, there do not exist any studies to show they have a direct connection. This suggests the need to investigate complexity from a different perspective. Simon’s concept of nearly decomposable systems, which describes complexity from a hierarchical perspective, aligns closely with the hierarchical nature of granular structures. Thus, granular structures can provide a foundation for exploring complexities in granular computing. This study investigates the complexity of the progressive partition-based model of granular computing. We formally define the progressive partitioning tree (PPT), which is the structure used in the progressive partition-based model, and provide a general method that recursively measures the complexity of PPTs. Additionally, we propose a class of interaction-based complexity measures by treating interactions as the source of complexity. These measures can quantitatively explain the complexity differences between structures and the complexity reduction offered by the progressive partition-based model of granular computing.