Interval Finding and Its Application to Data Mining (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let τ be the set of all intervals on U = {1,2, ..., n}. Consider an objective function f(I), conditional functions U_i(I) on τ, and define an optimization problem of finding the interval I maximizing f(I) subject to U_i (I) > K_i for given real numbers K_i (i = 1, 2, ..., h). We propose efficient algorithms to solve the above optimization problem if the objective function is either additive or quotient, and the conditional functions are additive, where a function f is additive if f(I) = Σ<i∈I>f^^^(i) extending a function f^^^ on U, and quotient if it is represented as a quotient of two additive functions. We use computational-geometric methods such as convex hull, range searching, and multidimensional divide-and-conquer.
社団法人電子情報通信学会の論文
1997-04-25