Konstruerad klusterbildning har varit välstuderad för algoritmer som K-medel och hierarkisk agglomerativ klusterbildning. Men hur man kodar begränsningar i spektral klusterbildning är fortfarande ett utvecklings område. I detta dokument föreslår vi en flexibel och generaliserad ram för begränsad spektralklustring. I motsats till några tidigare ansträngningar som implicit kodar Must-Link och kan inte-Link begränsningar genom att ändra grafen Laplacian eller den resulterande eigenspace, presenterar vi en mer naturlig och principfast formulering, som bevarar den ursprungliga grafen Laplacian och uttryckligen kodar begränsningarna. Vår metod erbjuder flera praktiska fördelar: det kan koda graden av tro (vikt) på MustLink och kan inte-Link begränsningar; det garanterar att sänka hur väl de givna begränsningarna är nöjda med hjälp av en användarspecificerad tröskel; och det kan lösas deterministiskt i polynom tid genom generaliserad eigendecomposition. Dessutom, genom att ärva den objektiva funktionen från spektral klustring och explicit koda begränsningarna, är en stor del av den befintliga analysen av spektral klustring tekniker fortfarande giltig. Följaktligen kan vårt arbete ses som en naturlig förlängning till okonstruerad spektralkluster och tolkas som att hitta den normaliserade min-cut av en märkt graf. Vi validerar effektiviteten i vårt tillvägagångssätt genom empiriska resultat på verkliga datamängder, med tillämpningar för begränsad bildsegmentering och kluster av referensdatamängder med både binära och grad av trosförmågor.
I REF föreslog Wang och Davidson en flexibel begränsad spektral kluster algoritm, som kan lösas i polynom tid och även tillåter mjuka begränsningar.
Flexible constrained spectral clustering
{'venue': "KDD '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}