Interval Finding and Its Application to Data Mining

Takeshi FUKUDA; Yasuhiko MORIMOTO; Shinichi MORISHITA; Takeshi TOKUYAMA

Interval Finding and Its Application to Data Mining

Takeshi FUKUDA, Yasuhiko MORIMOTO, Shinichi MORISHITA, Takeshi TOKUYAMA

Full Text Views

0

Cite this

Summary :

In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let I be the set of all intervals on U = {1, 2, , n}. Consider an objective function f(I), conditional functions u_i(I) on I, 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 alogorithms 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) = Σ_iIf^(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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.4 pp.620-626

Publication Date: 1997/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Takeshi FUKUDA, Yasuhiko MORIMOTO, Shinichi MORISHITA, Takeshi TOKUYAMA, "Interval Finding and Its Application to Data Mining" in IEICE TRANSACTIONS on Fundamentals, vol. E80-A, no. 4, pp. 620-626, April 1997, doi: .
Abstract: In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let I be the set of all intervals on U = {1, 2, , n}. Consider an objective function f(I), conditional functions u_i(I) on I, 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 alogorithms 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) = Σ_iIf^(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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_4_620/_p

Copy

@ARTICLE{e80-a_4_620,
author={Takeshi FUKUDA, Yasuhiko MORIMOTO, Shinichi MORISHITA, Takeshi TOKUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Interval Finding and Its Application to Data Mining},
year={1997},
volume={E80-A},
number={4},
pages={620-626},
abstract={In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let I be the set of all intervals on U = {1, 2, , n}. Consider an objective function f(I), conditional functions u_i(I) on I, 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 alogorithms 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) = Σ_iIf^(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.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Interval Finding and Its Application to Data Mining
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 620
EP - 626
AU - Takeshi FUKUDA
AU - Yasuhiko MORIMOTO
AU - Shinichi MORISHITA
AU - Takeshi TOKUYAMA
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1997
AB - In this paper, we investigate inverse problems of the interval query problem in application to data mining. Let I be the set of all intervals on U = {1, 2, , n}. Consider an objective function f(I), conditional functions u_i(I) on I, 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 alogorithms 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) = Σ_iIf^(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.
ER -