Efficient mining and prediction of user behavior patterns in mobile web systems

The development of wireless and web technologies has allowed the mobile users to request various kinds of services by mobile devices at anytime and anywhere. Helping the users obtain needed information effectively is an important issue in the mobile web systems. Discovery of user behavior can highly benefit the enhancements on system performance and quality of services. Obviously, the mobile user's behavior patterns, in which the location and the service are inherently coexistent, become more complex than those of the traditional web systems. In this paper, we propose a novel data mining method, namely SMAP-Mine that can efficiently discover mobile users' sequential movement patterns associated with requested services. Moreover, the corresponding prediction strategies are also proposed. Through empirical evaluation under various simulation conditions, SMAP-Mine is shown to deliver excellent performance in terms of accuracy, execution efficiency and scalability. Meanwhile, the proposed prediction strategies are also verified to be effective in measurements of precision, hit ratio and applicability.     

An adaptive key selection method for the multilevel index model for effective service management in the cloud

The growing number of services processed and stored in the cloud has led to difficulties in managing and discovering the required services efficiently. Multilevel index model is an efficient method to manage and retrieve services in service repositories. When adding a new service to a multilevel index model, a key needs to be selected for the service, but existing key selection methods cannot adapt to the situation that hot services change over time. To address this problem, this article proposes an adaptive key selection method to improve the efficiency of service retrieval. However, the service addition operation of the adaptive key selection method is inefficient in the multilevel index model. For this reason, this article improves the multilevel index model by introducing local equivalence partition. This indexing model improves the service addition efficiency of the adaptive key selection method without affecting the service retrieval efficiency. It is experimentally demonstrated that the retrieval and addition efficiencies of the adaptive key selection method are close to the ideal state optimum under the multilevel index model with local equivalence partitioning.     

An approach of support approximation to discover frequent patterns from concept-drifting data streams based on concept learning

In an online data stream, the composition and distribution of the data may change over time, which is a phenomenon known as concept drift. The occurrence of concept drift can affect considerably the performance of a data stream mining method, especially in relation to mining accuracy. In this paper, we study the problem of mining frequent patterns from transactional data streams in the presence of concept drift, considering the important issue of mining accuracy preservation. In terms of frequent-pattern mining, we give the definitions of concept and concept drift with respect to streaming data; moreover, we present a categorization for concept drift. The concept of streaming data is considered the relationships of frequency between different patterns. Accordingly, we devise approaches to describe the concept concretely and to learn the concept through frequency relationship modeling. Based on concept learning, we propose a method of support approximation for discovering data stream frequent patterns. Our analyses and experimental results have shown that in several studied cases of concept drift, the proposed method not only performs efficiently in terms of time and memory but also preserves mining accuracy well on concept-drifting data streams.     

Online role mining for context-aware mobile service recommendation

Finding and recommending suitable services for mobile devices are increasingly important due to the popularity of mobile Internet. While recent research has attempted to use role-based approaches to recommend services, role discovery is still an ongoing research topic. Using role-based approaches, popular mobile services can be recommended to other members in the same role group in a context- dependent manner. This paper proposes several role mining algorithms, to suit different application requirements, that automatically group users according to their interests and habits dynamically. Most importantly, we propose an online role mining algorithm that can discover role patterns efficiently and incrementally. Finally, we present a complete, question-based framework that can efficiently perform role mining for context-aware service recommendation in a mobile environment—where a device may not be always connected to the server and/or scalability of the role mining algorithm running on the server is critical.     

A data mining proxy approach for efficient frequent itemset mining

Data mining has attracted a lot of research efforts during the past decade. However, little work has been reported on the efficiency of supporting a large number of users who issue different data mining queries periodically when there are new needs and when data is updated. Our work is motivated by the fact that the pattern-growth method is one of the most efficient methods for frequent pattern mining which constructs an initial tree and mines frequent patterns on top of the tree. In this paper, we present a data mining proxy approach that can reduce the I/O costs to construct an initial tree by utilizing the trees that have already been resident in memory. The tree we construct is the smallest for a given data mining query. In addition, our proxy approach can also reduce CPU cost in mining patterns, because the cost of mining relies on the sizes of trees. The focus of the work is to construct an initial tree efficiently. We propose three tree operations to construct a tree. With a unique coding scheme, we can efficiently project subtrees from on-disk trees or in-memory trees. Our performance study indicated that the data mining proxy significantly reduces the I/O cost to construct trees and CPU cost to mine patterns over the trees constructed.     

Efficient mining of multilevel gene association rules from microarray and gene ontology

Some recent studies have shown that association rules can reveal the interactions between genes that might not have been revealed using traditional analysis methods like clustering. However, the existing studies consider only the association rules among individual genes. In this paper, we propose a new data mining method named MAGO for discovering the multilevel gene association rules from the gene microarray data and the concept hierarchy of Gene Ontology (GO). The proposed method can efficiently find out the relations between GO terms by analyzing the gene expressions with the hierarchy of GO. For example, with the biological process in GO, some rules like Process A (up) → Process B (up) cab be discovered, which indicates that the genes involved in Process B of GO are likely to be up-regulated whenever those involved in Process A are up-regulated. Moreover, we also propose a constrained mining method named CMAGO for discovering the multilevel gene expression rules with user-specified constraints. Through empirical evaluation, the proposed methods are shown to have excellent performance in discovering the hidden multilevel gene association rules.     

A service composition approach based on sequence mining for migrating e-learning legacy system to SOA

With the fast development of business logic and information technology, today's best solutions are tomorrow's legacy systems. In China, the situation in the education domain follows the same path. Currently, there exists a number of e-learning legacy assets with accumulated practical business experience, such as program resource, usage behaviour data resource, and so on. In order to use these legacy assets adequately and efficiently, we should not only utilize the explicit assets but also discover the hidden assets. The usage behaviour data resource is the set of practical operation sequences requested by all users. The hidden patterns in this data resource will provide users' practical experiences, which can benefit the service composition in service-oriented architecture (SOA) migration. Namely, these discovered patterns will be the candidate composite services (coarse-grained) in SOA systems. Although data mining techniques have been used for software engineering tasks, little is known about how they can be used for service composition of migrating an e-learning legacy system (MELS) to SOA. In this paper, we propose a service composition approach based on sequence mining techniques for MELS. Composite services found by this approach will be the complementation of business logic analysis results of MELS. The core of this approach is to develop an appropriate sequence mining algorithm for mining related data collected from an e-learning legacy system. According to the features of execution trace data on usage behaviour from this e-learning legacy system and needs of further pattern analysis, we propose a sequential mining algorithm to mine this kind of data of the legacy system. For validation, this approach has been applied to the corresponding real data, which was collected from the e-learning legacy system; meanwhile, some investigation questionnaires were set up to collect satisfaction data. The investigation result is 90% the same with the result obtained through our approach.     

Towards efficiency of QoS-driven semantic web service composition for large-scale service-oriented systems

Quality-of-Service (QoS) performance guarantee for service-oriented systems (SOS) has become a critical problem. With the increasing number of offered services comes the challenge of efficiently building large-scale SOS to meet the required QoS criteria. Optimization of QoS-driven semantic Web service composition is known to be NP-hard. We address the efficiency issue by developing a polynomial time algorithm (QDA) for shortest sequence composition. We use dynamic programming to find service candidates for each execution. When all the services are searched, we use a depth-first trace back to derive the execution plan. We have tested our approach under Web-scale demands 20,000 services and 150,000 semantic concepts. In comparison with existing approaches, our experimental results show that QDA can be used to solve large-scale service composition problem effectively and efficiently with QoS guarantee.     

基于用户与服务协同聚类的Web服务发现研究*

如何从大规模服务集合中快速而准确地发现目标服务是应用Web服务技术的关键。针对现有研究方法主要集中在基于语义的Web服务发现上,其实施难度大且适用性不强,提出一种基于服务日志挖掘的服务发现方法。该方法通过对用户与服务进行协同聚类,缩小查询空间,从而提高发现效率。仿真实验表明,其在召回率与准确率上比基于关键字的匹配算法都有不同程度的改善,且该方法能极大地满足服务执行时动态绑定的特性。     

一种基于综合不放回抽样的随机森林算法改进

数据挖掘是大数据服务计算的一个重要方法,对于优化服务计算有重要意义。作为一种典型的数据挖掘方法,随机森林有着较高的正确率,因而得到广泛的应用。为了更加准确高效地处理服务计算中的大数据问题,进一步提升随机森林的正确率和效率,成为一项极其重要的研究。通过改变训练集的样本量和样本抽样方法,对平衡样本集和不平衡样本集进行分析,发现通过上述两个改进后,在优化区间内,平衡样本集泛化误差会减小12%~20%;单项改变抽样方法,可以使算法时间缩短,提升效率达10%~40%;对不平衡数据,也能够明显提升效率。理论和实验均证明,基于综合不放回抽样的随机森林算法改进能够提升平衡样本的正确率,使得该数据挖掘方法更适用于服务计算中的大数据分析和处理。     

基于组合服务执行信息的服务选取方法研究

组合服务选取问题是服务计算领域的一个研究热点问题,已往的选取方法大多基于难以准确获取的服务QoS信息,且算法思路复杂.文中提出了一种基于组合服务执行信息的服务选取方法.该方法分为3个阶段:数据生成阶段、数据挖掘阶段和服务选取阶段,分别进行组合服务执行信息的记载和相关数据集的生成、路径分支关联规则和服务执行顺序序列模式的挖掘以及基于挖掘产生的知识模式进行服务选取.文中首先给出一种可以方便记载日志的服务组合系统架构;然后提出一种基于时间加权的算法模型,以有效地进行路径分支关联规则和顺序序列模式的挖掘;最后对文中的组合服务选取方法进行描述.实验结果表明:文中方法在选取出的组合服务健壮性方面要优于基于QoS的方法.     

Frequent itemset mining using cellular learning automata

A core issue of the association rule extracting process in the data mining field is to find the frequent patterns in the database of operational transactions. If these patterns discovered, the decision making process and determining strategies in organizations will be accomplished with greater precision. Frequent pattern is a pattern seen in a significant number of transactions. Due to the properties of these data models which are unlimited and high-speed production, these data could not be stored in memory and for this reason it is necessary to develop techniques that enable them to be processed online and find repetitive patterns. Several mining methods have been proposed in the literature which attempt to efficiently extract a complete or a closed set of different types of frequent patterns from a dataset. In this paper, a method underpinned upon Cellular Learning Automata (CLA) is presented for mining frequent itemsets. The proposed method is compared with Apriori, FP-Growth and BitTable methods and it is ultimately concluded that the frequent itemset mining could be achieved in less running time. The experiments are conducted on several experimental data sets with different amounts of minsup for all the algorithms as well as the presented method individually. Eventually the results prod to the effectiveness of the proposed method.     

Mining non-redundant diverse patterns: an information theoretic perspective

The discovery of diversity patterns from binary data is an important data mining task. In this paper, we propose the problem of mining highly diverse patterns called non-redundant diversity patterns (NDPs). In this framework, entropy is adopted to measure the diversity of itemsets. In addition, an algorithm called NDP miner is proposed to exploit both monotone properties of entropy diversity measure and pruning power for the efficient discovery of non-redundant diversity patterns. Finally, our experimental results are given to show that the NDP miner can efficiently identify non-redundant diversity patterns.     

Pattern discovery in data streams under the time warping distance

Subsequence matching is a basic problem in the field of data stream mining. In recent years, there has been significant research effort spent on efficiently finding subsequences similar to a query sequence. Another challenging issue in relation to subsequence matching is how we identify common local patterns when both sequences are evolving. This problem arises in trend detection, clustering, and outlier detection. Dynamic time warping (DTW) is often used for subsequence matching and is a powerful similarity measure. However, the straightforward method using DTW incurs a high computation cost for this problem. In this paper, we propose a one-pass algorithm, CrossMatch, that achieves the above goal. CrossMatch addresses two important challenges: (1) how can we identify common local patterns efficiently without any omission? (2) how can we find common local patterns in data stream processing? To tackle these challenges, CrossMatch incorporates three ideas: (1) a scoring function, which computes the DTW distance indirectly to reduce the computation cost, (2) a position matrix, which stores starting positions to keep track of common local patterns in a streaming fashion, and (3) a streaming algorithm, which identifies common local patterns efficiently and outputs them on the fly. We provide a theoretical analysis and prove that our algorithm does not sacrifice accuracy. Our experimental evaluation and case studies show that CrossMatch can incrementally discover common local patterns in data streams within constant time (per update) and space.     

Mining non-redundant diverse patterns: an information theoretic perspective

The discovery of diversity patterns from binary data is an important data mining task. In this paper, we propose the problem of mining highly diverse patterns called non-redundant diversity patterns (NDPs). In this framework, entropy is adopted to measure the diversity of itemsets. In addition, an algorithm called NDP miner is proposed to exploit both monotone properties of entropy diversity measure and pruning power for the efficient discovery of non-redundant diversity patterns. Finally, our experimental results are given to show that the NDP miner can efficiently identify non-redundant diversity patterns.     

传感器网络中频繁移动模式挖掘算法研究

针对传感器网络中包括目标位置和时间的二维属性频繁移动模式挖掘问题,建立一种新的树状结构OMP-tree(OMP: Object Moving Pattern),OMP-tree可以压缩存储大量的原始移动模式.提出一种条件搜索算法,使用该算法可以大大减少满足条件的前缀模式数量.基于OMP-tree和条件搜索算法,设计一种新的挖掘目标的频繁移动模式的算法OMP-mine,该算法基于模式增长思想,直接递归地从条件模式基中得到频繁的前缀模式,然后连接后缀,达到模式增长的目的.仿真结果表明所提出的OMP-mine算法可以有效挖掘出传感器网络中具有二维属性的频繁的移动模式,并较好地降低了算法的时间和空间复杂度.     

基于对等网的Web服务发布和发现机制研究

传统的Web服务发布和发现机制在效率、可靠性、安全等方面存在一定缺陷,提出了一种基于对等网技术的Web服务发布和发现新机制.该机制利用对等体服务发布技术实现了Web服务的快速和即时发布,利用对等网通告发现策略实现了Web服务的高效搜索和定位.同时给出了在JXTA对等网络中即时发布和异步发现Web服务的算法实现.研究表明,该机制有助于普及网络边缘服务,增强应用的服务能力,是一种效率更高的分布式动态发布和发现Web服务的新机制.     

网格环境下数据库对等发现服务模型的研究

发现服务是网格环境下的核心服务之一。本文针对网格中数据库的发现服务问题,提出了一种对等发现服务模型DPDS(Database Peer-to-peer Discovery Service)。该模型引入发现服务器日志,试探性的在对等网中搜索可用约数据库及服务,不仅使发现服务具有更好的可用性和可扩展性,同时可以缩短响应时间,提高服务效率。     

Grid Service Discovery with Rough Sets

The computational grid is rapidly evolving into a service-oriented computing infrastructure that facilitates resource sharing and large-scale problem solving over the Internet. Service discovery becomes an issue of vital importance in utilizing grid facilities. This paper presents ROSSE, a Rough sets-based search engine for grid service discovery. Building on the Rough sets theory, ROSSE is novel in its capability to deal with the uncertainty of properties when matching services. In this way, ROSSE can discover the services that are most relevant to a service query from a functional point of view. Since functionally matched services may have distinct nonfunctional properties related to the quality of service (QoS), ROSSE introduces a QoS model to further filter matched services with their QoS values to maximize user satisfaction in service discovery. ROSSE is evaluated from the aspects of accuracy and efficiency in discovery of computing services.