Hierarchical Clustering using Reconfigurable Devices ∗

Non-hierarchical k-means algorithms have been implemented in hardware, most frequently for image clustering. Here, we focus on hierarchical clustering of text documents based on document similarity. To our knowledge, this is the first work to present a hierarchical clustering algorithm designed for hardware implementation and ours is the first hardware-accelerated implementation. 1. Hierarchical Clustering Clustering partitions a set of items into subsets with similar characteristics by maximizing intracluster similarity while minimizing intercluster similarity, according to a given similarity metric. In hierarchical clustering, each sub-cluster is recursively clustered. A well-studied special case is where the items correspond to text documents and the similarity metric is based on viewing a document as a “bag-of-words”, or “bag-of-word-disjunctions ” [4, 5]. That is, documents are points in a high-dimensional space where each dimension corresponds to the frequency/occurrence of one or more words in the document. Input to Hierarchical Partitioning (HP) clustering is a set of N k-dimensional points (vectors) in a binary space and output is a binary tree where each point corresponds to exactly one leaf. Points (from tree root downward) are partitioned into sets left and right, maximizing score(left) + score(right). The algorithm terminates when left and right are individual points. The function score maps sets of points to reals, and measures cohesiveness. Specifically, for a set of points C = {�a1,�a2,...,�an}, let sum(C) � n