Graph-based Data Mining for Transactional,Spatial and Social-networking Data
Date Issued
2011
Date
2011
Author(s)
Tai, Chih-Hua
Abstract
Data Mining is a data-and-application dependant technique, and has received significant attentions in the last decade. In the past years, various techniques have been developed to deal with set or sequence data in business marketing, computer networks, bioinformatics, to name a few. Many real applications, however, have called for the need of new techniques to tackle data with structural information, i.e., graphs. Graph-based data mining, which discovers novel knowledge in graph-represented data, is thus becoming more and more important. In this dissertation, motivated by the fact that graph-based data mining is still in its fancy compared to the wide applications, we attempt to address the use of graph-based data mining in realistic problems with three kinds of data complexity, respectively.
First, due to the rise of cloud computing, people who lack of expertise in data mining and/or computational resources now can also take advantages from data mining by outsourcing their mining tasks. However, for any outsourcing service, privacy is a major concern. In Chapter 2, we study the problem of privacy protection in outsourcing frequent itemset mining. This problem has two challenges. One is on how to protect sensitive information, including the raw data and the frequent itemsets, with reasonable overhead and preserve the precise mining results. The other is how to protect against an attacker with related background knowledge such as item support information. To overcome these challenges, we propose k-support anonymity and develop a novel encryption approach that constructs a pseudo taxonomy tree to hide sensitive items. By leveraging the property that only the items at the leaf level of the taxonomy need to be appear at the transactions, the storage overhead is limited while the privacy protection is conformed.
Second, note that data collected by sensors can consist of not only geographic attributes but also informative attributes. Since the spatial-alone clustering approaches consider only the geographic attributes to identify spatial clusters at data-dense regions, it is infeasible to obtain spatial clusters with informatively similar data points from such data by the spatial-alone clustering approaches. Therefore, we address the informative spatial data clustering (ISDC) problem in Chapter 3. One of the main challenges in this problem is that geographic and informative attributes represent different concepts and should not be tackled in the same way in clustering. To overcome this challenge, we proposed Algorithm BiAgree that introduces a graph structure, named NeiGraph, to integrate informative attributes and geographic attributes in vertices and edges, respectively. Afterward, Algorithm BiAgree is able to identify informatively similar regions regardless of the data density by partitioning NeiGraph into informative-consistent connected components. In addition, by maintaining NeiGraph, Algorithm BiAgree also provides the online computing capability to acquire the solutions with high quality and smaller computation time respectively.
Finally, as the rapid growth in the number of services and applications leverage social network data, there is increasing concern about privacy issues in published social networks. Recently several studies have addressed the privacy issues on vertex/edge attributes, vertex identity, link disclosure, and so on. However, compared to the rich information inherent in graph data, the privacy issues in publications of social networks have not been fully solved. In Chapter 4, we address a new privacy issue, referred to as the community identification. The community identity of an individual is a kind of structural information that indicates the neighborhood or connections of the individual. The community identity could also represent the personal privacy information sensitive to the public, such as on-line political activity group, on-line disease support group information, or friend group in a social network. To protect such information, therefore, we propose a new privacy model, named k-structural diversity, and develop an Integer Programming formulation to find the optimal solutions to k-SDA. Moreover, we devise three scalable heuristics to solve the large instances of k-SDA with different perspectives.
Subjects
Graph-based Data Mining
Privacy-preserving
Anonymity
Grouping
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-100-F92921029-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):3e06e55cca76df136ccc149b7548101e