Seman, Ali (2013) Partitional clustering algorithms for highly similar and sparseness yshort tandem repeat data / Ali Seman. PhD thesis, Universiti Teknologi MARA.
Abstract
Clustering is an overlapping method found in many areas such as data mining, machine learning, pattern recognition, bioinformatics and information retrieval. The goal of clustering is to group any similar objects into a cluster, while the other objects that are not similar in the different clusters. Meanwhile, YShort Tandem Repeats (YSTR) is the tandem repeats on YChromosome. The YSTR data is now being utilized for distinguishing lineages and their relationships applied in many applications such as genetic genealogy, forensic genetic and anthropological genetic applications. This research tends to partition the YSTR data into groups of similar genetic distances. The genetic distance is measured by comparing the allele values and their modal haplotypes. Nevertheless, the distances among the YSTR data are typically found similar or very similar to each other. They are characterized by the higher degree of similarity of objects in intraclasses and also interclasses. In some cases, they are quite distant and sparseness. This uniqueness of YSTR data has become problematic in partitioning the data using the existing partitional clustering algorithms. The main problem was essentially caused by the mode mechanism (problem P?) which was unable to handle the characteristics of YSTR data, thus producing poor clustering results. The problem has become worst when the initial centroid selection which is also known as problem Po failed to obtain good centroids. These conditions have led the existing partitional algorithms to local minima and empty clusters problems. As a result, a new idea of problem P2 using the objects (medoid) themselves was introduced. The idea was incorporated into a new algorithm called, kApproximate Modal Haplotypes (&AMH) algorithm. Six YSTR data sets were used as a benchmark to evaluate the performances of the algorithm against the other eight partitional clustering algorithms. Out of six data sets, the &AMH algorithm obtained the highest mean accuracy scores for the five data sets and one data set was at equal performance. For the overall performances which were based on the six data sets, the &AMH algorithm recorded the highest mean accuracy scores of 0.93 as compared to the other algorithms: the ^Population (0.91), the &ModesRVF (0.81), the New Fuzzy &Modes (0.80), A:Modes (0.76), &ModesHI (0.76), £Modes HII (0.75), Fuzzy £Modes (0.74) and £ModesUAVM (0.70). A OneWay ANOVA test also indicated that the clustering accuracy scores of &AMH algorithm was significantly different as compared to the other eight partitional algorithms. In addition, the algorithm was also efficient in terms of time complexity which was recorded as O (km(nk) and considered as linear. Thus, the &AMH algorithm has been bounded with good characteristics of a desired algorithm  scalability
Download
Text
TP_ALI SEMAN CS 13_5.pdf Download (1MB) 
Metadata
Item Type:  Thesis (PhD)  

Creators: 


Subjects:  Q Science > QA Mathematics > Evolutionary programming (Computer science). Genetic algorithms > Malaysia  
Divisions:  Faculty of Computer and Mathematical Sciences  
Item ID:  15171  
Uncontrolled Keywords:  Clustering; Algorith  
URI:  http://ir.uitm.edu.my/id/eprint/15171 
Actions (login required)
View Item 