Prediction of user navigation patterns by mining the temporal web usage evolution

Advances in the data mining technologies have enabled the intelligent Web abilities in various applications by utilizing the hidden user behavior patterns discovered from the Web logs. Intelligent methods for discovering and predicting user’s patterns is important in supporting intelligent Web applications like personalized services. Although numerous studies have been done on Web usage mining, few of them consider the temporal evolution characteristic in discovering web user’s patterns. In this paper, we propose a novel data mining algorithm named Temporal N-Gram (TN-Gram) for constructing prediction models of Web user navigation by considering the temporality property in Web usage evolution. Moreover, three kinds of new measures are proposed for evaluating the temporal evolution of navigation patterns under different time periods. Through experimental evaluation on both of real-life and simulated datasets, the proposed TN-Gram model is shown to outperform other approaches like N-gram modeling in terms of prediction precision, in particular when the web user’s navigating behavior changes significantly with temporal evolution.     

Organizing photographs with geospatial and image semantics

The popularity of GPS-equipped gadgets and mapping mashup applications has motivated the growth of geotagged Web resources as well as georeferenced multimedia applications. More and more research attention have been put on mining collaborative knowledge from mass user-contributed geotagged contents. However, little attention has been paid to generating high-quality geographical clusters, which is an important preliminary data-cleaning process for most geographical mining works. Previous works mainly use geotags to derive geographical clusters. Simply using one channel information is not sufficient for generating distinguishable clusters, especially when the location ambiguity problem occurs. In this paper, we propose a two-level clustering framework to utilize both the spatial and the semantic features of photographs for clustering. For the first-level geoclustering phase, we cluster geotagged photographs according to their spatial ties to roughly partition the dataset in an efficient way. Then we leverage the textual semantics in photographs' annotation to further refine the grouping results in the second-level semantic clustering phase. To effectively measure the semantic correlation between photographs, a semantic enhancement method as well as a new term weighting function have been proposed. We also propose a method for automatic parameter determination for the second-level spectral clustering process. Evaluation of our implementation on real georeferenced photograph dataset shows that our algorithm performs well, producing distinguishable geographical cluster with high accuracy and mutual information.     

基于超链接信息的搜索引擎检索结果聚类方法研究

针对目前搜索引擎返回候选信息过多从而使用户不能准确查找与主题有关结果的问题,提出了基于超链接信息的搜索引擎检索结果聚类方法,通过对网页的超链接锚文档和网页文档内容挖掘,最终将网页聚成不同的子类别。这种方法在依据网页内容进行聚类的同时,充分利用了Web结构和超链接信息,比传统的结构挖掘方法更能体现网站文档的内容特点,从而提高了聚类的准确性。     

A weighted common structure based clustering technique for XML documents

XML has recently become very popular as a means of representing semistructured data and as a standard for data exchange over the Web, because of its varied applicability in numerous applications. Therefore, XML documents constitute an important data mining domain. In this paper, we propose a new method of XML document clustering by a global criterion function, considering the weight of common structures. Our approach initially extracts representative structures of frequent patterns from schemaless XML documents using a sequential pattern mining algorithm. Then, we perform clustering of an XML document by the weight of common structures, without a measure of pairwise similarity, assuming that an XML document is a transaction and frequent structures extracted from documents are items of the transaction. We conducted experiments to compare our method with previous methods. The experimental results show the effectiveness of our approach.     

Exploiting the Community Structure of Fraudulent Keywords for Fraud Detection in Web Search

Internet users heavily rely on web search engines for their intended information.The major revenue of search engines is advertisements (or ads).However,the search advertising suffers from fraud.Fraudsters generate fake traffic which does not reach the intended audience,and increases the cost of the advertisers.Therefore,it is critical to detect fraud in web search.Previous studies solve this problem through fraudster detection (especially bots) by leveraging fraudsters' unique behaviors.However,they may fail to detect new means of fraud,such as crowdsourcing fraud,since crowd workers behave in part like normal users.To this end,this paper proposes an approach to detecting fraud in web search from the perspective of fraudulent keywords.We begin by using a unique dataset of 150 million web search logs to examine the discriminating features of fraudulent keywords.Specifically,we model the temporal correlation of fraudulent keywords as a graph,which reveals a very well-connected community structure.Next,we design DFW (detection of fraudulent keywords) that mines the temporal correlations between candidate fraudulent keywords and a given list of seeds.In particular,DFW leverages several refinements to filter out non-fraudulent keywords that co-occur with seeds occasionally.The evaluation using the search logs shows that DFW achieves high fraud detection precision (99％) and accuracy (93％).A further analysis reveals several typical temporal evolution patterns of fraudulent keywords and the co-existence of both bots and crowd workers as frandsters for web search fraud.     

时态信息的语义抽取与排序方法研究及系统实现

针对通用搜索引擎缺乏对网页内容的时态表达式的准确抽取及语义查询支持,提出时态语义相关度算法（TSRR）。在通用搜索引擎基础上添加了时态信息抽取和时态信息排序功能,通过引入时态正则表达式规则,抽取查询关键词和网页文档中的时态点或时态区间等时态表达式,综合计算网页内容的文本相关度和时态语义相关度,从而得到网页的最终排序评分。实验表明,应用TSRR算法可以准确而有效地匹配与时态表达式相关的关键词查询。     

应用链接分析的web搜索结果聚类

随着web上信息的急剧增长,如何有效地从web上获得高质量的web信息已经成为很多研究领域里的热门研究主题之一,比如在数据库,信息检索等领域。在信息检索里,web搜索引擎是最常用的工具,然而现今的搜索引擎还远不能达到满意的要求,使用链接分析,提出了一种新的方法用来聚类web搜索结果,不同于信息检索中基于文本之间共享关键字或词的聚类算法,该文的方法是应用文献引用和匹配分析的方法,基于两web页面所共享和匹配的公共链接,并且扩展了标准的K-means聚类算法,使它更适合于处理噪音页面,并把它应用于web结果页面的聚类,为验证它的有效性,进行了初步实验,实验结果显示通过链接分析对web搜索结果聚类取得了预期效果     

Retrieving keyworded subgraphs with graph ranking score

Keyword queries have long been popular to search engines and to the information retrieval community and have recently gained momentum for its usage in the expert systems community. The conventional semantics for processing a user query is to find a set of top-k web pages such that each page contains all user keywords. Recently, this semantics has been extended to find a set of cohesively interconnected pages, each of which contains one of the query keywords scattered across these pages. The keyword query having the extended semantics (i.e., more than a list of keywords hyperlinked with each other) is referred to the graph query. In case of the graph query, all the query keywords may not be present on a single Web page. Thus, a set of Web pages with the corresponding hyperlinks need to be presented as the search result. The existing search systems reveal serious performance problem due to their failure to integrate information from multiple connected resources so that an efficient algorithm for keyword query over graph-structured data is proposed. It integrates information from multiple connected nodes of the graph and generates result trees with the occurrence of all the query keywords. We also investigate a ranking measure called graph ranking score (GRS) to evaluate the relevant graph results so that the score can generate a scalar value for keywords as well as for the topology.     

Incremental and interactive mining of web traversal patterns

Web mining involves the application of data mining techniques to large amounts of web-related data in order to improve web services. Web traversal pattern mining involves discovering users’ access patterns from web server access logs. This information can provide navigation suggestions for web users indicating appropriate actions that can be taken. However, web logs keep growing continuously, and some web logs may become out of date over time. The users’ behaviors may change as web logs are updated, or when the web site structure is changed. Additionally, it can be difficult to determine a perfect minimum support threshold during the data mining process to find interesting rules. Accordingly, we must constantly adjust the minimum support threshold until satisfactory data mining results can be found.The essence of incremental data mining and interactive data mining is the ability to use previous mining results in order to reduce unnecessary processes when web logs or web site structures are updated, or when the minimum support is changed. In this paper, we propose efficient incremental and interactive data mining algorithms to discover web traversal patterns that match users’ requirements. The experimental results show that our algorithms are more efficient than other comparable approaches.     

KPS: a Web information mining algorithm

The Web mostly contains semi-structured information. It is, however, not easy to search and extract structural data hidden in a Web page. Current practices address this problem by (1) syntax analysis (i.e. HTML tags); or (2) wrappers or user-defined declarative languages. The former is only suitable for highly structured Web sites and the latter is time-consuming and offers low scalability. Wrappers could handle tens, but certainly not thousands, of information sources. In this paper, we present a novel information mining algorithm, namely KPS, over semi-structured information on the Web. KPS employs keywords, patterns and/or samples to mine the desired information. Experimental results show that KPS is more efficient than existing Web extracting methods.     

基于Web日志的用户访问模式挖掘

Web日志挖掘是数据挖掘技术在Web日志数据存储中的应用。论文介绍了Web日志挖掘,在分析发现用户访问模式方法——类Apriori算法的基础上,给出一种基于粗糙集的用户访问模式聚类方法。     

Web page recommendation via twofold clustering: considering user behavior and topic relation

Web page recommendations have attracted increasing attention in recent years. Web page recommendation has different characteristics compared to the classical recommenders. For example, the recommender cannot simply use the user-item utility prediction method as e-commerce recommendation, which would face the repeated item cold-start problem. Recent researches generally classify the web page articles before recommending. But classification often requires manual labors, and the size of each category may be too large. Some studies propose to utilize clustering method to preprocess the web page corpus and achieve good results. But there are many differences between different clustering methods. For instance, some clustering methods are of high time complexity; in addition, some clustering methods rely on initial parameters by iterative computing whose results probably aren’t stable. In order to solve the above issues, we propose a web page recommendation based on twofold clustering by considering both effectiveness and efficiency, and take the popularity and freshness factors into account. In our proposed clustering, we combined the strong points of density-based clustering and the k-means clustering. The core idea is that we used the density-based clustering in sample data to get the number of clusters and the initial center of each cluster. The experimental results show that our method performs better diversity and accuracy compared to the state-of-the-art approaches.

     

An efficient algorithm for mining top-<Emphasis Type="Italic">k</Emphasis> on-shelf high utility itemsets

High on-shelf utility itemset (HOU) mining is an emerging data mining task which consists of discovering sets of items generating a high profit in transaction databases. The task of HOU mining is more difficult than traditional high utility itemset (HUI) mining, because it also considers the shelf time of items, and items having negative unit profits. HOU mining can be used to discover more useful and interesting patterns in real-life applications than traditional HUI mining. Several algorithms have been proposed for this task. However, a major drawback of these algorithms is that it is difficult for users to find a suitable value for the minimum utility threshold parameter. If the threshold is set too high, not enough patterns are found. And if the threshold is set too low, too many patterns will be found and the algorithm may use an excessive amount of time and memory. To address this issue, we propose to address the problem of top-k on-shelf high utility itemset mining, where the user directly specifies k, the desired number of patterns to be output instead of specifying a minimum utility threshold value. An efficient algorithm named KOSHU (fast top-K on-shelf high utility itemset miner) is proposed to mine the top-k HOUs efficiently, while considering on-shelf time periods of items, and items having positive and/or negative unit profits. KOSHU introduces three novel strategies, named efficient estimated co-occurrence maximum period rate pruning, period utility pruning and concurrence existing of a pair 2-itemset pruning to reduce the search space. KOSHU also incorporates several novel optimizations and a faster method for constructing utility-lists. An extensive performance study on real-life and synthetic datasets shows that the proposed algorithm is efficient both in terms of runtime and memory consumption and has excellent scalability.     

Mining Navigation Patterns Using a Sequence Alignment Method

In this article, a new method is illustrated for mining navigation patterns on a web site. Instead of clustering patterns by means of a Euclidean distance measure, in this approach users are partitioned into clusters using a non-Euclidean distance measure called the Sequence Alignment Method (SAM). This method partitions navigation patterns according to the order in which web pages are requested and handles the problem of clustering sequences of different lengths. The performance of the algorithm is compared with the results of a method based on Euclidean distance measures. SAM is validated by means of user-traffic data of two different web sites. Empirical results show that SAM identifies sequences with similar behavioral patterns not only with regard to content, but also considering the order of pages visited in a sequence.     

Complete Mining of Frequent Patterns from Graphs: Mining Graph Data

Basket Analysis, which is a standard method for data mining, derives frequent itemsets from database. However, its mining ability is limited to transaction data consisting of items. In reality, there are many applications where data are described in a more structural way, e.g. chemical compounds and Web browsing history. There are a few approaches that can discover characteristic patterns from graph-structured data in the field of machine learning. However, almost all of them are not suitable for such applications that require a complete search for all frequent subgraph patterns in the data. In this paper, we propose a novel principle and its algorithm that derive the characteristic patterns which frequently appear in graph-structured data. Our algorithm can derive all frequent induced subgraphs from both directed and undirected graph structured data having loops (including self-loops) with labeled or unlabeled nodes and links. Its performance is evaluated through the applications to Web browsing pattern analysis and chemical carcinogenesis analysis.     

基于Web企业竞争对手情报自动搜集平台

从互联网中准确有效及时地自动搜索出需要的信息,是Web信息处理中的一个重要研究课题。本文在所提出的基于搜索路径Web网页搜索和基于多知识网页信息抽取方法基础上,给出基于Web企业竞争对手情报自动收集平台的实现方法,该平台可以有效地从多个企业门户网站中,自动搜索出所需要的目标网页,并能够从目标网页中自动抽取其中多记录信息。本文利用该平台进行了企业人才招聘信息的自动搜索实验。实验结果证实了该平台在信息自动搜集方面的有效性和准确性。     

一种中文微博新闻话题检测的方法

微博的迅猛发展带来了另一种社会化的新闻媒体形式。提出一种从微博中挖掘新闻话题的方法,即在线检测微博消息中大量突现的关键字,并将它们进行聚类,从而找到新闻话题。为了提取出新闻主题词,综合考虑短文本中的词频和增长速度而构造复合权值,用以量化词语是新闻词汇的程度;在话题构造中使用了上下文的相关度模型来支撑增量式聚类算法,相比于语义相似度模型,其更能适应该问题的特点。在真实的微博数据上运行的实验表明,本方法可以有效地从大量消息中检测出新闻话题。     

Iterative Visual Clustering for Learning Concepts from Unstructured Text

Discovering concepts from vast amount of text is is an important but hard explorative task. A common approach is to identify meaningful keyword clusters with interesting temporal distributive trends from unstructured text. However, usually lacking clearly de ned objective functions, users'' domain knowledge and interactions need to be feed back and to drive the clustering process. Therefore we propose the iterative visual clustering (IVC), a noval visual text analytical model. It uses di erent types of visualizations to help users cluster keywords interactively, as well as uses graphics to suggest good clustering options. The most distinctive di erence between IVC and traditional text analytical tools is, IVC has a formal on-line learning model which learns users'' preference iteratively: during iterations, IVC transforms users'' interactions into model training input, and then visualizes the output for more users interactions. We apply IVC as a visual text mining framework to extract concepts from nursing narratives. With the engagement of domain knowledge, IVC has achieved insightful concepts with interesting patterns.     

Data model for warehousing historical Web information

In this paper, we present a temporal web data model designed for warehousing historical data from World Wide Web (WWW). As the Web is now populated with large volume of information, it has become necessary to capture selected portions of web information in a data warehouse that supports further information processing such as data extraction, data classification, and data mining. Nevertheless, due to the unstructured and dynamic nature of Web, the traditional relational model and its temporal variants could not be used to build such a data warehouse. In this paper, we therefore propose a temporal web data model that represents web documents and their connectivities in the form of temporal web tables. To represent web data that evolve with time, a visible time interval is associated with each web document. To manipulate temporal web tables, we have defined a set of web operators with capabilities ranging from extracting WWW information into web tables, to merging information from different web tables. We further illustrate the use of our temporal web data model using some realistic motivating examples.