Dissertations / Theses on the topic 'Spatial association mining'

A técnica de mineração de regras de associação surgiu com o objetivo de encontrar conhecimento novo, útil e previamente desconhecido em bancos de dados transacionais, e uma grande quantidade de algoritmos de mineração de regras de associação tem sido proposta na última década. O maior e mais bem conhecido problema destes algoritmos é a geração de grandes quantidades de conjuntos freqüentes e regras de associação. Em bancos de dados geográficos o problema de mineração de regras de associação espacial aumenta significativamente. Além da grande quantidade de regras e padrões gerados a maioria são associações do domínio geográfico, e são bem conhecidas, normalmente explicitamente representadas no esquema do banco de dados. A maioria dos algoritmos de mineração de regras de associação não garantem a eliminação de dependências geográficas conhecidas a priori. O resultado é que as mesmas associações representadas nos esquemas do banco de dados são extraídas pelos algoritmos de mineração de regras de associação e apresentadas ao usuário. O problema de mineração de regras de associação espacial pode ser dividido em três etapas principais: extração dos relacionamentos espaciais, geração dos conjuntos freqüentes e geração das regras de associação. A primeira etapa é a mais custosa tanto em tempo de processamento quanto pelo esforço requerido do usuário. A segunda e terceira etapas têm sido consideradas o maior problema na mineração de regras de associação em bancos de dados transacionais e tem sido abordadas como dois problemas diferentes: “frequent pattern mining” e “association rule mining”. Dependências geográficas bem conhecidas aparecem nas três etapas do processo. Tendo como objetivo a eliminação dessas dependências na mineração de regras de associação espacial essa tese apresenta um framework com três novos métodos para mineração de regras de associação utilizando restrições semânticas como conhecimento a priori. O primeiro método reduz os dados de entrada do algoritmo, e dependências geográficas são eliminadas parcialmente sem que haja perda de informação. O segundo método elimina combinações de pares de objetos geográficos com dependências durante a geração dos conjuntos freqüentes. O terceiro método é uma nova abordagem para gerar conjuntos freqüentes não redundantes e sem dependências, gerando conjuntos freqüentes máximos. Esse método reduz consideravelmente o número final de conjuntos freqüentes, e como conseqüência, reduz o número de regras de associação espacial.<br>The association rule mining technique emerged with the objective to find novel, useful, and previously unknown associations from transactional databases, and a large amount of association rule mining algorithms have been proposed in the last decade. Their main drawback, which is a well known problem, is the generation of large amounts of frequent patterns and association rules. In geographic databases the problem of mining spatial association rules increases significantly. Besides the large amount of generated patterns and rules, many patterns are well known geographic domain associations, normally explicitly represented in geographic database schemas. The majority of existing algorithms do not warrant the elimination of all well known geographic dependences. The result is that the same associations represented in geographic database schemas are extracted by spatial association rule mining algorithms and presented to the user. The problem of mining spatial association rules from geographic databases requires at least three main steps: compute spatial relationships, generate frequent patterns, and extract association rules. The first step is the most effort demanding and time consuming task in the rule mining process, but has received little attention in the literature. The second and third steps have been considered the main problem in transactional association rule mining and have been addressed as two different problems: frequent pattern mining and association rule mining. Well known geographic dependences which generate well known patterns may appear in the three main steps of the spatial association rule mining process. Aiming to eliminate well known dependences and generate more interesting patterns, this thesis presents a framework with three main methods for mining frequent geographic patterns using knowledge constraints. Semantic knowledge is used to avoid the generation of patterns that are previously known as non-interesting. The first method reduces the input problem, and all well known dependences that can be eliminated without loosing information are removed in data preprocessing. The second method eliminates combinations of pairs of geographic objects with dependences, during the frequent set generation. A third method presents a new approach to generate non-redundant frequent sets, the maximal generalized frequent sets without dependences. This method reduces the number of frequent patterns very significantly, and by consequence, the number of association rules.

The popularity of spatial databases increases since the amount of the spatial data that need to be handled has increased by the use of digital maps, images from satellites, video cameras, medical equipment, sensor networks, etc. Spatial data are difficult to examine and extract interesting knowledge<br>hence, applications that assist decision-making about spatial data like weather forecasting, traffic supervision, mobile communication, etc. have been introduced. In this thesis, more natural and precise knowledge from spatial data is generated by construction of fuzzy spatial data cube and extraction of fuzzy association rules from it in order to improve decision-making about spatial data. This involves an extensive research about spatial knowledge discovery and how fuzzy logic can be used to develop it. It is stated that incorporating fuzzy logic to spatial data cube construction necessitates a new method for aggregation of fuzzy spatial data. We illustrate how this method also enhances the meaning of fuzzy spatial generalization rules and fuzzy association rules with a case-study about weather pattern searching. This study contributes to spatial knowledge discovery by generating more understandable and interesting knowledge from spatial data by extending spatial generalization with fuzzy memberships, extending the spatial aggregation in spatial data cube construction by utilizing weighted measures, and generating fuzzy association rules from the constructed fuzzy spatial data cube.

In this thesis, we present an innovative and novel approach to personalise maps/geo-spatial services for mobile users. With the proposed map personalisation approach, only relevant data will be extracted from detailed maps/geo-spatial services on the fly, based on a user’s current location, preferences and requirements. This would result in dramatic improvements in the legibility of maps on mobile device screens, as well as significant reductions in the amount of data being transmitted; which, in turn, would reduce the download time and cost of transferring the required geo-spatial data across mobile networks. Furthermore, the proposed map personalisation approach has been implemented into a working system, based on a four-tier client server architecture, wherein fully detailed maps/services are stored on the server, and upon a user’s request personalised maps/services, extracted from the fully detailed maps/services based on the user’s current location, preferences, are sent to the user’s mobile device through mobile networks. By using open and standard system development tools, our system is open to everyday mobile devices rather than smart phones and Personal Digital Assistants (PDA) only, as is prevalent in most current map personalisation systems. The proposed map personalisation approach combines content-based information filtering and collaborative information filtering techniques into an algorithmic solution, wherein content-based information filtering is used for regular users having a user profile stored on the system, and collaborative information filtering is used for new/occasional users having no user profile stored on the system. Maps/geo-spatial services are personalised for regular users by analysing the user’s spatial feature preferences automatically collected and stored in their user profile from previous usages, whereas, map personalisation for new/occasional users is achieved through analysing the spatial feature preferences of like-minded users in the system in order to make an inference for the target user. Furthermore, with the use of association rule mining, an advanced inference technique, the spatial features retrieved for new/occasional users through collaborative filtering can be attained. The selection of spatial features through association rule mining is achieved by finding interesting and similar patterns in the spatial features most commonly retrieved by different user groups, based on their past transactions or usage sessions with the system.

Data mining is the extraction of interesting non-trivial, implicit, previously unknown and potentially useful information or patterns from data in large databases. Association rule mining is a data mining method that seeks to discover associations among transactions encoded within a database. Data mining on spatio-temporal data takes into consideration the dynamics of spatially extended systems for which large amounts of spatial data exist, given that all real world spatial data exists in some temporal context. We need fuzzy sets in mining association rules from spatio-temporal databases since fuzzy sets handle the numerical data better by softening the sharp boundaries of data which models the uncertainty embedded in the meaning of data. In this thesis, fuzzy association rule mining is performed on spatio-temporal data using data cubes and Apriori algorithm. A methodology is developed for fuzzy spatio-temporal data cube construction. Besides the performance criteria interpretability, precision, utility, novelty, direct-to-the-point and visualization are defined to be the metrics for the comparison of association rule mining techniques. Fuzzy association rule mining using spatio-temporal data cubes and Apriori algorithm performed within the scope of this thesis are compared using these metrics. Real meteorological data (precipitation and temperature) for Turkey recorded between 1970 and 2007 are analyzed using data cube and Apriori algorithm in order to generate the fuzzy association rules.

This thesis draws on David Harvey’s concept of “accumulation by dispossession” and an international political economy (IPE) approach centred on the institutional arrangements and power structures that privilege certain actors and values, in order to critique current capitalist practices of primitive accumulation by the global corporate extractive industry. The thesis examines how accumulation by dispossession by the global extractive industry is facilitated by the “free entry” or “free mining” principle. It does so by focusing on Canada as a leader in the global extractive industry and the spread of this country’s mining laws to other countries – in other words, the transnationalisation of norms in the global extractive industry – so as to maintain a consistent and familiar operating environment for Canadian extractive companies. The transnationalisation of norms is further promoted by key international institutions such as the World Bank, which is also the world’s largest development lender and also plays a key role in shaping the regulations that govern natural resource extraction. The thesis briefly investigates some Canadian examples of resource extraction projects, in order to demonstrate the weaknesses of Canadian mining laws, particularly the lack of protection of landowners’ rights under the free entry system and the subsequent need for “free, prior and informed consent” (FPIC). The thesis also considers some of the challenges to the adoption and implementation of the right to FPIC. These challenges include embedded institutional structures like the free entry mining system, international political economy (IPE) as shaped by international institutions and powerful corporations, as well as concerns regarding ‘local’ power structures or the legitimacy of representatives of communities affected by extractive projects. The thesis concludes that in order for Canada to be truly recognized as a leader in the global extractive industry, it must establish legal norms domestically to ensure that Canadian mining companies and residents can be held accountable when there is evidence of environmental and/or human rights violations associated with the activities of Canadian mining companies abroad. The thesis also concludes that Canada needs to address underlying structural issues such as the free entry mining system and implement FPIC, in order to curb “accumulation by dispossession” by the extractive industry, both domestically and abroad.

碩士<br>國立臺灣大學<br>電機工程學研究所<br>93<br>In this paper, we integrate data mining with image processing for discovering spatial relationships in images. We present an image mining framework, Spatial Association Rulemining (SAR), to mine spatial associations located in specific locations of images. A rule in the SAR refers to the occurrences of image content in a pair of spatial locations. The proposed approach is applied to mine color spatial association rules (color-SAR) in landscape scene images so as to demonstrate that the spatial association rules is able to the application of image classification. Our experimental results show that the classification accuracy of 86% can be achieved by the rule-based classifier.

碩士<br>國立臺灣大學<br>資訊管理學研究所<br>93<br>Nowadays, there are the increasing numbers of images accumulated on the Internet. Spatial data mining play an important role of extracting implicit knowledge, spatial relationships among objects and other interesting patterns stored in spatial databases. In this thesis, we focus on finding the association rules of spatial relations among objects in an image. Previously, some scholars have proposed viewpoint mining and co-relation mining method based on the 2D string representation. However, the mining results may be too detailed and the relations between the objects are vague. Therefore, we propose a novel algorithm, 9DLT-Miner, where every image is represented by the 9DLT representation. 9DLT-Miner adopts the concept of the Apriori algorithm as well as uses the anti-monotone and 9DLT pruning strategies. Our proposed method consists of two phase. In the first phase, we find all frequent patterns of length one. In the second phase, we use the frequent k-patterns (k>=1) to generate all candidate (k+1)-patterns and then scan the databases to count the support and check if a pattern is frequent. Repeat the steps in phase 2 until no more frequent patterns can be found. Experimental results show that 9DLT-Miner prunes a large number of impossible frequent candidates, and it’s more efficient and scalable.

碩士<br>國立臺灣大學<br>資訊管理學研究所<br>95<br>In this thesis, we propose a novel spatial data mining algorithm, called 9DSPA-Miner, to mine the spatial association rules from an image database, where every image is represented by the 9D-SPA representation. Our proposed method consists of three phases. In the first phase, we scan the database once and create an index structure. In the second phase, we scan the index structure to find all frequent patterns of length two. In the third phase, we use the frequent k-patterns (k≧2) to generate candidate (k+1)-patterns and check each generated candidate if its support is not less than the user-specified minimum support threshold by using the index structure. Then, the steps in phase 3 are repeated until no more frequent patterns can be found. Since 9DSPA-Miner uses the characteristics of the 9D-SPA representation to prune most of impossible candidates and the index structure to speed up the mining process, the experiment results demonstrate that it is more efficient and scalable than the modified Apriori method.

碩士<br>朝陽科技大學<br>資訊管理系碩士班<br>91<br>Since huge amounts of spatial data can be easily collected from various applications, ranging from remote sensing technology to geographical information system, the extraction and comprehension of spatial knowledge is a more and more important task. Spatial association rule mining is a kind of spatial data mining that is to discover interesting and implicit association knowledge from spatial databases. There have been some interesting studies related to the mining of spatial association rules. However, lack of studies on semantic spatial association rules which can reflect the way human think. Besides, designing efficient methods for mining spatial association rules also demand immediate our attentions from better performance. Therefore, in this thesis, an efficient method based on Class Inheritance Tree (CIT) is proposed for capturing intrinsic relationships between spatial and non-spatial data. This rules help to accommodate data semantics as well as to achieve better performance. Moreover, many excellent studies on Remote Sensed Image (RSI) have been conducted for potential relationships of crop yield. However, most of them suffer from the performance problem because their techniques for mining association rules are based on Apriori algorithm. In this thesis, two efficient algorithms, two-phase spatial association rules mining and adaptive two-phase spatial association rules mining, are proposed for addressing the above problem. Both methods primarily conduct two phase algorithms by creating Histogram Generators for fast generating coarse-grained spatial association rules, and further mining the fine-grained spatial association rules w.r.t the coarse-grained frequently patterns obtained in the first phase. Adaptive two-phase spatial association rules mining method conducts the idea of partition on an image for efficiently filtering out non-frequent patterns and thus facilitate the following two phase process. Such two-phase approaches save much computations and will be shown by lots of experimental results in the thesis.

碩士<br>亞洲大學<br>資訊工程學系碩士班<br>95<br>Scientists in many researches have been using computer technologies lately. GIS, GPS have been helping scientists in doing many kinds of researches. Geographical data as a result from GPS were available in electronic format. This type of data can be treated as a spatial data. And by using colocation pattern mining, we would discover associations between spatial features. The first thing we do was developed a data set generator. Data sets that are generated by data set generator then processed using the proposed approach. The system we proposed was a two steps system. The first step was doing a segmentation to produce the transaction from the data set. The segmentation was using a fix threshold segmentation and the threshold was 3*sigma. Sigma in this study is our way to measure closeness of a point to its neighbors. Sigma is a distance value that will bring the entropy of the whole data set into it minimum, sigma was calculated using data field model. And the second one was doing a fuzzy association rule mining where we introduce the transaction into a fuzzy membership function. After fuzzfied the data set then we counted the fuzzy support values and fuzzy confidence values. The infrequent rules then pruned using an apriori-like algorithm. The result of the approach then come as these manners, feature a will be whether near or close or far from feature b.

碩士<br>國立高雄海洋科技大學<br>海事資訊科技研究所<br>106<br>With the rapid expansion of the total amount of information in cyberspace and the timing and spatial information is ubiquitous. However, the data in such a large number of fast and complex background, how to further through the data structure to reorganize such a wide range of nonstructural data, and uses the system manages to extract the potential value derived from the data, so as to predict and provide decision-making information. Such issues have gradually crossed the statistics, information, and specific business areas. Among the many large databases in Taiwan, the National Health Insurance Database is the most complete, which includes time-based medical information and spatial distribution of diseases and other major fields. Therefore, this study will use the National Health Insurance Research Database as an example, through the Big Data analysis technology combined with the spatial geographic information system to explore the data relevant to establish the disease distribution map and the relationship between the disease networks. By the methods of Spatial Autocorrelation, Spatial Autoregressive Model and Association Rules to analyze the distribution of heavy metals in Taiwan farmland. To explore on heavy metal environmental pollution factors with spatial dependence of the prevalence of Parkinson's disease, and mining a common association rules with comorbidities of Parkinson's disease.

With the growth of geo-referenced data and the sophistication and complexity of spatial databases, data mining and knowledge discovery techniques become essential tools for successful analysis of large spatial datasets. Spatial clustering is fundamental and central to geographical data mining. It partitions a dataset into smaller homogeneous groups due to spatial proximity. Resulting groups represent geographically interesting patterns of concentrations for which further investigations should be undertaken to find possible causal factors. In this thesis, we propose a spatial-dominant generalization approach that mines multivariate causal associations among geographical data layers using clustering analysis. First, we propose a generic framework of multi-purpose exploratory spatial clustering in the form of the Template-Method Pattern. Based on an object-oriented framework, we design and implement an automatic multi-purpose exploratory spatial clustering tool. The first instance of this framework uses the Delaunay diagram as an underlying proximity graph. Our spatial clustering incorporates the peculiar characteristics of spatial data that make space special. Thus, our method is able to identify high-quality spatial clusters including clusters of arbitrary shapes, clusters of heterogeneous densities, clusters of different sizes, closely located high-density clusters, clusters connected by multiple chains, sparse clusters near to high-density clusters and clusters containing clusters within O(n log n) time. It derives values for parameters from data and thus maximizes user-friendliness. Therefore, our approach minimizes user-oriented bias and constraints that hinder exploratory data analysis and geographical data mining. Sheer volume of spatial data stored in spatial databases is not the only concern. The heterogeneity of datasets is a common issue in data-rich environments, but left open by exploratory tools. Our spatial clustering extends to the Minkowski metric in the absence or presence of obstacles to deal with situations where interactions between spatial objects are not adequately modeled by the Euclidean distance. The genericity is such that our clustering methodology extends to various spatial proximity graphs beyond the default Delaunay diagram. We also investigate an extension of our clustering to higher-dimensional datasets that robustly identify higher-dimensional clusters within O(n log n) time. The versatility of our clustering is further illustrated with its deployment to multi-level clustering. We develop a multi-level clustering method that reveals hierarchical structures hidden in complex datasets within O(n log n) time. We also introduce weighted dendrograms to effectively visualize the cluster hierarchies. Interpretability and usability of clustering results are of great importance. We propose an automatic pattern spotter that reveals high level description of clusters. We develop an effective and efficient cluster polygonization process towards mining causal associations. It automatically approximates shapes of clusters and robustly reveals asymmetric causal associations among data layers. Since it does not require domain-specific concept hierarchies, its applicability is enhanced.<br>PhD Doctorate

With the growth of geo-referenced data and the sophistication and complexity of spatial databases, data mining and knowledge discovery techniques become essential tools for successful analysis of large spatial datasets. Spatial clustering is fundamental and central to geographical data mining. It partitions a dataset into smaller homogeneous groups due to spatial proximity. Resulting groups represent geographically interesting patterns of concentrations for which further investigations should be undertaken to find possible causal factors. In this thesis, we propose a spatial-dominant generalization approach that mines multivariate causal associations among geographical data layers using clustering analysis. First, we propose a generic framework of multi-purpose exploratory spatial clustering in the form of the Template-Method Pattern. Based on an object-oriented framework, we design and implement an automatic multi-purpose exploratory spatial clustering tool. The first instance of this framework uses the Delaunay diagram as an underlying proximity graph. Our spatial clustering incorporates the peculiar characteristics of spatial data that make space special. Thus, our method is able to identify high-quality spatial clusters including clusters of arbitrary shapes, clusters of heterogeneous densities, clusters of different sizes, closely located high-density clusters, clusters connected by multiple chains, sparse clusters near to high-density clusters and clusters containing clusters within O(n log n) time. It derives values for parameters from data and thus maximizes user-friendliness. Therefore, our approach minimizes user-oriented bias and constraints that hinder exploratory data analysis and geographical data mining. Sheer volume of spatial data stored in spatial databases is not the only concern. The heterogeneity of datasets is a common issue in data-rich environments, but left open by exploratory tools. Our spatial clustering extends to the Minkowski metric in the absence or presence of obstacles to deal with situations where interactions between spatial objects are not adequately modeled by the Euclidean distance. The genericity is such that our clustering methodology extends to various spatial proximity graphs beyond the default Delaunay diagram. We also investigate an extension of our clustering to higher-dimensional datasets that robustly identify higher-dimensional clusters within O(n log n) time. The versatility of our clustering is further illustrated with its deployment to multi-level clustering. We develop a multi-level clustering method that reveals hierarchical structures hidden in complex datasets within O(n log n) time. We also introduce weighted dendrograms to effectively visualize the cluster hierarchies. Interpretability and usability of clustering results are of great importance. We propose an automatic pattern spotter that reveals high level description of clusters. We develop an effective and efficient cluster polygonization process towards mining causal associations. It automatically approximates shapes of clusters and robustly reveals asymmetric causal associations among data layers. Since it does not require domain-specific concept hierarchies, its applicability is enhanced.<br>PhD Doctorate

碩士<br>國立政治大學<br>資訊管理學系<br>87<br>There have been a lot of research about data mining in relational database. We can mine more specific and concrete knowledge in transaction databases by further considering spatial and temporal dimension. Until now the statistical spatial analysis has been one common technique for analyzing spatial data. However , there are still many remaining problems. Han et al. used concept hierarchies to mine multiple-level association rules. Their ideas are great and worth our learning. On the other hand , some scholars proposed the notion of cyclic association rules. Therefore , we combine the merits of these researches to discover more meaningful knowledge. In this research , we try to integrate the ideas of spatial associations with cyclic association and propose the idea of spatial cyclic association rules. First , we survey these researches in the fields of spatial and temporal data mining. A framework is then proposed. Finally , we implement a prototype system in WWW ( 1-itemset and 2-itemset only now).

碩士<br>國立臺南大學<br>數位學習科技學系<br>95<br>Over the past few years, a considerable number of studies have made on Market Basket analysis. Market Basket analysis is an efficient method to mining customers’ purchasing behavior from markets’ transaction databases. Therefore, nowadays customer’s transaction do not only made in a single location, but also it could be made in many different geography locations over time, especially after the E-Business, wireless network, and RFID techniques Over the past few years, a considerable number of studies have made on Market Basket analysis. Market Basket analysis is an efficient method to mining customers’ purchasing behavior from markets’ transaction databases. Therefore, nowadays customer’s transaction do not only made in a single location, but also it could be made in many different geography locations over time, especially after the E-Business, wireless network, and RFID techniques have become more available. Traditional Association rule only gather single location’s information, and it can’t be suitable for such a multi-time and multi-location environment. We design a novel and efficient algorithm named Mining Association Rules Considering Connected Patterns in Spatio-Temporal Transactions(STTACP for short) for mining spatio-temporal association rules with multi-time and multi-location granularities efficiently. Experimental results have shown that the STTACP algorithm can discovery spatio-temporal association rules efficiently from different spatio-temporal transaction databases. Simultaneously, the method we proposed is more faster then traditional Apriori algorithm.

碩士<br>國立臺南大學<br>數位學習科技學系<br>95<br>We can only check what the customers buy on the traditional data mining for shopping, but we can not understand the shopping flow when the customers shop. Association Rules know the shopping behavior of customers from transactions database in the market, search for frequent item ets, but only pay attention to the relationship between the items. Nowadays along with technical progress, we can not only obtain the transaction information of the customers’ purchasing items when paying up by cash register, but also extra obtain when and where items put in the shopping vehicle along with the shopping flow by establishing RFID or other sensor devices in the shopping vehicle. The shopping flow contains the time and location information, but the traditional transaction does not. With the extra information, we are possibly interested in the follows: Customers’ shopping flow, which items together can the customer purchase in the certain scope, and which items together can the customer purchase in the certain time. Therefore, in order to solve the traditional association rules which has not support the analysis of the time and spatial multiple dimensions, this research proposes Spatio-Temporal Transaction Association rules with the Dynamic Window (STTA/DW). Based on the Apriori algorithm, it supports analysis of the time and spatial multiple factor, and also provides the Dynamic Windows for modification of parameters of mining. When parameters are modified, it refers to other sub-transactions which have the same parent, instead of re-scanning the whole database. The experimental result showed that this research under the different conditions not only can mining out spatio-temporal rules effectively and correctly, and is more quick and exact than traditional Apriori.