Mining frequent patterns in image databases with 9D-SPA representation

In this paper, we propose a novel algorithm, called 9DSPA-Miner, to mine frequent patterns from an image database, where every image is represented by the 9D-SPA representation. Our proposed method consists of three phases. First, we scan the database once and create an index structure. Next, the index structure is scanned to find all frequent patterns of length two. Finally, we use the frequent k-patterns (k ? 2) to generate candidate (k + 1)-patterns and check if the support of each candidate generated is not less than the user-specified minimum support threshold by using the index structure. Then, the steps in the third phase are repeated until no more frequent patterns can be found. Since the 9DSPA-Miner algorithm uses the characteristics of the 9D-SPA representation to prune most of impossible candidates, the experiment results demonstrate that it is more efficient and scalable than the modified Apriori method.     

An order-clique-based approach for mining maximal co-locations

Most algorithms for mining spatial co-locations adopt an Apriori-like approach to generate size-k prevalence co-locations after size-(k − 1) prevalence co-locations. However, generating and storing the co-locations and table instances is costly. A novel order-clique-based approach for mining maximal co-locations is proposed in this paper. The efficiency of the approach is achieved by two techniques: (1) the spatial neighbor relationships and the size-2 prevalence co-locations are compressed into extended prefix-tree structures, which allows the order-clique-based approach to mine candidate maximal co-locations and co-location instances; and (2) the co-location instances do not need to be stored after computing some characteristics of the corresponding co-location, which significantly reduces the execution time and space required for mining maximal co-locations. The performance study shows that the new method is efficient for mining both long and short co-location patterns, and is faster than some other methods (in particular the join-based method and the join-less method).     

A (4n − 9)/3 diagnosis algorithm on n-dimensional cube network

As a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis of multicomputers, the t/k diagnosis strategy can significantly improve the self-diagnosing capability of a system at the expense of no more than k fault-free processors (nodes) being mistakenly diagnosed as faulty. In the case k ? 2, to our knowledge, there is no known t/k diagnosis algorithm for general diagnosable system or for any specific system. Hypercube is a popular topology for interconnecting processors of multicomputers. It is known that an n-dimensional cube is (4n − 9)/3-diagnosable. This paper addresses the (4n − 9)/3 diagnosis of n-dimensional cube. By exploring the relationship between a largest connected component of the 0-test subgraph of a faulty hypercube and the distribution of the faulty nodes over the network, the fault diagnosis of an n-dimensional cube can be reduced to those of two constituent (n − 1)-dimensional cubes. On this basis, a diagnosis algorithm is presented. Given that there are no more than 4n − 9 faulty nodes, this algorithm can isolate all faulty nodes to within a set in which at most three nodes are fault-free. The proposed algorithm can operate in O(N log₂ N) time, where N = 2ⁿ is the total number of nodes of the hypercube. The work of this paper provides insight into developing efficient t/k diagnosis algorithms for larger k value and for other types of interconnection networks.     

The design and analysis of an efficient load balancing algorithm employing the symmetric balanced incomplete block design

In order to maintain load balancing in a distributed network, each node should obtain workload information from all the nodes in the network. To accomplish this, this processing requires O(v²) communication complexity, where v is the number of nodes. First, we present a new synchronous dynamic distributed load balancing algorithm on a (v, k + 1, 1)-configured network applying a symmetric balanced incomplete block design, where v = k² + k + 1. Our algorithm designs a special adjacency matrix and then transforms it to (v, k + 1, 1)-configured network for an efficient communication. It requires only communication complexity and each node receives workload information from all the nodes without redundancy since each link has the same amount of traffic for transferring workload information. Later, this algorithm is revised for distributed networks and is analyzed in terms of efficiency of load balancing.     

A Pattern Decomposition Algorithm for Data Mining of Frequent Patterns

Efficient algorithms to mine frequent patterns are crucial to many tasks in data mining. Since the Apriori algorithm was proposed in 1994, there have been several methods proposed to improve its performance. However, most still adopt its candidate set generation-and-test approach. In addition, many methods do not generate all frequent patterns, making them inadequate to derive association rules. We propose a pattern decomposition (PD) algorithm that can significantly reduce the size of the dataset on each pass, making it more efficient to mine all frequent patterns in a large dataset. The proposed algorithm avoids the costly process of candidate set generation and saves time by reducing the size of the dataset. Our empirical evaluation shows that the algorithm outperforms Apriori by one order of magnitude and is faster than FP-tree algorithm. Received 14 May 2001 / Revised 5 September 2001 / Accepted in revised form 26 October 2001 Correspondence and offprint requests to: Qinghua Zou, Department of Computer Science, California University–Los Angeles, CA 90095, USA. Email: zou@cs.ucla.eduau     

基于Apriori改进算法的入侵检测系统的研究

通过对经典Apriori算法的思想和性能的分析,针对算法中存在的项集生成瓶颈问题:连接步骤的存在,使空间的复杂度较大,提出了一种去掉连接步骤的非连接Apriori算法.该算法通过去掉频繁项集的自连接方式来降低生成的候选项集个数,从而减少扫描数据库的次数,以优化空间复杂度.实验结果表明,改进算法比经典Apriori算法执行效率明显提高.     

Mining frequent patterns from univariate uncertain data

In this paper, we propose a new algorithm called U2P-Miner for mining frequent U2 patterns from univariate uncertain data, where each attribute in a transaction is associated with a quantitative interval and a probability density function. The algorithm is implemented in two phases. First, we construct a U2P-tree that compresses the information in the target database. Then, we use the U2P-tree to discover frequent U2 patterns. Potential frequent U2 patterns are derived by combining base intervals and verified by traversing the U2P-tree. We also develop two techniques to speed up the mining process. Since the proposed method is based on a tree-traversing strategy, it is both efficient and scalable. Our experimental results demonstrate that the U2P-Miner algorithm outperforms three widely used algorithms, namely, the modified Apriori, modified H-mine, and modified depth-first backtracking algorithms.     

An agglomerative clustering algorithm using a dynamic k-nearest-neighbor list

In this paper, a new algorithm is developed to reduce the computational complexity of Ward’s method. The proposed approach uses a dynamic k-nearest-neighbor list to avoid the determination of a cluster’s nearest neighbor at some steps of the cluster merge. Double linked algorithm (DLA) can significantly reduce the computing time of the fast pairwise nearest neighbor (FPNN) algorithm by obtaining an approximate solution of hierarchical agglomerative clustering. In this paper, we propose a method to resolve the problem of a non-optimal solution for DLA while keeping the corresponding advantage of low computational complexity. The computational complexity of the proposed method DKNNA + FS (dynamic k-nearest-neighbor algorithm with a fast search) in terms of the number of distance calculations is O(N²), where N is the number of data points. Compared to FPNN with a fast search (FPNN + FS), the proposed method using the same fast search algorithm (DKNNA + FS) can reduce the computing time by a factor of 1.90-2.18 for the data set from a real image. In comparison with FPNN + FS, DKNNA + FS can reduce the computing time by a factor of 1.92-2.02 using the data set generated from three images. Compared to DLA with a fast search (DLA + FS), DKNNA + FS can decrease the average mean square error by 1.26% for the same data set.     

Mining frequent closed patterns in pointset databases

In this paper, we proposed an efficient algorithm, called PCP-Miner (Pointset Closed Pattern Miner), for mining frequent closed patterns from a pointset database, where a pointset contains a set of points. Our proposed algorithm consists of two phases. First, we find all frequent patterns of length two in the database. Second, for each pattern found in the first phase, we recursively generate frequent closed patterns by a frequent pattern tree in a depth-first search manner. Since the PCP-Miner does not generate unnecessary candidates, it is more efficient and scalable than the modified Apriori, SASMiner and MaxGeo. The experimental results show that the PCP-Miner algorithm outperforms the comparing algorithms by more than one order of magnitude.     

基于日历的时序关联规则挖掘算法

以日历格作为框架来研究时序关联规则,提出了一个有效的挖掘算法。在用户指定的日历模式下,首先通过一次扫描产生所有的频繁2项集及相应的1*日历模式,在此基础上产生k*日历模式,并利用聚集性质产生候选K项集及相应的日历模式,最后扫描事务数据库产生所有的频繁项集及其日历模式。实验证明,该算法具有较好的性能。     

An affinity-based new local distance function and similarity measure for kNN algorithm

In this paper, we propose a modified version of the k-nearest neighbor (kNN) algorithm. We first introduce a new affinity function for distance measure between a test point and a training point which is an approach based on local learning. A new similarity function using this affinity function is proposed next for the classification of the test patterns. The widely used convention of k, i.e., k = [√N] is employed, where N is the number of data used for training purpose. The proposed modified kNN algorithm is applied on fifteen numerical datasets from the UCI machine learning data repository. Both 5-fold and 10-fold cross-validations are used. The average classification accuracy, obtained from our method is found to exceed some well-known clustering algorithms.     

Discovering top-k patterns with differential privacy-an accurate approach

Frequent pattern mining discovers sets of items that frequently appear together in a transactional database; these can serve valuable economic and research purposes. However, if the database contains sensitive data (e.g., user behavior records, electronic health records), directly releasing the discovered frequent patterns with support counts will carry significant risk to the privacy of individuals. In this paper, we study the problem of how to accurately find the top-k frequent patterns with noisy support counts on transactional databases while satisfying differential privacy. We propose an algorithm, called differentially private frequent pattern (DFP-Growth), that integrates a Laplace mechanism and an exponential mechanism to avoid privacy leakage. We theoretically prove that the proposed method is (λ, δ)-useful and differentially private. To boost the accuracy of the returned noisy support counts, we take consistency constraints into account to conduct constrained inference in the post-processing step. Extensive experiments, using several real datasets, confirm that our algorithm generates highly accurate noisy support counts and top-k frequent patterns.     

关联规则挖掘中Apriori算法的研究与改进

经典的产生频繁项目集的Apriori算法存在多次扫描数据库可能产生大量候选及反复对候选项集和事务进行模式匹配的缺陷,导致了算法的效率较低。为此,对Apriori算法进行以下3方面的改进:改进由k阶频繁项集生成k+1阶候选频繁项集时的连接和剪枝策略;改进对事务的处理方式,减少Apriori算法中的模式匹配所需的时间开销;改进首次对数据库的处理方法,使得整个算法只扫描一次数据库,并由此提出了改进算法。实验结果表明,改进算法在性能上得到了明显提高。     

一种基于关联规则Apriori算法的改进研究

介绍Apriori算法的原理和基础,并对制约Apriori算法效率的瓶颈问题提出一种改进策略,针对该算法的两个缺陷,多次扫描事务数据库并产生大量的候选集,提出一种0-1矩阵的改进算法改变由低维频繁项目集到高维频繁项目集的多次连接运算。此改进算法大大减少了访问数据库的次数,提高系统的运行效率,同时还减少大量的候选集的产生,节约存储空间。     

A lattice-based approach for I/O efficient association rule mining

Most algorithms for association rule mining are variants of the basic Apriori algorithm (Agarwal and Srikant, Fast algorithms for mining association rules in databases, in: Proceedings of the 20th International Conference on Very Large Data Bases (VLDB’94), Santiago, Chile, 1994, pp. 487–499). One characteristic of these Apriori-based algorithms is that candidate itemsets are generated in rounds, with the size of the itemsets incremented by one per round. The number of database scans required by Apriori-based algorithms thus depends on the size of the biggest frequent itemsets. In this paper, we devise a more general candidate set generation algorithm, LGen, which generates candidate itemsets of multiple sizes during each database scan. We present an algorithm FindLarge which uses LGen to find frequent itemsets. We show that, given a reasonable set of suggested frequent itemsets, FindLarge can significantly reduce the number of I/O passes required. In the best cases, only two passes are sufficient to discover all the frequent itemsets irrespective of the size of the biggest ones.Two I/O-saving algorithms, namely DIC and Pincher-Search, are compared with FindLarge in a series of experiments. We discuss the conditions under which FindLarge significantly outperforms the others in terms of I/O efficiency.     

快速挖掘全局频繁项目集

分布式环境中，全局频繁项目集的挖掘是数据挖掘中最重要的研究课题之一．传统的全局频繁项目集挖掘算法采用Apriori算法框架，须多遍扫描数据库并产生大量的候选项目集，且通过传送局部频繁项目集求全局频繁项目集的网络通信代价高．为此，提出了一种分布数据库的全局频繁项目集快速挖掘算法——FMAGF.FMAGF算法采用传送条件频繁模式树或条件模式基来挖掘全局频繁项目集，可有效地减小网络通信量，提高全局频繁项目集挖掘效率．理论分析和实验结果表明提出的算法是有效可行的．     

Effects of spatial and spectral resolution in estimating ecosystem α-diversity by satellite imagery

Remote sensing represents a powerful tool to derive quantitative and qualitative information about ecosystem biodiversity. In particular, since plant species richness is a fundamental indicator of biodiversity at the community and regional scales, attempts were made to predict species richness (spatial heterogeneity) by means of spectral heterogeneity. The possibility of using spectral variance of satellite images for predicting species richness is known as Spectral Variation Hypothesis. However, when using remotely sensed data, researchers are limited to specific scales of investigation. This paper aims to investigate the effects of scale (both as spatial and spectral resolution) when searching for a relation between spectral and spatial (related to plant species richness) heterogeneity, by using satellite data with different spatial and spectral resolution. Species composition was sampled within square plots of 100 m² nested in macroplots of 10,000 m². Spectral heterogeneity of each macroplot was calculated using satellite images with different spatial and spectral resolution: a Quickbird multispectral image (4 bands, spatial resolution of 3 m), an Aster multispectral image (first 9 bands used, spatial resolution of 15 m for bands 1 to 3 and 30 m for bands 4 to 9), an ortho-Landsat ETM+ multispectral image (bands 1 to 5 and band 7 used; spatial resolution, 30 m), a resampled 60 m Landsat ETM+ image.Quickbird image heterogeneity showed a statistically highly significant correlation with species richness (r = 0.69) while coarse resolution images showed contrasting results (r = 0.43, r = 0.67, and r = 0.69 considering the Aster, Landsat ETM+, and the resampled 60 m Landsat ETM+ images respectively). It should be stressed that spectral variability is scene and sensor dependent. Considering coarser spatial resolution images, in such a case even using SWIR Aster bands (i.e. the additional spectral information with respect to Quickbird image) such an image showed a very low power in catching spectral and thus spatial variability with respect to Landsat ETM+ imagery. Obviously coarser resolution data tend to have mixed pixel problems and hence less sensitive to spatial complexity. Thus, one might argue that using a finer pixel dimension should inevitably result in a higher level of detail. On the other hand, the spectral response from different land-cover features (and thus different species) in images with higher spectral resolution should exhibit higher complexity.Spectral Variation Hypothesis could be a basis for improving sampling designs and strategies for species inventory fieldwork. However, researchers must be aware on scale effects when measuring spectral (and thus spatial) heterogeneity and relating it to field data, hence considering the concept of scale not only related to a spatial framework but even to a spectral one.     

Apriori-sort算法研究

Apriori算法虽然在候选集的产生时利用了剪支技术,但每次扫描数据库时都必须扫描整个数据库,因此扫描的数据量大,速度较慢。Apriori-sort算法是在Apriori算法基础上的改进,基本思想是把事务数据库变为以度表示的事务度数据库,并对事务度数据库进行排序。Apriori-sort算法查找频繁项集时,只扫描数据库Dd中满足d（Ck）≦d（Ti）的事务。对扫描数据库进行了有效剪支,因此Apriori-sort算法的计算效率高。并用仿真数据对Apriori-sort算法和Apriori算法进行了仿真对比实验,实验结果证明了新算法的高效性。     

Fast Discovery Of Long Patterns For Association Rules

The most time consuming process in discovering association rules is identifying the frequent patterns especially in the cases when the database contains long patterns. An algorithm called Flex for identifying frequent patterns especially efficient when the patterns are long is proposed by successive construction of the nodes lexicographic tree. The vertical counting strategy to facilitate fast discovery is used in support computation. The experimental result shows that Flex outperform Apriori, a well-known and widely used algorithm for patterns discovery.     

分布环境中的并行频繁模式挖掘算法

频繁模式的并行挖掘算法是数据挖掘中重要的研究课题。目前已经提出的并行算法大多是基于Apriori或基于FP-tree。由于两者的固有局限性,而且在计算过程中需要多次同步,因而具有较低的性能。文章提出了一种基于分布数据库的并行挖掘算法。该算法尽可能地让每个处理器独立地挖掘,每个处理器基于前缀树采用深度优先搜索的策略挖掘局部频繁模式集,并通过相关性质尽量减少候选全局频繁模式的规模,减少网络的通信量和同步次数以提高挖掘效率。