Mostrar el registro sencillo del ítem
Artículo
Separability of Point Sets by k-Level Linear Classification Trees
dc.creator | Arkin, Esther M. | |
dc.creator | Garijo Royo, Delia | |
dc.creator | Márquez Pérez, Alberto | |
dc.creator | Mitchell, Joseph S. B. | |
dc.creator | Seara Ojea, Carlos | |
dc.date.accessioned | 2016-03-17T12:42:51Z | |
dc.date.available | 2016-03-17T12:42:51Z | |
dc.date.issued | 2012 | |
dc.identifier.uri | http://hdl.handle.net/11441/38751 | |
dc.description.abstract | Let R and B be sets of red and blue points in the plane in general position. We study the problem of computing a k-level binary space partition (BSP) tree to classify/separate R and B, such that the tree defines a linear decision at each internal node and each leaf of the tree corresponds to a (convex) cell of the partition that contains only red or only blue points. Specifically, we show that a 2-level tree can be computed, if one exists, in time O(n2). We show that a minimum-level (3 ≤ k ≤ log n) tree can be computed in time nO(log n). In the special case of axis-parallel partitions, we show that 2-level and 3-level trees can be computed in time O(n), while a minimum-level tree can be computed in time O(n5). | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.relation.ispartof | International Journal of Computational Geometry & Applications, 22 (2), 143-165. | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Red-blue separation | es |
dc.subject | binary space partitions | es |
dc.subject | classification | es |
dc.subject | decision trees | es |
dc.subject | machine learning | es |
dc.title | Separability of Point Sets by k-Level Linear Classification Trees | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.identifier.doi | http://dx.doi.org/10.1142/S0218195912500021 | es |
dc.journaltitle | International Journal of Computational Geometry & Applications | es |
dc.publication.volumen | 22 | es |
dc.publication.issue | 2 | es |
dc.publication.initialPage | 143 | es |
dc.publication.endPage | 165 | es |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/38751 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Separability of points.pdf | 382.9Kb | [PDF] | Ver/ | |