【正文】 same as their true location, thus creating clusters a’, b’, c’ and c’’. Note that a’ has one fewer object than a, and b’ has one more object than b. Also, c is mistakenly split into c’ and c’’. (c) Line uncertainty is considered to produce clusters a’, b’ and c. The clustering result is closer to that of (a) than (b). We suggest incorporating uncertainty information, such as the probability density functions (pdf) of uncertain data, into existing data mining methods so that the mining results could resemble closer to the results obtained as if actual data were available and used in the mining process (Figure 2(c)). In this paper we study how uncertainty can be incorporated in data mining by using data clustering as a motivating example. We call this the Uncertain Data Mining problem. In this paper, we present a framework for possible research directions in this area. The rest of the paper is structured as follows. Related work is reviewed in Section 2. Uncertain Data Mining: A New Research Direction 3 In Section 3 we define the problem of clustering on data with uncertainty and present our proposed algorithm. Section 4 presents the application of our algorithm to a movingobject database. Detailed experiment results are shown in Section 5. We conclude our paper and suggest possible research directions in Section 6. 2. Research Background In recent years, there is significant research interest in data uncertainty management. Data uncertainty can be categorized into two types, namely existential uncertainty and value uncertainty. In the first type it is uncertain whether the object or data tuple exists or not. For example, a tuple in a relational database could be associated with a probability value that indicates the confidence of its presence[1,11]. In value uncertainty, a data item is modelled as a closed region which bounds its possible values, together with a probability density function (pdf) of its value [3,4,12,15]. This model can be used to quantify the imprecision of location and sensor data in a constantlyevolving works in this area have been devoted to “imprecise queries”, which provide probabilistic guarantees over correctness of answers. For example, in [5], indexing solutions for range queries over uncertain data have been proposed. The same authors also proposed solutions for aggregate queries such as nearestneighbor queries in [4]. Notice that all these works have applied the study of uncertain data management to simple database queries, instead of to the relatively more plicated data analysis and mining problems. The clustering problem has been well studied in data mining research. A standard clustering process consists of five major steps: pattern representation, definition of a pattern similarity metric, clustering or grouping, data abstraction, and output assessment [10]. Only a few studies on data mining or data clustering for uncertain data have been reported. Hamdan and Govaert have addressed the problem of fitting mixture densities to uncertain data for clustering using the EM algorithm [8]. However, the model cannot be readily applied to other clustering algorithms and is rather customized for on interval data also has been studied. Different distance measures, like cityblock distance or Minkowski distance, have been used in measuring the similarity between two intervals [6,9]. The pdf of the interval is not taken into account in most of these metrics. Another related area of research is fuzzy clustering. Fuzzy clustering has been long studied in fuzzy logic [13]. In fuzzy clustering, a cluster is represented by a fuzzy subset Uncertain Data Mining: A New Research Direction 4 of a set of objects. Each object has a “degree of belongingness” for each cluster. In other words, an object can belong to more than one cluster, each with a different degree. The fuzzy cmeans algorithm was one of the most widely used fuzzy clustering method [2,7]. Different fuzzy clustering methods have been applied on normal data or fuzzy data to produce fuzzy clusters [14]. While their work is based on a fuzzy data model, our work is developed based on the uncertainty model of moving objects. 3. Taxonomy of Uncertain Data Mining In Figure 2, we propose a taxonomy to illustrate how data mining methods can be classified based on whether data imprecision is considered. There are a number of mon data mining techniques, ., association rule mining, data classification, data clustering, that need to be modified in order to handle uncertain data. Moreover, we distinguish two types of data clustering: hard clustering and fuzzy clustering. Hard clustering aims at improving the accuracy of clustering by considering expected data values after data uncertainty is considered. On the other hand, fuzzy clustering presents the clustering result in a “fuzzy” form. An example of a fuzzy clustering result is that each data item is given a probability of being assigned to each member in a set of clusters [14]. Figure 2. A taxonomy of data mining on data with uncertainty For example, when uncertainty is considered, there is an interesting problem on how each tuple and the uncertainty associated should be represented in the dataset. Moreover, the notion of support and other metrics would need to be redefined. Wellknown association rule mining algorithm (such as Apriori) has to be revised in order to take this into account. Similarly, in data classification and data clustering, traditional algorithms may not work any more because uncertainty was not taken into account. Important Uncertain Data Mining: A New Research Direction 5 metrics, like cluster centroids, distance between two objects, or distance between an object and a centroid, have to be redefined and further studied. 4. Example on Uncertain Data Clustering In this section, we prese