Using Compression to Find Interesting One Dimensional Cellular Automata

Research output: Contribution to journalArticlepeer-review

Electronic versions

Documents

DOI

This paper proposes a novel method for finding interesting behaviour in complex systems based on compression. A new clustering algorithm has been designed and applied specifically for clustering 1D elementary cellular automata behaviour using the prediction by partial matching (PPM) compression scheme, with the results gathered to find interesting behaviours. This new algorithm is then compared with other clustering algorithms in Weka and the new algorithm is found to be more effective at grouping behaviour that is visually similar in output. Using PPM compression, the rate of change of the cross-entropy with respect to time is calculated. These values are used in combination with a clustering algorithm, such as k-means, to create a new set of clusters for cellular automata. An analysis of the data in each cluster is then used to determine if a cluster can be classed as interesting. The clustering algorithm itself was able to find unusual behaviours, such as rules 167 and 181 which have output that is slightly different from all the other Sierpiński Triangle-like patterns, because their apexes are off-centre by one cell. When comparing the new algorithm with other established ones, it was discovered that the new algorithm was more effective in its ability to group interesting and unusual cellular automata behaviours together.

Keywords

  • Machine Learning, Clustering, Interestingness, Cellular Automata, PPM Compression
Original languageEnglish
Pages (from-to)123–146
Number of pages26
JournalComplex and Intelligent Systems
Volume6
Issue number1
Early online date20 Sept 2019
DOIs
Publication statusPublished - Apr 2020

Total downloads

No data available
View graph of relations