Search Word(s) in Title, Keywords, Authors, and Abstract: Clustering

A New Approach for Hierarchical Dividing to Passenger Nodes in Passenger Dedicated Line
Chanchan Zhao, Feng Liu and Xiaowei Hai
Page: 694~708, Vol. 14, No.3, 2018
10.3745/JIPS.04.0074

Keywords: Hierarchical Dividing, K-Means, Passenger Nodes, Passenger Dedicated line, Self-Organizing Map
Show / Hide Abstract
China possesses a passenger dedicated line system of large scale, passenger flow intensity with uneven distribution, and passenger nodes with complicated relations. Consequently, the significance of passenger nodes shall be considered and the dissimilarity of passenger nodes shall be analyzed in compiling passenger train operation and conducting transportation allocation. For this purpose, the passenger nodes need to be hierarchically divided. Targeting at problems such as hierarchical dividing process vulnerable to subjective factors and local optimum in the current research, we propose a clustering approach based on self-organizing map (SOM) and k-means, and then, harnessing the new approach, hierarchical dividing of passenger dedicated line passenger nodes is effectuated. Specifically, objective passenger nodes parameters are selected and SOM is used to give a preliminary passenger nodes clustering firstly; secondly, Davies–Bouldin index is used to determine the number of clusters of the passenger nodes; and thirdly, k-means is used to conduct accurate clustering, thus getting the hierarchical dividing of passenger nodes. Through example analysis, the feasibility and rationality of the algorithm was proved.


Microblog Sentiment Analysis Method Based on Spectral Clustering
Shi Dong, Xingang Zhang and Ya Li
Page: 727~739, Vol. 14, No.3, 2018
10.3745/JIPS.04.0076

Keywords: Machine Learning, RDM, Sentiment Analysis, Spectral Cluster
Show / Hide Abstract
This study evaluates the viewpoints of user focus incidents using microblog sentiment analysis, which has been actively researched in academia. Most existing works have adopted traditional supervised machine learning methods to analyze emotions in microblogs; however, these approaches may not be suitable in Chinese due to linguistic differences. This paper proposes a new microblog sentiment analysis method that mines associated microblog emotions based on a popular microblog through user-building combined with spectral clustering to analyze microblog content. Experimental results for a public microblog benchmark corpus show that the proposed method can improve identification accuracy and save manually labeled time compared to existing methods.


Clustering Algorithm Considering Sensor Node Distribution in Wireless Sensor Networks
Boseon Yu, Wonik Choi, Taikjin Lee and Hyunduk Kim
Page: 926~940, Vol. 14, No.4, 2018
10.3745/JIPS.03.0102

Keywords: CACD, Clustering, EEUC, Node Distribution, WSN
Show / Hide Abstract
In clustering-based approaches, cluster heads closer to the sink are usually burdened with much more relay traffic and thus, tend to die early. To address this problem, distance-aware clustering approaches, such as energy-efficient unequal clustering (EEUC), that adjust the cluster size according to the distance between the sink and each cluster head have been proposed. However, the network lifetime of such approaches is highly dependent on the distribution of the sensor nodes, because, in randomly distributed sensor networks, the approaches do not guarantee that the cluster energy consumption will be proportional to the cluster size. To address this problem, we propose a novel approach called CACD (Clustering Algorithm Considering node Distribution), which is not only distance-aware but also node density-aware approach. In CACD, clusters are allowed to have limited member nodes, which are determined by the distance between the sink and the cluster head. Simulation results show that CACD is 20%–50% more energy-efficient than previous work under various operational conditions considering the network lifetime.


A Clustering Approach for Feature Selection in Microarray Data Classification Using Random Forest
Husna Aydadenta and Adiwijaya
Page: 1167~1175, Vol. 14, No.5, 2018
10.3745/JIPS.04.0087

Keywords: Classification, Clustering, Dimensional Reduction, Microarray, Random Forest
Show / Hide Abstract
Microarray data plays an essential role in diagnosing and detecting cancer. Microarray analysis allows the examination of levels of gene expression in specific cell samples, where thousands of genes can be analyzed simultaneously. However, microarray data have very little sample data and high data dimensionality. Therefore, to classify microarray data, a dimensional reduction process is required. Dimensional reduction can eliminate redundancy of data; thus, features used in classification are features that only have a high correlation with their class. There are two types of dimensional reduction, namely feature selection and feature extraction. In this paper, we used k-means algorithm as the clustering approach for feature selection. The proposed approach can be used to categorize features that have the same characteristics in one cluster, so that redundancy in microarray data is removed. The result of clustering is ranked using the Relief algorithm such that the best scoring element for each cluster is obtained. All best elements of each cluster are selected and used as features in the classification process. Next, the Random Forest algorithm is used. Based on the simulation, the accuracy of the proposed approach for each dataset, namely Colon, Lung Cancer, and Prostate Tumor, achieved 85.87%, 98.9%, and 89% accuracy, respectively. The accuracy of the proposed approach is therefore higher than the approach using Random Forest without clustering.


A Dependency Graph-Based Keyphrase Extraction Method Using Anti-patterns
Khuyagbaatar Batsuren, Erdenebileg Batbaatar, Tsendsuren Munkhdalai, Meijing Li, Oyun-Erdene Namsrai and Keun Ho Ryu
Page: 1254~1271, Vol. 14, No.5, 2018
10.3745/JIPS.04.0091

Keywords: Dependency Graph, Keyphrase Extraction
Show / Hide Abstract
Keyphrase extraction is one of fundamental natural language processing (NLP) tools to improve many textmining applications such as document summarization and clustering. In this paper, we propose to use two novel techniques on the top of the state-of-the-art keyphrase extraction methods. First is the anti-patterns that aim to recognize non-keyphrase candidates. The state-of-the-art methods often used the rich feature set to identify keyphrases while those rich feature set cover only some of all keyphrases because keyphrases share very few similar patterns and stylistic features while non-keyphrase candidates often share many similar patterns and stylistic features. Second one is to use the dependency graph instead of the word co-occurrence graph that could not connect two words that are syntactically related and placed far from each other in a sentence while the dependency graph can do so. In experiments, we have compared the performances with different settings of the graphs (co-occurrence and dependency), and with the existing method results. Finally, we discovered that the combination method of dependency graph and anti-patterns outperform the state-of-the-art performances.


A Mixed Co-clustering Algorithm Based on Information Bottleneck
Yongli Liu, Tianyi Duan, Xing Wan and Hao Chao
Page: 1467~1486, Vol. 13, No.6, 2017
10.3745/JIPS.01.0019

Keywords: Co-clustering, F-Measure, Fuzzy Clustering, Information Bottleneck, Objective Function
Show / Hide Abstract
Fuzzy co-clustering is sensitive to noise data. To overcome this noise sensitivity defect, possibilistic clustering relaxes the constraints in FCM-type fuzzy (co-)clustering. In this paper, we introduce a new possibilistic fuzzy co-clustering algorithm based on information bottleneck (ibPFCC). This algorithm combines fuzzy co- clustering and possibilistic clustering, and formulates an objective function which includes a distance function that employs information bottleneck theory to measure the distance between feature data point and feature cluster centroid. Many experiments were conducted on three datasets and one artificial dataset. Experimental results show that ibPFCC is better than such prominent fuzzy (co-)clustering algorithms as FCM, FCCM, RFCC and FCCI, in terms of accuracy and robustness.


An Improved Cat Swarm Optimization Algorithm Based on Opposition-Based Learning and Cauchy Operator for Clustering
Yugal Kumar and G. Sahoo
Page: 1000~1013, Vol. 13, No.4, 2017
10.3745/JIPS.02.0022

Keywords: Cat Swarm Optimization, Cauchy Mutation Operator, Clustering, Opposition-Based Learning, Particle Swarm Optimization
Show / Hide Abstract
Clustering is a NP-hard problem that is used to find the relationship between patterns in a given set of patterns. It is an unsupervised technique that is applied to obtain the optimal cluster centers, especially in partitioned based clustering algorithms. On the other hand, cat swarm optimization (CSO) is a new meta- heuristic algorithm that has been applied to solve various optimization problems and it provides better results in comparison to other similar types of algorithms. However, this algorithm suffers from diversity and local optima problems. To overcome these problems, we are proposing an improved version of the CSO algorithm by using opposition-based learning and the Cauchy mutation operator. We applied the opposition-based learning method to enhance the diversity of the CSO algorithm and we used the Cauchy mutation operator to prevent the CSO algorithm from trapping in local optima. The performance of our proposed algorithm was tested with several artificial and real datasets and compared with existing methods like K-means, particle swarm optimization, and CSO. The experimental results show the applicability of our proposed method.


Granular Bidirectional and Multidirectional Associative Memories: Towards a Collaborative Buildup of Granular Mappings
Witold Pedrycz
Page: 435~447, Vol. 13, No.3, 2017
10.3745/JIPS.02.0058

Keywords: Allocation of Information Granularity and Optimization, Bidirectional Associative Memory, Collaborative Clustering, Granular Computing, Multi-directional Associative Memory, Prototypes
Show / Hide Abstract
Associative and bidirectional associative memories are examples of associative structures studied intensively in the literature. The underlying idea is to realize associative mapping so that the recall processes (one- directional and bidirectional ones) are realized with minimal recall errors. Associative and fuzzy associative memories have been studied in numerous areas yielding efficient applications for image recall and enhancements and fuzzy controllers, which can be regarded as one-directional associative memories. In this study, we revisit and augment the concept of associative memories by offering some new design insights where the corresponding mappings are realized on the basis of a related collection of landmarks (prototypes) over which an associative mapping becomes spanned. In light of the bidirectional character of mappings, we have developed an augmentation of the existing fuzzy clustering (fuzzy c-means, FCM) in the form of a so- called collaborative fuzzy clustering. Here, an interaction in the formation of prototypes is optimized so that the bidirectional recall errors can be minimized. Furthermore, we generalized the mapping into its granular version in which numeric prototypes that are formed through the clustering process are made granular so that the quality of the recall can be quantified. We propose several scenarios in which the allocation of information granularity is aimed at the optimization of the characteristics of recalled results (information granules) that are quantified in terms of coverage and specificity. We also introduce various architectural augmentations of the associative structures.


An Improved Zone-Based Routing Protocol for Heterogeneous Wireless Sensor Networks
Liquan Zhao and Nan Chen
Page: 500~517, Vol. 13, No.3, 2017
10.3745/JIPS.03.0072

Keywords: Energy Consumption, Heterogeneous Wireless Sensor Networks, Stable Election Protocol, Zone-Based
Show / Hide Abstract
In this paper, an improved zone-based routing protocol for heterogeneous wireless sensor networks is proposed. The proposed protocol has fixed the sized zone according to the distance from the base station and used a dynamic clustering technique for advanced nodes to select a cluster head with maximum residual energy to transmit the data. In addition, we select an optimal route with minimum energy consumption for normal nodes and conserve energy by state transition throughout data transmission. Simulation results indicated that the proposed protocol performed better than the other algorithm by reducing energy consumption and providing a longer network lifetime and better throughput of data packets


Modeling and Simulation of Scheduling Medical Materials Using Graph Model for Complex Rescue
Ming Lv, Jingchen Zheng, Qingying Tong, Jinhong Chen, Haoting Liu and Yun Gao
Page: 1243~1258, Vol. 13, No.5, 2017
10.3745/JIPS.04.0042

Keywords: Bipartite Graph, BSCS, Drug Scheduling, Medical Rescue, Optimization Matching
Show / Hide Abstract
A new medical materials scheduling system and its modeling method for the complex rescue are presented. Different from other similar system, first both the BeiDou Satellite Communication System (BSCS) and the Special Fiber-optic Communication Network (SFCN) are used to collect the rescue requirements and the location information of disaster areas. Then all these messages will be displayed in a special medical software terminal. After that the bipartite graph models are utilized to compute the optimal scheduling of medical materials. Finally, all these results will be transmitted back by the BSCS and the SFCN again to implement a fast guidance of medical rescue. The sole drug scheduling issue, the multiple drugs scheduling issue, and the backup-scheme selection issue are all utilized: the Kuhn-Munkres algorithm is used to realize the optimal matching of sole drug scheduling issue, the spectral clustering-based method is employed to calculate the optimal distribution of multiple drugs scheduling issue, and the similarity metric of neighboring matrix is utilized to realize the estimation of backup-scheme selection issue of medical materials. Many simulation analysis experiments and applications have proved the correctness of proposed technique and system.


A New Image Clustering Method Based on the Fuzzy Harmony Search Algorithm and Fourier Transform
Ibtissem Bekkouche and Hadria Fizazi
Page: 555~576, Vol. 12, No.4, 2016
10.3745/JIPS.02.0047

Keywords: Fourier Transform, Fuzzy Clustering, Harmony Search, Processing Image, Remote Sensing
Show / Hide Abstract
In the conventional clustering algorithms, an object could be assigned to only one group. However, this is sometimes not the case in reality, there are cases where the data do not belong to one group. As against, the fuzzy clustering takes into consideration the degree of fuzzy membership of each pixel relative to different classes. In order to overcome some shortcoming with traditional clustering methods, such as slow convergence and their sensitivity to initialization values, we have used the Harmony Search algorithm. It is based on the population metaheuristic algorithm, imitating the musical improvisation process. The major thrust of this algorithm lies in its ability to integrate the key components of population-based methods and local search-based methods in a simple optimization model. We propose in this paper a new unsupervised clustering method called the Fuzzy Harmony Search-Fourier Transform (FHS-FT). It is based on hybridization fuzzy clustering and the harmony search algorithm to increase its exploitation process and to further improve the generated solution, while the Fourier transform to increase the size of the image's data. The results show that the proposed method is able to provide viable solutions as compared to previous work


A Virtual Laboratory to Practice Mobile Wireless Sensor Networks: A Case Study on Energy Efficient and Safe Weighted Clustering Algorithm
Amine Dahane, Nasr-Eddine Berrached and Abdelhamid Loukil
Page: 205~228, Vol. 11, No.2, 2015
10.3745/JIPS.02.0019

Keywords: Clustering, Energy Efficiency, Practical Work, Security Attacks, Virtual labs, Wireless Sensor Networks
Show / Hide Abstract
In this paper, we present a virtual laboratory platform (VLP) baptized Mercury allowing students to make practical work (PW) on different aspects of mobile wireless sensor networks (WSNs). Our choice of WSNs is motivated mainly by the use of real experiments needed in most courses about WSNs. These experiments require an expensive investment and a lot of nodes in the classroom. To illustrate our study, we propose a course related to energy efficient and safe weighted clustering algorithm. This algorithm which is coupled with suitable routing protocols, aims to maintain stable clustering structure, to prevent most routing attacks on sensor networks, to guaranty energy saving in order to extend the lifespan of the network. It also offers a better performance in terms of the number of re-affiliations. The platform presented here aims at showing the feasibility, the flexibility and the reduced cost of such a realization. We demonstrate the performance of the proposed algorithms that contribute to the familiarization of the learners in the field of WSNs.


Femtocell Subband Selection Method for Managing Cross- and Co-tier Interference in a Femtocell Overlaid Cellular Network
Young Min Kwon, Hyunseung Choo, Tae-Jin Lee, Min Young Chung and Mihui Kim
Page: 384~394, Vol. 10, No.3, 2014
10.3745/JIPS.03.0008
Keywords: Clustering Method, Femtocell, Frequency Partition, Interference Management
Show / Hide Abstract
The femtocell overlaid cellular network (FOCN) has been used to enhance the capacity of existing cellular systems. To obtain the desired system performance, both cross-tier interference and co-tier interference in an FOCN need to be managed. This paper proposes an interference management scheme that adaptively constructs a femtocell cluster, which is a group of femtocell base stations that share the same frequency band. The performance evaluation shows that the proposed scheme can enhance the performance of the macrocell-tier and maintain a greater signal to interference-plus-noise ratio than the outage level can for about 99% of femtocell users.


A Study of Wireless Sensor Network Routing Protocols for Maintenance Access Hatch Condition Surveillance
Hoo-Rock Lee, Kyung-Yul Chung and Kyoung-Son Jhang
Page: 237~246, Vol. 9, No.2, 2013
10.3745/JIPS.2013.9.2.237
Keywords: Maintenance Hatch, Underground Facilities, WSN, Routing Protocol, ns-2
Show / Hide Abstract
Maintenance Access Hatches are used to ensure urban safety and aesthetics while facilitating the management of power lines, telecommunication lines, and gas pipes. Such facilities necessitate affordable and effective surveillance. In this paper, we propose a FiCHS (Fixed Cluster head centralized Hierarchical Static clustering) routing protocol that is suitable for underground maintenance hatches using WSN (Wireless Sensor Network) technology. FiCHS is compared with three other protocols, LEACH, LEACH-C, and a simplified LEACH, based on an ns-2 simulation. FiCHS was observed to exhibit the highest levels of power and data transfer efficiency.


A Computational Intelligence Based Online Data Imputation Method: An Application For Banking
Kancherla Jonah Nishanth and Vadlamani Ravi
Page: 633~650, Vol. 9, No.4, 2013
10.3745/JIPS.2013.9.4.633
Keywords: Data Imputation, General Regression Neural Network (GRNN), Evolving Clustering Method (ECM), Imputation, K-Medoids clustering, K-Means clustering, MLP
Show / Hide Abstract
All the imputation techniques proposed so far in literature for data imputation are offline techniques as they require a number of iterations to learn the characteristics of data during training and they also consume a lot of computational time. Hence, these techniques are not suitable for applications that require the imputation to be performed on demand and near real-time. The paper proposes a computational intelligence based architecture for online data imputation and extended versions of an existing offline data imputation method as well. The proposed online imputation technique has 2 stages. In stage 1, Evolving Clustering Method (ECM) is used to replace the missing vlaues with cluster centers, as part of the local learnig strategy Stage 2 refines the resultant approximate values using a Genearal Regression Neural Network (GRNN) as part of the global approximation strategy. We also propose extended versions of an existing offline imputation technique. The offline imputation techniques emploly K-Means or K-Medoids and Multi Layer Perceptron (MLP) or GRNN in Stage-1 and Stage-2 respectively. Several experiments were conducted on 8 benchmark datasets and 4 bank related datasets to assess the effectiveness of the proposed online and offline imputation techniques. In terms of Mean Absolute Percentage Error (MAPE), the results indicate that the difference between the proposed best offline imputation method viz., K-Medoids+GRNN and the proposed online imputation method viz., ECM+GRNN is statistically insignificant at a 1% level of significance. Consequently, the proposed online technique, being less expensive and faster, can be employed for imputation instead of the existing and proposed offline imputation techniques. This is the significant outcome of the study. Furthermore, GRNN in stage-2 uniformly reduced MAPE values in both offline and online imputation methods on all datasets.


Automatic Detection of Texture-defects using Texture-periodicity and Jensen-Shannon Divergence
V. Asha, N.U. Bhajantri and P. Nagabhushan
Page: 359~374, Vol. 8, No.2, 2012
10.3745/JIPS.2012.8.2.359
Keywords: Periodicity, Jensen-Shannon Divergence, Cluster, Defect
Show / Hide Abstract
In this paper, we propose a new machine vision algorithm for automatic defect detection on patterned textures with the help of texture-periodicity and the Jensen- Shannon Divergence, which is a symmetrized and smoothed version of the Kullback- Leibler Divergence. Input defective images are split into several blocks of the same size as the size of the periodic unit of the image. Based on histograms of the periodic blocks, Jensen-Shannon Divergence measures are calculated for each periodic block with respect to itself and all other periodic blocks and a dissimilarity matrix is obtained. This dissimilarity matrix is utilized to get a matrix of true-metrics, which is later subjected to Ward"'"s hierarchical clustering to automatically identify defective and defect-free blocks. Results from experiments on real fabric images belonging to 3 major wallpaper groups, namely, pmm, p2, and p4m with defects, show that the proposed method is robust in finding fabric defects with a very high success rates without any human intervention


Texture Comparison with an Orientation Matching Scheme
Nguyen Cao Truong Hai, Do-Yeon Kim and Hyuk-Ro Park
Page: 389~398, Vol. 8, No.3, 2012
10.3745/JIPS.2012.8.3.389
Keywords: Orientation Matching, Texture Analysis, Texture Comparison, K-means Clustering
Show / Hide Abstract
Texture is an important visual feature for image analysis. Many approaches have been proposed to model and analyze texture features. Although these approaches significantly contribute to various image-based applications, most of these methods are sensitive to the changes in the scale and orientation of the texture pattern. Because textures vary in scale and orientations frequently, this easily leads to pattern mismatching if the features are compared to each other without considering the scale and/or orientation of textures. This paper suggests an Orientation Matching Scheme (OMS) to ease the problem of mismatching rotated patterns. In OMS, a pair of texture features will be compared to each other at various orientations to identify the best matched direction for comparison. A database including rotated texture images was generated for experiments. A synthetic retrieving experiment was conducted on the generated database to examine the performance of the proposed scheme. We also applied OMS to the similarity computation in a K-means clustering algorithm. The purpose of using K-means is to examine the scheme exhaustively in unpromising conditions, where initialized seeds are randomly selected and algorithms work heuristically. Results from both types of experiments show that the proposed OMS can help improve the performance when dealing with rotated patterns.


Online Recognition of Handwritten Korean and English Characters
Ming Ma, Dong-Won Park, Soo Kyun Kim and Syungog An
Page: 653~668, Vol. 8, No.4, 2012
10.3745/JIPS.2012.8.4.653
Keywords: Online Handwriting Recognition, Hidden Markov Model, Stochastic Grammar, Hierarchical Clustering, Position Verifier
Show / Hide Abstract
In this study, an improved HMM based recognition model is proposed for online English and Korean handwritten characters. The pattern elements of the handwriting model are sub character strokes and ligatures. To deal with the problem of handwriting style variations, a modified Hierarchical Clustering approach is introduced to partition different writing styles into several classes. For each of the English letters and each primitive grapheme in Korean characters, one HMM that models the temporal and spatial variability of the handwriting is constructed based on each class. Then the HMMs of Korean graphemes are concatenated to form the Korean character models. The recognition of handwritten characters is implemented by a modified level building algorithm, which incorporates the Korean character combination rules within the efficient network search procedure. Due to the limitation of the HMM based method, a postprocessing procedure that takes the global and structural features into account is proposed. Experiments showed that the proposed recognition system achieved a high writer independent recognition rate on unconstrained samples of both English and Korean characters. The comparison with other schemes of HMM-based recognition was also performed to evaluate the system


A Single Mobile Target Tracking in Voronoi-based Clustered Wireless Sensor Network
Jiehui Chen, Mariam B.Salim and Mitsuji Matsumoto
Page: 17~28, Vol. 7, No.1, 2011
10.3745/JIPS.2011.7.1.017
Keywords: Mobile Target Tracking, Sensor Network, Clustering, Voronoi Diagram
Show / Hide Abstract
Despite the fact that the deployment of sensor networks and target tracking could both be managed by taking full advantage of Voronoi diagrams, very little few have been made in this regard. In this paper, we designed an optimized barrier coverage and an energy-efficient clustering algorithm for forming Vonoroi-based Wireless Sensor Networks(WSN) in which we proposed a mobile target tracking scheme (CTT&MAV) that takes full advantage of Voronoi-diagram boundary to improve detectability. Simulations verified that CTT&MAV outperforms random walk, random waypoint, random direction and Gauss-Markov in terms of both the average hop distance that the mobile target moved before being detected and lower sensor death rate. Moreover, we demonstrate that our results are robust as realistic sensing models and also validate our observations through extensive simulations.


A Clustering Protocol with Mode Selection for Wireless Sensor Network
Aries Kusdaryono and Kyung Oh Lee
Page: 29~42, Vol. 7, No.1, 2011
10.3745/JIPS.2011.7.1.029
Keywords: Ad Hoc Network, Wireless Sensor Networks, Clustering, Routing Protocol
Show / Hide Abstract
Wireless sensor networks are composed of a large number of sensor nodes with limited energy resources. One critical issue in wireless sensor networks is how to gather sensed information in an energy efficient way, since their energy is limited. The clustering algorithm is a technique used to reduce energy consumption. It can improve the scalability and lifetime of wireless sensor networks. In this paper, we introduce a clustering protocol with mode selection (CPMS) for wireless sensor networks. Our scheme improves the performance of BCDCP (Base Station Controlled Dynamic Clustering Protocol) and BIDRP (Base Station Initiated Dynamic Routing Protocol) routing protocol. In CPMS, the base station constructs clusters and makes the head node with the highest residual energy send data to the base station. Furthermore, we can save the energy of head nodes by using the modes selection method. The simulation results show that CPMS achieves longer lifetime and more data message transmissions than current important clustering protocols in wireless sensor networks.


A Novel Similarity Measure for Sequence Data
Mohammad. H. Pandi, Omid Kashefi and Behrouz Minaei
Page: 413~424, Vol. 7, No.3, 2011
10.3745/JIPS.2011.7.3.413
Keywords: Sequence Data, Similarity Measure, Sequence Mining
Show / Hide Abstract
A variety of different metrics has been introduced to measure the similarity of two given sequences. These widely used metrics are ranging from spell correctors and categorizers to new sequence mining applications. Different metrics consider different aspects of sequences, but the essence of any sequence is extracted from the ordering of its elements. In this paper, we propose a novel sequence similarity measure that is based on all ordered pairs of one sequence and where a Hasse diagram is built in the other sequence. In contrast with existing approaches, the idea behind the proposed sequence similarity metric is to extract all ordering features to capture sequence properties. We designed a clustering problem to evaluate our sequence similarity metric. Experimental results showed the superiority of our proposed sequence similarity metric in maximizing the purity of clustering compared to metrics such as d2, Smith-Waterman, Levenshtein, and Needleman-Wunsch. The limitation of those methods originates from some neglected sequence features, which are considered in our proposed sequence similarity metric.


Approximate Clustering on Data Streams Using Discrete Cosine Transform
Feng Yu, Damalie Oyana, Wen-Chi Hou and Michael Wainer
Page: 67~78, Vol. 6, No.1, 2010
10.3745/JIPS.2010.6.1.067
Keywords: Grid Density-Based Clustering, Approximate Cluster Analysis, Discrete Cosine Transform, Sampling, Data Reconstruction, Data Compression
Show / Hide Abstract
In this study, a clustering algorithm that uses DCT transformed data is presented. The algorithm is a grid density-based clustering algorithm that can identify clusters of arbitrary shape. Streaming data are transformed and reconstructed as needed for clustering. Experimental results show that DCT is able to approximate a data distribution efficiently using only a small number of coefficients and preserve the clusters well. The grid based clustering algorithm works well with DCT transformed data, demonstrating the viability of DCT for data stream clustering applications.


An Optimized Approach of Fault Distribution for Debugging in Parallel
Maneesha Srivasatav, Yogesh Singh and Durg Singh Chauhan
Page: 537~552, Vol. 6, No.4, 2010
10.3745/JIPS.2010.6.4.537
Keywords: Clustering, Debugging, Fault Localization, Optimization, Software Testing
Show / Hide Abstract
Software Debugging is the most time consuming and costly process in the software development process. Many techniques have been proposed to isolate different faults in a program thereby creating separate sets of failing program statements. Debugging in parallel is a technique which proposes distribution of a single faulty program segment into many fault focused program slices to be debugged simultaneously by multiple debuggers. In this paper we propose a new technique called Faulty Slice Distribution (FSD) to make parallel debugging more efficient by measuring the time and labor associated with a slice. Using this measure we then distribute these faulty slices evenly among debuggers. For this we propose an algorithm that estimates an optimized group of faulty slices using as a parameter the priority assigned to each slice as computed by value of their complexity. This helps in the efficient merging of two or more slices for distribution among debuggers so that debugging can be performed in parallel. To validate the effectiveness of this proposed technique we explain the process using example.


A Geometrical Center based Two-way Search Heuristic Algorithm for Vehicle Routing Problem with Pickups and Deliveries
Kwangcheol Shin
Page: 237~242, Vol. 5, No.4, 2009
10.3745/JIPS.2009.5.4.237
Keywords: Vehicle Routing Problem, Heuristic Algorithm, Initial Solution
Show / Hide Abstract
The classical vehicle routing problem (VRP) can be extended by including customers who want to send goods to the depot. This type of VRP is called the vehicle routing problem with pickups and deliveries (VRPPD). This study proposes a novel way to solve VRPPD by introducing a two-phase heuristic routing algorithm which consists of a clustering phase and uses the geometrical center of a cluster and route establishment phase by applying a two-way search of each route after applying the TSP algorithm on each route. Experimental results show that the suggested algorithm can generate better initial solutions for more computer-intensive meta-heuristics than other existing methods such as the giant-tour-based partitioning method or the insertion-based method.


Inverted Index based Modified Version of K-Means Algorithm for Text Clustering
Taeho Jo
Page: 67~76, Vol. 4, No.2, 2008
10.3745/JIPS.2008.4.2.067
Keywords: String Vector, K Means Algorithm, Text Clustering
Show / Hide Abstract
This research proposes a new strategy where documents are encoded into string vectors and modified version of k means algorithm to be adaptable to string vectors for text clustering. Traditionally, when k means algorithm is used for pattern classification, raw data should be encoded into numerical vectors. This encoding may be difficult, depending on a given application area of pattern classification. For example, in text clustering, encoding full texts given as raw data into numerical vectors leads to two main problems: huge dimensionality and sparse distribution. In this research, we encode full texts into string vectors, and modify the k means algorithm adaptable to string vectors for text clustering.


Feature Extraction of Concepts by Independent Component Analysis
Altangerel Chagnaa, Cheol-Young Ock, Chang-Beom Lee and Purev Jaimai
Page: 33~37, Vol. 3, No.1, 2007
None
Keywords: Independent Component Analysis, Clustering, Latent Concepts.
Show / Hide Abstract
Semantic clustering is important to various fields in the modern information society. In this work we applied the Independent Component Analysis method to the extraction of the features of latent concepts. We used verb and object noun information and formulated a concept as a linear combination of verbs. The proposed method is shown to be suitable for our framework and it performs better than a hierarchical clustering in latent semantic space for finding out invisible information from the data.


Secure Key Management Protocol in the Wireless Sensor Network
Yoon-Su Jeong and Sang-Ho Lee
Page: 48~51, Vol. 2, No.1, 2006
None
Keywords: Cluster, Key Management Protocol, WSN
Show / Hide Abstract
To achieve security in wireless sensor networks (WSN), it is important to be able to encrypt messages sent among sensor nodes. We propose a new cryptographic key management protocol, which is based on the clustering scheme but does not depend on the probabilistic key. The protocol can increase the efficiency to manage keys since, before distributing the keys by bootstrap, the use of public keys shared among nodes can eliminate the processes to send or to receive keys among the sensors. Also, to find any compromised nodes safely on the network, it solves safety problems by applying the functions of a lightweight attack-detection mechanism.


ASVMRT: Materialized View Selection Algorithm in Data Warehouse
Jin-Hyuk Yang and In-Jeong Chung
Page: 67~75, Vol. 2, No.2, 2006
None
Keywords: Materialized views, Data Warehouse, and Clustering
Show / Hide Abstract
In order to acquire a precise and quick response to an analytical query, proper selection of the views to materialize in the data warehouse is crucial. In traditional view selection algorithms, all relations are considered for selection as materialized views. However, materializing all relations rather than a part results in much worse performance in terms of time and space costs. Therefore, we present an improved algorithm for selection of views to materialize using the clustering method to overcome the problem resulting from conventional view selection algorithms. In the presented algorithm, ASVMRT (Algorithm for Selection of Views to Materialize using Reduced Table), we first generate reduced tables in the data warehouse using clustering based on attribute-values density, and then we consider the combination of reduced tables as materialized views instead of a combination of the original base relations. For the justification of the proposed algorithm, we reveal the experimental results in which both time and space costs are approximately 1.8 times better than conventional algorithms.


A Cluster-Based Energy-Efficient Routing Protocol without Location Information for Sensor Networks
Giljae Lee, Jonguk Kong, Minsun Lee and Okhwan Byeon
Page: 49~54, Vol. 1, No.1, 2005
None
Keywords: Wireless sensor networks, ubiquitous sensor networks, cluster-based routing protocol, energy-efficient routing
Show / Hide Abstract
With the recent advances in Micro Electro Mechanical System (MEMS) technology, low cost and low power consumption wireless micro sensor nodes have become available. However, energy-efficient routing is one of the most important key technologies in wireless sensor networks as sensor nodes are highly energy-constrained. Therefore, many researchers have proposed routing protocols for sensor networks, especially cluster-based routing protocols, which have many advantages such as reduced control messages, bandwidth re-usability, and improved power control. Some protocols use information on the locations of sensor nodes to construct clusters efficiently. However, it is rare that all sensor nodes know their positions. In this article, we propose another cluster-based routing protocol for sensor networks. This protocol does not use information concerning the locations of sensor nodes, but uses the remaining energy of sensor networks and the desirable number of cluster heads according to the circumstances of the sensor networks. From performance simulation, we found that the proposed protocol shows better performance than the low-energy adaptive clustering hierarchy (LEACH).