Simple algorithms for some classification problems

Stephan Olariu; Nageswara S.V. Rao

doi:10.1016/0167-8655(95)00095-X

Simple algorithms for some classification problems

Stephan Olariu, Nageswara S.V. Rao

Autonomous and Complex Systems

Research output: Contribution to journal › Article › peer-review

Abstract

Consider two classifiers C₁ and C₂ each partitioning a collection A of n objects into classes based on respective sets of features. In a number in pattern recognition and knowledge engineering applications, the following problems arise: given the two partitions generated by C₁ and C₂, compute new partitions by considering (i) the features common to both classifiers, and (ii) the features of either of the classifiers. We show that both problems can be solved in Θ (n log n) time using very simple algorithms.

Original language	English
Pages (from-to)	163-167
Number of pages	5
Journal	Pattern Recognition Letters
Volume	17
Issue number	2
DOIs	https://doi.org/10.1016/0167-8655(95)00095-X
State	Published - Feb 8 1996

Funding

* The work of the first author is supported in part by NSF grant CCR-9407180 and by ONR grant N00014-95-1-0779. The work of the second author is sponsored by the Engineering Research Program of the Office of Basic Energy Sciences, of the U. S. Department of Energy, under Contract No. DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc. * Corresponding author. Email: [email protected]

Keywords

Classification
Equivalence relations
Partitions
Pattern recognition
Refinement

Access to Document

10.1016/0167-8655(95)00095-X

Cite this

@article{a9a8dbd060e44fcf9127c26c87d1e140,

title = "Simple algorithms for some classification problems",

abstract = "Consider two classifiers C1 and C2 each partitioning a collection A of n objects into classes based on respective sets of features. In a number in pattern recognition and knowledge engineering applications, the following problems arise: given the two partitions generated by C1 and C2, compute new partitions by considering (i) the features common to both classifiers, and (ii) the features of either of the classifiers. We show that both problems can be solved in Θ (n log n) time using very simple algorithms.",

keywords = "Classification, Equivalence relations, Partitions, Pattern recognition, Refinement",

author = "Stephan Olariu and Rao, {Nageswara S.V.}",

year = "1996",

month = feb,

day = "8",

doi = "10.1016/0167-8655(95)00095-X",

language = "English",

volume = "17",

pages = "163--167",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Simple algorithms for some classification problems

AU - Olariu, Stephan

AU - Rao, Nageswara S.V.

PY - 1996/2/8

Y1 - 1996/2/8

N2 - Consider two classifiers C1 and C2 each partitioning a collection A of n objects into classes based on respective sets of features. In a number in pattern recognition and knowledge engineering applications, the following problems arise: given the two partitions generated by C1 and C2, compute new partitions by considering (i) the features common to both classifiers, and (ii) the features of either of the classifiers. We show that both problems can be solved in Θ (n log n) time using very simple algorithms.

AB - Consider two classifiers C1 and C2 each partitioning a collection A of n objects into classes based on respective sets of features. In a number in pattern recognition and knowledge engineering applications, the following problems arise: given the two partitions generated by C1 and C2, compute new partitions by considering (i) the features common to both classifiers, and (ii) the features of either of the classifiers. We show that both problems can be solved in Θ (n log n) time using very simple algorithms.

KW - Classification

KW - Equivalence relations

KW - Partitions

KW - Pattern recognition

KW - Refinement

UR - http://www.scopus.com/inward/record.url?scp=0030574673&partnerID=8YFLogxK

U2 - 10.1016/0167-8655(95)00095-X

DO - 10.1016/0167-8655(95)00095-X

M3 - Article

AN - SCOPUS:0030574673

SN - 0167-8655

VL - 17

SP - 163

EP - 167

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 2

ER -

Simple algorithms for some classification problems

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this