Using Parametric Test to determine the Significance of Banded patterns in N-dimensional 0-1 dataset
Keywords:
Banded pattern, N-dimension, 0-1 data, Parametric test.Abstract
Background: The identification of banded patterns in N-dimensional (ND) 0-1 dataset is one where all the elements in the dimensions are arranged such that the one’s entries are ordered about the center of dimensions. Reordering 0-1 datasets in order to determine banded patterns in data, allows for the identification of interesting pattern that are hidden in the data. The challenge is whether or not the identify banded patterns are significant. Previous work on the significance of banded patterns using parametric test was aimed at 2D and 3D banding algorithms, using a single banding algorithm in each case, which meant no work on the significance of banded patterns using different banding algorithms with different dimensions. Aim: To this end, this paper presents a comparison between ND banding algorithms for 2D and 3D. Method: The approach is to use parametric test on synthetic data, UCI and the real datasets taken from the cattle tracing system (CTS). The ND banding algorithms considered for 2D are:2D banding, barycentric (BC) and 2D sort, and for 3D are: exact-Euclidean, exact-Manhattan variations and the approximate. Results: The experimental results presented shows the significance of banded patterns with p value less than 0.05. However, the post-hoc test result shows a statistically significant difference between 2D banding and BC, 2D banding and 2D sort, exact-Euclidean and exact-Manhattan, exact-Euclidean and the approximate but no significant difference between BC and 2D sort as well as exact-Manhattan and the approximate.
References
Alizadeh, F., Karp, R.M., Newberg, L. A. and Weisser, D.K. (1995). Physical Mapping of Chromosomes: A combinatorial problem in Molecular Biology. Algorithmica, pp. 52-76.
Cheng, Y. and Church, G.M. (2000). Biclustering of expression data. In: ISMB, vol. 8, pp. 93–103.
Myllykangas, S., Himberg, J., Bohling, T., Nagy, B., Hollman, J., & Knuttila, S. (2006). DNA copy number
amplification profiling of human neoplasms. Oncogene 25, pp. 7324–7332
Atkins, J.E., Boman, E.G. and Hendrickson, B. (1998). Spectral algorithm for seriation and the consecutive one’s
problem. J. Computing. SIAM 28, pp. 297–310
Fortelius, M., Kai Puolamaki, M.F. & Mannila, H. (2006). Seriation in paleontological data using Markov chain
monte Carlo methods. PLoS. Computing. Biol., 2, pp. 2.
Garriga, G.C., Junttila, E. and Mannila, H. (2008). Banded structures in binary matrices. In: Proceedings
Knowledge Discovery in Data Mining (KDD 2008), pp.292–300.
Garriga, G.C., Junttila, E. and Mannila, H. (2011). Banded structure in binary matrices. Knowledge Information
System 28(1), pp.197–226.
Makinen, E. and Siirtola, H. (2005). The barycenter heuristic and the reorderable matrix. Informatica 29,
pp.357–363.
Abdullahi, F.B., Coenen, F. and Martin, R. (2014). A novel approach for identifying banded patterns in zero-one
data using column and row banding scores. In: Perner, P. (ed.) MLDM 2014. LNCS (LNAI), Springer, vol.
, pp.58–72.
Abdullahi, F.B., Coenen, F. and Martin, R. (2015). Finding banded patterns in data: the banded pattern mining
algorithm. In: Madria, S., Hara, T.(eds.) DaWaK LNCS, Springer, vol. 9263, pp. 95–107.
Papadimitriou, Ch. H. (1976). The np-completeness of the bandwidth minimization problem. Computing,
vol. 16, pp.263-270.
Koebe, M., & Knochel, J. (1990). On the block alignment problem. Elektronische Informationsverarbeitung
und Kybernetik 26(7), pp. 377–387.
Sugiyama, K., Tagawa, S. and Toda, M. (1981). Methods for visual understanding of hierarchical system
structures. IEEE Trans. Syst. Man Cybernet, vol.11, pp.109–125.
Atkinson, K.E. (2008). An Introduction to Numerical Analysis. John Wiley & Sons, New York, pp. 64
Bertin, J. (1981). Graphics and Graphic Information Processing. Walter de Gruyter, New York.
Bertin, J. (1999). Graphics and graphic information processing. In: Readings in Information Visualization,
Morgan Kaufmann Publishers Inc. pp.62–65.
Liiv, I. (2010). Seriation and matrix reordering methods: an historical overview. Stat. Anal. Data Min,
(2), pp.70–91.
Makinen, E. and Siirtola, H. (2000). Reordering the reorderable matrix as an algorithmic problem. In: Anderson,
M., Cheng, P., Haarslev, V. (eds.) Diagrams 2000. LNCS (LNAI), vol. 1889, pp. 453–468. Springer,
Heidelberghttps://doi.org/10. 1007/3-540-44590-0 37.
Aykanat, C., Pinar, A. and Catalyurek, U. (2004). Permuting sparse rectangular matrices into block-diagonal
form. SIAM Journal of Science Computing. 25, pp.1860–1879.
Deutsch, S.B. and Martin, J.J. (1971). An ordering algorithm for analysis of data arrays. Operation Research
(6), pp.1350–1362.
Cheng, K.Y. (1973a). Minimizing the bandwidth of sparse symmetric matrices. Computing 11(2), pp. 103–110.
Cheng, K.-Y. (1973b). Note on minimizing the bandwidth of sparse, symmetric matrices. Computing 11(1),
pp. 27–30.
Harri, S & Eekki, M. (2005). Constructing and reconstructing of reorderable matrix. Information Visualisation,
vol.4, pp.32-48
Abdullahi, F.B., Coenen, F. and Martin, R. (2016). Banded pattern mining algorithms in multi-dimensional zero-
one data. In: Hameurlain, A., Kung, J., Wagner, R., Bellatreche, L., Mohania, M. (eds.) Transactions on
Large-Scale Data- and Knowledge Centered Systems XXVI. LNCS, vol. 9670, pp. 1–31. Springer,
Heidelberg. https://doi.org/10.1007/978-3-662-49784-5 1
Abdullahi, F.B. and Frans Coenen (2018a). Statistical Significance Testing for Banded Patterns Using Gaussian
distribution. In Proceedings of 1st International Conference on Information Technology in Education and
Development (ITED), Baze University, Abuja 25th-27th April, pp. 209-219.
Abdullahi, F.B. and Frans Coenen (2018b). Multi-Dimensional Banded Pattern Mining. In Proceedings of the
Pacific Rim Knowledge Acquisition Workshop (PKAW2018), in Conjunction with the 15th Pacific Rim
International Conference on Artificial Intelligence (PRICAI 2018), Nanjing, China, 28th-29th, August,
pp. 154 – 169.
Abdullahi, F.B (2018a). Finding Banded Patterns in 2-Dimrnsional Zero-Data Using Weighted Column and
Row scores Nigerian Journal of Scientific Research (NJSR), 17(2), pp. 186-196.
Abdullahi, F.B (2018b). Three-Dimensional Banded Pattern Mining Algorithms Nigerian Journal of Scientific
Research (NJSR), 17(3), pp. 292-302.
Abdullahi, F.B (2019a). Reordering 2-D Binary matrices without permutation generation Nigerian Journal of
Scientific Research (NJSR), 18(3), pp. 195-203.
Abdullahi, F.B (2019b). Statistical Significant Testing For 3-Dimensional Banded Patterns. Katsina Journal of
Natural and Applied Sciences (KAJONAS), 8(2), pp. 144-153.
Abdullahi, F.B. and Hassan, T., (2020). Testing the Significance of 2D banded data using statistical methods
Bayero Journal of Pure and Applied Sciences (BAJOPAS), 13(1), pp. 113-120.
Abdullahi, F.B. and Coenen, F., (2020). Finding banded patterns in large data set using Segmentation Bayero
Journal of Pure and Applied Sciences (BAJOPAS), 13(1), pp. 90-96.
Gupta, S. P. (2013). Statistical Methods. Publisher Sultan Chand & Sons ISBN: 978-81-8054-931-1, 882-1000.
Coenen, F., (2003). LUCS-KDD data generator software. http://www.csc.liv.ac.uk/~frans/
Department of Computer Science, The University of Liverpool, UK.
Blake, C. I. and Merz, C. J., (1998). UCI Repository of Machine Learning Databases.
http://www.ics.uci.edu/mlearn/MLRepository.htm
Nohuddin, P. N. E., Christley, R., Coenen, F & Setzkorn, C. (2010). Trend mining in social networks: A study
using a large cattle movement database. Advances in Data mining, Applications and Theoretical
Aspects LNAI 6171, pp. 464–475.
Abdullahi, F.B., Salihu, I. and Falgore, J. (2021). Determining the Significant of Banded Patterns in 2-Dimensional
Binary-valued Dataset Using Parametric test. Proceedings of International Conference on Computing
and Advances in Information Technology (ICCAIT), ABU, Zaria,15th-17th November, pp. 231-237