Browsing by Author "Liang, Tyne"

Now showing 1 - 20 of 36

A case-based reasoning approach to zero anaphora resolution in Chinese texts
(2006)
Wu, Dian-Song
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Anaphora is a common phenomenon in discourses as well as an important research issue in the applications of natural language processing. In this paper, both intra-sentential and inter-sentential zero anaphora in Chinese texts are addressed. Unlike general rule-based approaches, our resolution method is embedded with a case-based reasoning mechanism which has the benefit of knowledge acquisition if the case size varies. In addition, the presented approach employs informative features with the help of two outer knowledge resources. Compared to rule-based approaches, our resolution to 1047 zero anaphora instances achieved 82% recall and 77% precision.
A CROSS-TEXT ANNOTATION SHARING MECHANISM FOR ENHANCING STUDENTS' COMPREHENSION OF POETRY
(2012-10-01)
Yang, Che-Ching
;
Tseng, Shian-Shyong
;
Shih, Wen-Chung
;
Liang, Tyne
;
資訊工程學系
Poems are usually expressed with elaborate rhetoric techniques, which make them hard to be understood. In this study, a cross-text annotation sharing mechanism is proposed to help students comprehend poetry by creating and sharing individual annotations. Furthermore, relevant annotations among various texts can be retrieved to stimulate and help students make connections while reading. A quasi-experiment has been conducted to evaluate the effectiveness of the proposed approach. The experimental results show that a cross-text annotation sharing approach is significantly more helpful to the students for poetry comprehension than a conventional annotation sharing approach in terms of learning achievements; moreover, the students highly accepted the developed learning system in terms of "ease of use" and "usefulness."
A design of a vortex flow data management and analysis system
(2007-05-01)
Liang, Tyne
;
Hung, Yan-Dung
;
資訊工程學系
;
Department of Computer Science
In this paper, a flow data management and analysis system that can automatically extract features and present summaries of flow fields for the researcher was presented by applying information extraction and mining techniques. The informative vortex features were extracted by using a content-based feature extractor. Shot detection was implemented on the basis of a Maximum-Block-Difference method and global clustering was implemented with semi-Hausdorff distance measure. On the other hand, the frequent patterns in data sequences and the hidden relations among visual features were also discovered by the application of mining techniques. The implementation of this system is believed to benefit both the information scientist in the context of knowledge discovery and at the same time help develop a good data management system for fluid dynamists to better deal with flow data.
A Folksonomy-based Guidance Mechanism for Context-aware Ubiquitous Learning: A Case Study of Chinese Scenic Poetry Appreciation Activities
(2012-01-01)
Shih, Wen-Chung
;
Tseng, Shian-Shyong
;
Yang, Che-Ching
;
Lin, Chih-Yu
;
Liang, Tyne
In this work ubiquitous learning technologies are applied to Chinese scenic poetry appreciation. A folksonomy-based approach is proposed to accumulate knowledge about poems and their corresponding scenic spots. A user can use a "Tagging" operation by a smart phone to associate a concept (a word, a phrase or a sentence) with a scenic spot. These associations will be recorded in a folksonomy, which is then transformed into a Learning Guidance Tree to support personalized guidance in u-learning environments. The purpose of this work is to propose a folksonomy-based guidance mechanism. Also, we attempt to find students' and teachers' attitudes towards the innovative application through a case study. To show the effectiveness of the innovative approach, a ubiquitous learning system was developed to conduct Chinese scenic poetry appreciation activities for a fifth-grade Chinese course in Taiwan, in which forty-eight students participated. The survey results show that the system had a positive impact on students' learning, especially on the affective domain including participation, motivation and interaction.
A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
(2009-04-01)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
In the paper "Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges" (J. Comb. Optim. 13:153-162, 2007), the authors claimed that an n-dimensional hypercube can be embedded with (n-1-f)-mutually independent Hamiltonian cycles when fa parts per thousand currency signn-2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to explain why the proof is deficient. Then we present a correct proof.
A Two-Stage Learning Method for Response Prediction
(2015)
Chen, Kuan-Hsi
;
Ting, Zih-Yun
;
Shen, Jia-Ying
;
Hu, Yuh-Jyh
;
Liang, Tyne
Social networks have become a popular and powerful communication platform as the mobile technology evolves. To evaluate the influence of a message on a social network, response prediction is crucial in modeling the message propagation and interaction among users. To predict whether a new message will receive responses, we propose a two-stage learning method using a new set of features derived from the messages, the users and their responding behaviors. This method first clusters the messages, and then learns the different prediction models from the clusters respectively. The central argument for this two-stage strategy is that the classifiers trained separately from the clustered data sets can focus on particular types of data, reduce the effects of noise, and consequently have an overall higher predictive performance than a single classifier trained from the entire data set. We tested the proposed two-stage learner on Plurk, and compared it with other classifiers. The experimental results show that the two-stage learner outperformed the gradient boosting decision tree learner, the logistic function learner, and the support vector machine for not only the predictive accuracy, but also for the efficiency.
An efficient algorithm for mining high utility itemsets with negative item values in large databases
(2009-09-15)
Chu, Chun-Jung
;
Tseng, Vincent S.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Utility itemsets typically consist of items with different values such as utilities, and the aim of utility mining is to identify the itemsets with highest utilities. In the past studies on utility mining, the values of utility itemsets were considered as positive. In some applications, however, an itemset may be associated with negative item values. Hence, discovery of high utility itemsets with negative item values is important for mining interesting patterns like association rules. In this paper, we propose a novel method, namely HUINIV (High Utility Itemsets with Negative Item Values)-Mine, for efficiently and effectively mining high utility itemsets from large databases with consideration of negative item values. To the best of our knowledge, this is the first work that considers the concept of negative item values in utility mining. The novel contribution of HUINIV-Mine is that it can effectively identify high utility itemsets by generating fewer high transaction-weighted utilization itemsets such that the execution time can be reduced substantially in mining the high utility itemsets. In this way, the process of discovering all high utility itemsets with consideration of negative item values can be accomplished effectively with less requirements on memory space and CPU I/O. This meets the critical requirements of temporal and spatial efficiency for mining high utility itemsets with negative item values. Through experimental evaluation, it is shown that HUINIV-Mine outperforms other methods substantially by generating much less candidate itemsets under different experimental conditions. (C) 2009 Elsevier Inc. All rights reserved.
An efficient algorithm for mining temporal high utility itemsets from data streams
(2008-07-01)
Chu, Chun-Jung
;
Tseng, Vincent S.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Utility of an itemset is considered as the value of this itemset, and utility mining aims at identifying the itemsets with high utilities. The temporal high utility itemsets are the itemsets whose support is larger than a pre-specified threshold in current time window of the data stream. Discovery of temporal high utility itemsets is an important process for mining interesting patterns like association rules from data streams. In this paper, we propose a novel method, namely THUI (Temporal High Utility Itemsets)-Mine, for mining temporal high utility itemsets from data streams efficiently and effectively. To the best of our knowledge, this is the first work on mining temporal high utility itemsets from data streams. The novel contribution of THUI-Mine is that it can effectively identify the temporal high utility itemsets by generating fewer candidate itemsets such that the execution time can be reduced substantially in mining all high utility itemsets in data streams. In this way, the process of discovering all temporal high utility itemsets under all time windows of data streams can be achieved effectively with less memory space and execution time. This meets the critical requirements on time and space efficiency for mining data streams. Through experimental evaluation, THUI-Mine is shown to significantly outperform other existing methods like Two-Phase algorithm under various experimental conditions. (c) 2007 Elsevier Inc. All rights reserved.
An Integration of Fuzzy Association Rules and WordNet for Document Clustering
(2009)
Chen, Chun-Ling
;
Tseng, Frank S. C.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
With the rapid growth of text documents, document clustering has become one of the train techniques for organizing large amount of documents into a small number of meaningful clusters. However, there still exist several challenges for document clustering, such as high dimensionality, scalability. accuracy, meaningful cluster labels, and extracting semantics from texts. In order to improve the quality of document clustering results, we propose an effective Fuzzy Frequent Itemset-based Document Clustering (F(2)IDC) approach that combines fuzzy association rule mining with the background knowledge embedded in WordNet. A term hierarchy generated from WordNet is applied to discovery fuzzy frequent itemsets as candidate cluster labels for grouping documents. We have conducted experiments to evaluate our approach on Reuters-21578 dataset. The experimental result shows that our proposed method outperforms the accuracy quality of FIHC, HFTC, and UPGMA.
An integration of fuzzy association rules and WordNet for document clustering
(2011-09-01)
Chen, Chun-Ling
;
Tseng, Frank S. C.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
With the rapid growth of text documents, document clustering technique is emerging for efficient document retrieval and better document browsing. Recently, some methods had been proposed to resolve the problems of high dimensionality, scalability, accuracy, and meaningful cluster labels by using frequent itemsets derived from association rule mining for clustering documents. In order to improve the quality of document clustering results, we propose an effective Fuzzy Frequent Itemset-based Document Clustering (F(2)IDC) approach that combines fuzzy association rule mining with the background knowledge embedded in WordNet. A term hierarchy generated from WordNet is applied to discover generalized frequent itemsets as candidate cluster labels for grouping documents. We have conducted experiments to evaluate our approach on Classic4, Re0, R8, and WebKB datasets. Our experimental results show that our proposed approach indeed provide more accurate clustering results than prior influential clustering methods presented in recent literature.
An integration of Word Net and fuzzy association rule mining for multi-label document clustering
(2010-11-01)
Chen, Chun-Ling
;
Tseng, Frank S. C.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
With the rapid growth of text documents, document clustering has become one of the main techniques for organizing large amount of documents into a small number of meaningful clusters. However, there still exist several challenges for document clustering, such as high dimensionality, scalability, accuracy, meaningful cluster labels, overlapping clusters, and extracting semantics from texts. In order to improve the quality of document clustering results, we propose an effective Fuzzy-based Multi-label Document Clustering (FMDC) approach that integrates fuzzy association rule mining with an existing ontology WordNet to alleviate these problems. In our approach, the key terms will be extracted from the document set, and the initial representation of all documents is further enriched by using hypernyms of WordNet in order to exploit the semantic relations between terms. Then, a fuzzy association rule mining algorithm for texts is employed to discover a set of highly-related fuzzy frequent itemsets, which contain key terms to be regarded as the labels of the candidate clusters. Finally, each document is dispatched into more than one target cluster by referring to these candidate clusters, and then the highly similar target clusters are merged. We conducted experiments to evaluate the performance based on Classic, Re0, R8, and WebKB datasets. The experimental results proved that our approach outperforms the influential document clustering methods with higher accuracy. Therefore, our approach not only provides more general and meaningful labels for documents, but also effectively generates overlapping clusters. (C) 2010 Elsevier B.V. All rights reserved.
An integration of Word Net and fuzzy association rule mining for multi-label document clustering
(2010-11-01)
Chen, Chun-Ling
;
Tseng, Frank S. C.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
With the rapid growth of text documents, document clustering has become one of the main techniques for organizing large amount of documents into a small number of meaningful clusters. However, there still exist several challenges for document clustering, such as high dimensionality, scalability, accuracy, meaningful cluster labels, overlapping clusters, and extracting semantics from texts. In order to improve the quality of document clustering results, we propose an effective Fuzzy-based Multi-label Document Clustering (FMDC) approach that integrates fuzzy association rule mining with an existing ontology WordNet to alleviate these problems. In our approach, the key terms will be extracted from the document set, and the initial representation of all documents is further enriched by using hypernyms of WordNet in order to exploit the semantic relations between terms. Then, a fuzzy association rule mining algorithm for texts is employed to discover a set of highly-related fuzzy frequent itemsets, which contain key terms to be regarded as the labels of the candidate clusters. Finally, each document is dispatched into more than one target cluster by referring to these candidate clusters, and then the highly similar target clusters are merged. We conducted experiments to evaluate the performance based on Classic, Re0, R8, and WebKB datasets. The experimental results proved that our approach outperforms the influential document clustering methods with higher accuracy. Therefore, our approach not only provides more general and meaningful labels for documents, but also effectively generates overlapping clusters. (C) 2010 Elsevier B.V. All rights reserved.
Byzantine Agreement & Fault Diagnosis Agreement in Dynamic Ad-Hoc Environment
(2008)
Cheng, Chien-Fu
;
Wang, Shu-Ching
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Since wireless communication and mobile computing are becoming more and more ubiquitous, the reliability and fault tolerance of the Mobile Ad-hoc Network (MANET) has become an important topic. In order to provide a reliable environment, a mechanism that allows a set of nodes to reach a common agreement, even in the presence of faulty nodes, is needed. Therefore, the Byzantine Agreement (BA) problem has drawn attention of more researchers. Traditionally, the BA problem was focused on wired networks. We know that the physical topology of a wired network is static, but the physical topology of an MANET is dynamic. Thus, previous BA protocols are not applicable in an MANET. In this paper, a new protocol is proposed to solve the BA problem with malicious faulty components in dynamic MANET. Furthermore, we also propose a new Fault Diagnosis Agreement (FDA) protocol to detect/locate faulty components to provide a highly reliable environment. From the performance perspective, the proposed protocols use the minimum number of message exchanges and can tolerate/detect/locate the maximum number of faulty nodes allowed in the dynamic network.
Chinese Pronominal Anaphora Resolution Using Lexical Knowledge and Entropy-Based Weight
(2008-11-01)
Wu, Dian-Song
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Pronominal anaphors are commonly observed in written texts. In this article, effective Chinese pronominal anaphora resolution is addressed by using lexical knowledge acquisition and salience measurement. The lexical knowledge acquisition is aimed to extract more semantic features, such as gender, number, and collocate compatibility by employing multiple resources. The presented salience measurement is based on entropy-based weighting on selecting antecedent candidates. The resolution is justified with a real corpus and compared with a rule-based model. Experimental results by five-fold cross-validation show that our approach yields 82.5% success rate on 1343 anaphoric instances. In comparison with a general rule-based approach, the performance is improved by 7%.
Efficient mining of temporal emerging itemsets from data streams
(2009-01-01)
Chu, Chun-Jung
;
Tseng, Vincent S.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a new method, namely EFI-Mine, for mining temporal emerging frequent itemsets from data streams efficiently and effectively. The temporal emerging frequent itemsets are those that are infrequent in the current time window of data stream but have high potential to become frequent in the subsequent time windows. Discovery of emerging frequent itemsets is an important process for mining interesting patterns like association rules from data streams. The novel contribution of EFI-Mine is that it can effectively identify the potential emerging itemsets such that the execution time can be reduced substantially in mining all frequent itemsets in data streams. This meets the critical requirements of time and space efficiency for mining data streams. The experimental results show that EFI-Mine can find the emerging frequent itemsets with high precision under different experimental conditions and it performs scalable in terms of execution time. (C) 2007 Elsevier Ltd. All rights reserved.
Embedding paths of variable lengths into hypercubes with conditional link-faults
(2009-08-01)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q(n), in which every node is still incident to at least two fault-free links. Then we show that Q(n) - F has a path of any odd (resp. even) length in the range from the distance to 2(n) - 1 (resp. 2(n) - 2) between two arbitrary nodes even if vertical bar F vertical bar = 2n - 5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults. (C) 2009 Elsevier B.V. All rights reserved.
Fault-free mutually independent Hamiltonian cycles of faulty star graphs
(2011)
Kung, Tzu-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG(n) denote an n-dimensional star network in which f <= n - 3 edges may fail accidentally. We show that there exist (n - 2 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SGn if n epsilon {3, 4}, and there exist (n - 1 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SG(n) if n >= 5.
Fault-tolerant hamiltonian connectedness of cycle composition networks
(2008-02-15)
Kueng, Tz-Liang
;
Lin, Cheng-Kuan
;
Liang, Tyne
;
Tan, Jimmy J. M.
;
Hsu, Lih-Hsing
It is important for a network to tolerate as many faults as possible. With the graph representation of an interconnection network, a k-regular hamiltonian and hamiltonian connected network is super fault-tolerant hamiltonian if it remains hamiltonian after removing up to k - 2 vertices and/or edges and remains hamiltonian connected after removing up to k - 3 vertices and/or edges. Super fault-tolerant hamiltonian networks have an optimal flavor with regard to the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. For this reason, a cycle composition framework was proposed to construct a (k + 2)-regular super fault-tolerant hamiltonian network based on a collection of n k-regular super fault-tolerant hamiltonian networks containing the same number of vertices for it n >= 3 and k >= 5. This paper is aimed to emphasize that the cycle composition framework can be still applied even when k = 4. (c) 2007 Elsevier Inc. All rights reserved.
FILE CONSISTENCY PROBLEM OF FILE-SHARING IN PEER-TO-PEER ENVIRONMENT
(2010-02-01)
Cheng, Chien-Fu
;
Wang, Shu-Ching
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
In this paper, file consistency problem of file-sharing with malicious processors in Peer-to-Peer (P2P) networks is investigated. We propose a novel hybrid approach integrating the clustering algorithm and consensus protocol to provide better Quality of Service (QoS) and solve the file consistency problem in the P2P file-sharing system. First, the clustering algorithm is introduced in our approach to provide better QoS. After clustering, we use consistent hash Junction to assign each processor and key to the corresponding processor in the de-Bruijn network. The de-Bruijn graph is nearly optimal and feature very short average routing distances. Finally, We use the consensus protocol to reach the consistent file information.
Friendship Prediction on Social Network Users
(2013)
Chen, Kuan-Hsi
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Undoubtedly friendship is one of key factors which keep social networking service users active and the whole community expanding. Hence, predicting friendships becomes an indispensable service provided by the platforms like Plurk, Twitter and Facebook. In this study, an empirical prediction resolution is presented by taking into account the interactions among Plurk users in Taiwan. Both response links and content information extracted from the interaction corpus are used as features in the implementation of the vector space machine based prediction. Experimental results show that the presented approach outperforms those bag-of-word based methods presented in previous studies.