ASP-KNN: A Declarative, Constraint-Aware, and Explainable Reformulation of k-Nearest Neighbors in Answer Set Programming

ASP-KNN: A Declarative, Constraint-Aware, and Explainable Reformulation of k-Nearest Neighbors in Answer Set Programming | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article ASP-KNN: A Declarative, Constraint-Aware, and Explainable Reformulation of k-Nearest Neighbors in Answer Set Programming Liu Liu, Dongjie Tang, Xunpeng Xia This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8787247/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 11 You are reading this latest preprint version Abstract Traditional $k$-Nearest Neighbors (KNN) offers a simple and effective non-parametric approach for classification but lacks transparency and the ability to incorporate domain-specific constraints. This study introduces \emph{ASP-KNN}, a declarative reformulation of KNN using Answer Set Programming (ASP), which expresses neighbor selection, ranking, and voting through logical rules and supports both hard and soft reasoning constraints. The baseline ASP-KNN program replicates deterministic top-$k$ selection and majority voting, while its extensions enable rule-based exclusion of forbidden labels and preference-guided optimization to improve local label consistency. The soft preference model adopts a two-level objective that first minimizes label–neighbor mismatches and then applies a distance-weighted penalty, allowing the solver to favor predictions supported by closer neighbors in ambiguous cases. Experiments on benchmark datasets (UCI Iris and Wine) using stratified 5-fold cross-validation show that ASP-KNN achieves accuracy comparable to classical KNN (e.g., $96.7%$ on Iris at $k{=}3$) while offering additional interpretability. The exclusion rule ensures full constraint compliance (violation rate $=0.0%$) and increases accuracy by up to $2%$, and the distance-weighted soft preference further reduces inconsistency cost by 15–20% without degrading performance. These results demonstrate that ASP-KNN preserves the predictive strength of conventional KNN while providing transparent, policy-aware, and optimizable decision reasoning within a unified logical framework. Answer Set Programming k-Nearest Neighbors Machine Learning Explainable AI Declarative Optimization Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Revision requested 23 Feb, 2026 Reviews received at journal 21 Feb, 2026 Reviews received at journal 19 Feb, 2026 Reviews received at journal 16 Feb, 2026 Reviewers agreed at journal 15 Feb, 2026 Reviewers agreed at journal 11 Feb, 2026 Reviewers agreed at journal 11 Feb, 2026 Reviewers invited by journal 09 Feb, 2026 Editor assigned by journal 05 Feb, 2026 Submission checks completed at journal 05 Feb, 2026 First submitted to journal 04 Feb, 2026 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8787247","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":589016678,"identity":"c5b06c3c-1940-4e95-9600-2dc23cf7fbf4","order_by":0,"name":"Liu Liu","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA3klEQVRIie3PMQrCMBSA4ZRCu0Rcn4P2CpGADi14lRQhXaI4dnCoFNrRteDgFTyCEMhUdwcHe4N6gWLr5mCsm0P+7cH74D2ETKY/bGhb+aOOYYLgNdvfyShPlQ1lQPsTUiqOBhkPk94EXcXsDo6Mjoe0qlHsh4l7OWuFVYg52WC5Ot0UBVRGYYLXTEtsEAQAWgLCQVYm2wsx0RKnI5jIyCs60vQgGCsOmHHWPtWSpAcBN5UUzsH0dOUUmIpohoWeLKS1qx4NeF6xrOp664/3bqkn77Huux/2TSaTyfShJ+6ZQ34X84QEAAAAAElFTkSuQmCC","orcid":"","institution":"Shanghai Customs College","correspondingAuthor":true,"prefix":"","firstName":"Liu","middleName":"","lastName":"Liu","suffix":""},{"id":589016679,"identity":"7c44e613-2a8c-4b3d-ba20-6878d3c86ca2","order_by":1,"name":"Dongjie Tang","email":"","orcid":"","institution":"Shanghai Customs College","correspondingAuthor":false,"prefix":"","firstName":"Dongjie","middleName":"","lastName":"Tang","suffix":""},{"id":589016680,"identity":"27d6d498-7178-4a10-b2a6-8412ca75922e","order_by":2,"name":"Xunpeng Xia","email":"","orcid":"","institution":"Shanghai Customs College","correspondingAuthor":false,"prefix":"","firstName":"Xunpeng","middleName":"","lastName":"Xia","suffix":""}],"badges":[],"createdAt":"2026-02-04 13:40:20","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8787247/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8787247/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":102367849,"identity":"b720e7c3-4da9-476f-94a2-cb16a5c54c5a","added_by":"auto","created_at":"2026-02-11 03:01:42","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":335555,"visible":true,"origin":"","legend":"","description":"","filename":"jksu43.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8787247/v1_covered_fe4becad-3447-41cd-8efd-6da28f05782a.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"ASP-KNN: A Declarative, Constraint-Aware, and Explainable Reformulation of k-Nearest Neighbors in Answer Set Programming","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"journal-of-king-saud-university-computer-and-information-sciences","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Journal of King Saud University Computer and Information Sciences](https://link.springer.com/journal/44443)","snPcode":"44443","submissionUrl":"https://submission.springernature.com/new-submission/44443/3","title":"Journal of King Saud University Computer and Information Sciences","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Open","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"Answer Set Programming, k-Nearest Neighbors, Machine Learning, Explainable AI, Declarative Optimization","lastPublishedDoi":"10.21203/rs.3.rs-8787247/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8787247/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Traditional $k$-Nearest Neighbors (KNN) offers a simple and effective non-parametric approach for classification but lacks transparency and the ability to incorporate domain-specific constraints. This study introduces \\emph{ASP-KNN}, a declarative reformulation of KNN using Answer Set Programming (ASP), which expresses neighbor selection, ranking, and voting through logical rules and supports both hard and soft reasoning constraints. The baseline ASP-KNN program replicates deterministic top-$k$ selection and majority voting, while its extensions enable rule-based exclusion of forbidden labels and preference-guided optimization to improve local label consistency. The soft preference model adopts a two-level objective that first minimizes label–neighbor mismatches and then applies a distance-weighted penalty, allowing the solver to favor predictions supported by closer neighbors in ambiguous cases. Experiments on benchmark datasets (UCI Iris and Wine) using stratified 5-fold cross-validation show that ASP-KNN achieves accuracy comparable to classical KNN (e.g., $96.7\\%$ on Iris at $k{=}3$) while offering additional interpretability. The exclusion rule ensures full constraint compliance (violation rate $=0.0\\%$) and increases accuracy by up to $2\\%$, and the distance-weighted soft preference further reduces inconsistency cost by 15–20\\% without degrading performance. These results demonstrate that ASP-KNN preserves the predictive strength of conventional KNN while providing transparent, policy-aware, and optimizable decision reasoning within a unified logical framework.","manuscriptTitle":"ASP-KNN: A Declarative, Constraint-Aware, and Explainable Reformulation of k-Nearest Neighbors in Answer Set Programming","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-02-11 03:01:35","doi":"10.21203/rs.3.rs-8787247/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2026-02-23T09:52:37+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-02-21T13:11:17+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-02-19T15:07:23+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-02-16T16:31:13+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"268967938917533518209863482112830343194","date":"2026-02-16T03:52:17+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"64372322495187195495826179132146434178","date":"2026-02-11T14:58:40+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"299710991640546011096268021699221338134","date":"2026-02-11T05:49:51+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-02-09T09:45:07+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-02-05T10:25:39+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-02-05T10:19:45+00:00","index":"","fulltext":""},{"type":"submitted","content":"Journal of King Saud University Computer and Information Sciences","date":"2026-02-04T13:24:55+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"journal-of-king-saud-university-computer-and-information-sciences","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Journal of King Saud University Computer and Information Sciences](https://link.springer.com/journal/44443)","snPcode":"44443","submissionUrl":"https://submission.springernature.com/new-submission/44443/3","title":"Journal of King Saud University Computer and Information Sciences","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Open","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"7bebf9f7-24db-42de-811d-af6906abc7a6","owner":[],"postedDate":"February 11th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-05-05T13:26:36+00:00","versionOfRecord":[],"versionCreatedAt":"2026-02-11 03:01:35","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8787247","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8787247","identity":"rs-8787247","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}