Question

Constraint-based Clustering is an approach that cluster data while satisfying a requirement of the domain knowledge on the cluster assignment. The constraints are usually expressed as pairwise statements indicating that two items must, or cannot, be placed into the same cluster. 1. Explain the hard and soft constraint approach in clustering. 2. Name one algorithm used in each type on constraint-based clustering in (1). Discuss how constraint-based clustering is applied on spatial data. You may include a real world example in your discussion.

Answer 1

ANSWER:--

GIVEN THAT:--

Hard constraints:--
Hard constraints are constraints that are absolutely non-negotiable.

The scheduling engine will always respect every hard constraint that you give it.

When you specify a hard constraint, you're effectively telling the scheduler that "If I can't have this constraint met,

then I don't want any schedule at all."
In many cases,

hard constraints also make the scheduler run slower, which also decreases the likelihood that it will find any schedules for you within the its computation window.
Soft constraints:
Soft constraints, on the other hand, are constraints that could be negotiated once in awhile. The scheduling engine still works hard to respect every soft constraint that you give it, but will make an exception on the constraint in the rare case that something must give.
When you specify a soft constraint, you're effectively telling the scheduler that "If I can't have this constraint met, I suppose it's okay--just do the best you can. I'd rather have a near-perfect schedule than no schedule at all."
Soft constraints never slow the scheduler down, which also increases the likelihood that it will find schedules for you within its computation window.
Which type should I use, and when?
Try to minimize the number of hard constraints that you use. Hard constraints usually make the scheduler run slower, which also decreases the likelihood that it will find any schedules for you within the its computation window.
You're encouraged to use as many soft constraints as you like. There is no computational penalty for using more of them.
Comparison
Hard constraints Soft constraints
Absolutely non-negotiable Negotiable if necessary
Always respected by the scheduler Usually respected by the scheduler
Exceptions are never made Exceptions are made if it's the difference between generating a schedule and not generating one
Usually make the scheduler run slower No impact on scheduler speed
  
Decrease likelihood that the scheduler Likelihood of finding schedules not affected
will find any schedules
  
Too many hard constraints may mean not
getting any schedules No penalty for having lots and lots of soft constraints

SolvingProblemswithHardandSoftConstraintsUsinga StochasticAlgorithmforMAX-SAT:
Walksat(WEIGHTED-CLAUSES,HARD-LIMIT, MAX-FLIPS,
TARGET, MAX-TRIES,NOISE)
M:=a randomtruthassignmentoverthevariablesthat
appearinWEIGHTED-CLAUSES;
HARD-UNSAT :=clausesnotsatisfiedbyMwithweight>HARD-LIMIT;
SOFT-UNSAT :=clausesnotsatisfiedbyMwithweight<HARD-LIMIT;
BAD:sumoftheweightofHARD-SAT andSOFT-UNSAT;
TOPLOOP:forI :=1toMAX-TRIESdo
forJ :=1toMAX-FLIPSdo
if BAD=TARGETthenbreakfromTOPLOOP;endif
if HARD-UNSAT is notemptythen
C :=a randommemberofHARD-UNSAT;
elseC :=a randommemberofSOFT-UNSAT;endif
Flip a cointhathasprobabilityNOISEofheads;
if heads then
P :=a randomlychosenvariablethatappearsinC;
else
for eachpropositionQ thatappearsinC do
BREAKCOUNT[Q]:=0;
for eachclauseC’thatcontainsQ do
if C’is satisfiedbyM,but not
satisfiedif Q is flipped then
BREAKCOUNT[Q]:=weightofC’
end if
end for
end for
P :=a randomlychosenvariableQ thatappearsinC andwhose
BREAKCOUNT[Q]valueis minimal;
endif
FlipthevalueassignedtoP byM;
UpdateHARD-UNSAT, SOFT-UNSAT, andBAD;
endfor
endfor
print“Weightofunsatisfiedclausesis”,BAD;
printM;
endWalksat.

Real world example FOR Hard Constraints:
Student "Must Not" availability entries
Therapist "Must Not" availability entries
“Must” Groupings
“Must Only” Groupings
“Must Not” Groupings
Therapist travel time between buildings
Therapist Locked to Building
Therapist Start Time
Therapist End Time
Maximum Group Size
Maximum Grade Span
Student Start Time
Student End Time
Buildings
Categories
Days Apart
Delivery Model
Exact Time Spans
Real world example FOR Soft Constraints:
Student "Prefer Not" availability entries
Student "Prefer" availability entries
“Prefer” Groupings
“Prefer Only” Groupings
“Prefer Not” Groupings
Therapist Day Start Buffer
Therapist Day End Buffer
Therapist Lunchtime
Therapist Post-Session Recovery
Session Goals
Anything else you set preferences for:
Productivity
Session Cost
Billing Cost
Behavior Cost
Grade Span Cost
Classroom Count Cost
Goal Count Cost
Travel Trip Cost
Travel Time Cost
"Must Not" availability entries
"Must Not" availability entries are hard constraints, whereas "Prefer Not" entries are soft constraints. Where possible, try to use "Prefer Not" instead of "Must Not". Just like with "Must Not" entries, the scheduler will still work hard to avoid "Prefer Not" entries, but will make sparing exceptions when required in order to give you a workable schedule.
SolvingProblemswithHardandSoftConstraintsUsinga StochasticAlgorithmforMAX-SAT: