I am facing a problem of learning clusters from a pairwise dissimilarity matrix. The measures i try are not metrics(not symmetric,no triangular equality), like KL-divergence for example. Are there Clustering methods i can use to find clusters from these kinds of matrices? If i have labels available, what kind of cluster validation techniques can i use?
Classic hierarchical cluster analysis requires the proximity matrix to be symmetric. So, you have to symmetricize your matrix, for example, averaging elements above and below the diagonal.
If it lacks triangular inequality, you can't use methods such as Ward, centroid, median, which are called "geometric" ones because they need distances be euclidean, - or metric at worst. Other methods, such as nearest neighbour, farthest neighbour, average linkage - you still can use them.
Also, you might choose to rectify your dissimilarities into metric/euclidean by adding constant to all the elements. Iteratively add small value and check when the "double centrat" of the matrix looses negative eigenvalues. When it's lost, your dissimilarities got euclidean. Look here how to do double centering.