Data mining and knowledge discovery are two important growing research fields in the last two decades due to the abundance of data collected from various sources. The exponentially growing volumes of generated data urge the development of several mining techniques to feed the needs for automatically derived knowledge. Clustering analysis (finding similar groups of data) is a well-established and widely used approach in data mining and knowledge discovery. In this paper, we introduce a clustering technique that uses game theory models to tackle multi-objective application problems. The main idea is to exploit a specific type of simultaneous move games, called congestion games. Congestion games offer numerous advantages ranging from being succinctly represented to possessing Nash equilibrium that is reachable in a polynomial-time. The proposed algorithm has three main steps: 1) it starts by identifying the initial players (or the cluster-heads), 2) it establishes the initial clusters' composition by constructing the game and try to find the equilibrium of the game. The third step consists of merging close clusters to obtain the final clusters. The experimental results show that the proposed clustering approach obtains good results and it is very promising in terms of scalability and performance.
翻译:在过去二十年中,由于从各种来源收集的数据丰富,数据开采和知识发现是两个重要的、不断增长的重要研究领域。生成的数据数量成倍增长,促使开发几种采矿技术,以满足对自动获取的知识的需求。集束分析(调查类似的数据组)是数据开采和知识发现方面的一种既定和广泛使用的方法。在本文件中,我们引入了一种集束技术,利用游戏理论模型解决多目标应用问题。主要想法是利用一种特定类型的同时移动游戏,即所谓的拥堵游戏。收缩游戏提供了许多优势,从简单代表到拥有多球时可以达到的纳什平衡。提议的算法有三个主要步骤:(1)首先确定最初的玩家(或集头),(2)通过构建游戏并试图找到游戏的平衡。第三步是合并近组,以获得最后组。实验结果显示,拟议的集束方法取得了良好的结果,在可缩放性和性方面很有希望。