Using Compression to Find Interesting One Dimensional Cellular Automata
Research output: Contribution to journal › Article › peer-review
Electronic versions
Documents
- 2019 s40747-019-00121-7
Final published version, 4.37 MB, PDF document
Licence: CC BY Show licence
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 language | English |
---|---|
Pages (from-to) | 123–146 |
Number of pages | 26 |
Journal | Complex and Intelligent Systems |
Volume | 6 |
Issue number | 1 |
Early online date | 20 Sept 2019 |
DOIs | |
Publication status | Published - Apr 2020 |
Total downloads
No data available