Database Reference
In-Depth Information
BEGIN
FOR
k
=1
,...,K
let
r
k
be a randomly chosen point in
T
;
WHILE changes in clusters
C
k
happen DO
/* Form clusters */
FOR
k
=1
,...,K
DO
C
k
=
{x
i
∈ T | d
(
r
k
,x
i
)
≤ d
(
r
j
,x
i
)
∀j
=1
,...,K,j
=
k}
;
END;
/* Compute new cluster centers */
FOR
k
=1
,...,K
;
DO
r
k
=
the vector mean of the points in
C
k
;
END;
END;
END;
There are several enhancements and variations of the classic clustering
method. A relevant one is hierarchical clustering. The idea behind
hierar-
chical clustering
is to reduce or increase iteratively the number of clusters
of a given model. In the first case, we have
agglomerative algorithms
;in
the second one, we have
divisive algorithms
. Let us consider agglomerative
algorithms. The rationale is that if two clusters are close to each other (given
the distance function in use), we can merge them into a single one. The
general algorithm is given below:
Agglomerative Algorithm
INPUT: A data set
T
containing
n
data points
(
x
1
,...,x
n
)
.
Afunction
d
(
C
i
,C
j
)
to measure the distance between clusters.
OUTPUT: A set of
K
clusters
C
1
,...,C
K
BEGIN
FOR
k
=1
,...,n
let
C
i
=
{x
i
}
;
WHILE there is more than one cluster left DO
Let
C
i
and
C
j
be the clusters minimizing the distance between
all pairs of clusters;
C
i
=
C
i
∪ C
j
;
Remove
C
j
;
END;
END;
9.1.4 Association Rules
Association analysis aims at discovering interesting relationships hidden in
large data sets. Although it can be used in many domains, it is a very popular
technique for market basket analysis, for example, in the retail industry. Thus,
the goal of mining association rules in databases is to discover associations
between items that are present in a set of transactions. Although through
this technique we can find many trivial associations, it is also possible to
find unexpected associations, that is, items that are frequently purchased
together although their relationship is not that obvious. Like in all data
mining techniques, data preprocessing must be performed to produce the
Search WWH ::
Custom Search