hac_bic.py 7.79 KB
Newer Older
Anthony Larcher's avatar
Anthony Larcher committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding: utf-8 -*-
#
# This file is part of s4d.
#
# s4d is a python package for speaker diarization.
# Home page: http://www-lium.univ-lemans.fr/s4d/
#
# s4d is free software: you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as
# published by the Free Software Foundation, either version 3 of the License,
# or (at your option) any later version.
#
# s4d is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with s4d.  If not, see <http://www.gnu.org/licenses/>.


"""
Anthony Larcher's avatar
Anthony Larcher committed
23
Copyright 2014-2020 Sylvain Meignier
Anthony Larcher's avatar
Anthony Larcher committed
24
"""
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
25
26

import copy
Anthony Larcher's avatar
Anthony Larcher committed
27
28
29
30
31
32
33
import logging
import numpy as np

from ..diar import Diar
from .gauss import GaussFull
from .hac_utils import argmin, roll
from .hac_utils import bic_square_root
Sylvain Meignier's avatar
??    
Sylvain Meignier committed
34
from math import isnan
Anthony Larcher's avatar
Anthony Larcher committed
35

Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class HAC_BIC:
    """
    BIC Hierarchical Agglomerative Clustering (HAC) with gaussian models

    The algorithm is based upon a hierarchical agglomerative clustering. The
    initial set of clusters is composed of one segment per cluster. Each cluster
    is modeled by a Gaussian with a full covariance matrix (see
    :class:`gauss.GaussFull`). :math:`\Delta BIC`
    measure is employed to select the candidate clusters to group as well as
    to stop the merging process. The two closest clusters :math:`i` and
    :math:`j` are merged at each iteration until :math:`\\Delta BIC_{i,j} > 0`.


        :math:`\\Delta BIC_{i,j} = PBIC_{i+j} - PBIC_{i} - PBIC_{j} - P`

        :math:`PBIC_{x}  = \\frac{n_x}{2} \\log|\\Sigma_x|`

        :math:`cst  = \\frac{1}{2} \\alpha \\left(d + \\frac{d(d+1)}{2}\\right)`

        :math:`P  = cst + log(n_i+n_j)`

    where :math:`|\\Sigma_i|`, :math:`|\\Sigma_j|` and :math:`|\\Sigma|` are the
    determinants of gaussians associated to the clusters :math:`i`, :math:`j`
    and :math:`i+j`. :math:`\\alpha` is a parameter to set up. The penalty
    factor :math:`P` depends on :math:`d`, the dimension of the features, as well as
    on :math:`n_i` and :math:`n_j`, refering to the total length of cluster
    :math:`i` and cluster :math:`j` respectively.


    """
Sylvain Meignier's avatar
merge    
Sylvain Meignier committed
67
68
    def __init__(self, cep, table, alpha=1.0, sr=False):
        self.cep = cep
Anthony Larcher's avatar
Anthony Larcher committed
69
        self.dim = cep.shape[1]
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
70
71
72
73
74
75
        self.alpha = alpha
        self.diar = copy.deepcopy(table)
        self.models = []
        self.merge = []
        self.nb_merge = 0
        self.sr = sr
Sylvain Meignier's avatar
Sylvain Meignier committed
76
        self.dist = None
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
77
78
79
80
81
82
83
84
        self._init_train()
        self._init_distance()

    def _init_train(self):
        """
        Train initial models

        """
85
86
87
        map = self.diar.make_index(['cluster'])
        for cluster in map:
            model = GaussFull(cluster, self.dim)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
88
            self.models.append(model)
Sylvain Meignier's avatar
merge    
Sylvain Meignier committed
89
            self.cst_bic = GaussFull.cst_bic(self.dim, self.alpha)
90
            for row in map[cluster]:
Sylvain Meignier's avatar
merge    
Sylvain Meignier committed
91
92
93
                start = row['start']
                stop = row['stop']
                model.add(self.cep[start:stop])
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
94
95
96
97
98
99
100
101
102
103
104
105

        for model in self.models:
            model.compute()

    def _init_distance(self):
        """ Compute distance matrix
        """
        nb = len(self.models)
        self.dist = np.full((nb, nb), np.nan)
        # for i in range(0, nb):
        #    mi = self.models[i]
        for i, mi in enumerate(self.models):
Sylvain Meignier's avatar
Sylvain Meignier committed
106
            # self.merge.append([])
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
107
108
109
110
111
            # for j, mj in enumerate(self.models, start=i+1):
            #    logging.debug('i %d j %d n %d', i, j ,nb)
            for j in range(i + 1, nb):
                mj = self.models[j]
                self.dist[i, j] = self.dist[j, i] = self._dist(mi, mj)
Anthony Larcher's avatar
Anthony Larcher committed
112
        # logging.debug(self.dist)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
113
114
115
116
117
118
119
120

    def _dist(self, mi, mj):
        """
        Compute the BIC distance d(i,j)
        :param mi: a GaussFull object
        :param mj: a GaussFull object
        :return: float
        """
Sylvain Meignier's avatar
??    
Sylvain Meignier committed
121
        v = GaussFull.merge_partial_bic(mi, mj) - mi.partial_bic - mj.partial_bic
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
122
        if self.sr:
Sylvain Meignier's avatar
??    
Sylvain Meignier committed
123
            v += - bic_square_root(mi.count, mj.count, self.alpha, self.dim)
Anthony Larcher's avatar
Anthony Larcher committed
124
        else:
Sylvain Meignier's avatar
??    
Sylvain Meignier committed
125
126
127
128
            v += - self.cst_bic * np.log(mi.count + mj.count)
        if isnan(v):
            logging.warning('BIC is NAN, mi: '+mi.name+' ' + str(mi.count)+' mj: '+mj.name+' ' + str(mj.count))
        return v
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

    def _merge_model(self, mi, mj):
        """
        Merge two a GaussFull objects
        :param mi: a GaussFull object
        :param mj: a GaussFull object
        :return: a GaussFull object
        """
        return GaussFull.merge(mi, mj)

    def _update_dist(self, i):
        """
        Update row and column i of the distance matrix
        :param i: int

        """
        nb = len(self.models)
        mi = self.models[i]
        for j in (x for x in range(nb) if x != i):
            mj = self.models[j]
            self.dist[i, j] = self.dist[j, i] = self._dist(mi, mj)

Sylvain Meignier's avatar
??    
Sylvain Meignier committed
151
152
    def information(self, i, j, value, duration):
        self.merge.append([self.nb_merge, self.models[i].name, self.models[j].name, value, duration])
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
153
154
155
156

    def perform(self, to_the_end=False):
        """
        perform the HAC algorithm
157
        :return: a Diar object and a dictonary mapping the old cluster_list to the
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
158
159
160
161
162
        new lables
        """
        nb = len(self.models)
        self.nb_merge = -1
        for i in range(nb):
Sylvain Meignier's avatar
??    
Sylvain Meignier committed
163
            self.information(i, i, 0, self.models[i].count)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
164
165
166
167

        i, j, v = argmin(self.dist, nb)
        self.nb_merge = 0
        while v < 0.0 and nb > 1:
Sylvain Meignier's avatar
??    
Sylvain Meignier committed
168
            self.information(i, j, v, self.models[i].count+self.models[j].count)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
169
170
171
172
173
            self.nb_merge += 1
            logging.debug('merge: %d c1: %s (%d) c2: %s (%d) dist: %f %d',
                          self.nb_merge, self.models[i].name, i,
                          self.models[j].name, j, v, nb)
            # update merge
Sylvain Meignier's avatar
Sylvain Meignier committed
174
            # self.merge[i].append(
Sylvain Meignier's avatar
Sylvain Meignier committed
175
            #    [self.nb_merge, self.models[i].speaker, self.models[j].speaker, v])
Sylvain Meignier's avatar
Sylvain Meignier committed
176
177
            # self.merge[i] += self.merge[j]
            # self.merge.pop(j)
178
            self.diar.rename('cluster', [self.models[j].name], self.models[i].name)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
179
180
181
            # update model
            self.models[i] = self._merge_model(self.models[i], self.models[j])
            self.models.pop(j)
Sylvain Meignier's avatar
Sylvain Meignier committed
182
            # nb = len(self.models)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
183
184
185
186
187
188
189
190
191
192
            # update distances
            self.dist = roll(self.dist, j)
            self._update_dist(i)
            nb -= 1
            i, j, v = argmin(self.dist, nb)

        out_diar = copy.deepcopy(self.diar)

        if to_the_end:
            while nb > 1:
Sylvain Meignier's avatar
??    
Sylvain Meignier committed
193
                self.information(i, j, v, self.models[i].count+self.models[j].count)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
194
195
                self.nb_merge += 1
                logging.debug('merge: %d c1: %s (%d) c2: %s (%d) dist: %f %d',
Anthony Larcher's avatar
Anthony Larcher committed
196
197
                              self.nb_merge, self.models[i].name, i,
                              self.models[j].name, j, v, nb)
198
                self.diar.rename('cluster', [self.models[j].name], self.models[i].name)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
199
200
201
                # update model
                self.models[i] = self._merge_model(self.models[i], self.models[j])
                self.models.pop(j)
Sylvain Meignier's avatar
Sylvain Meignier committed
202
                # nb = len(self.models)
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
203
204
205
206
207
208
                # update distances
                self.dist = roll(self.dist, j)
                self._update_dist(i)
                nb -= 1
                i, j, v = argmin(self.dist, nb)

Sylvain Meignier's avatar
merge    
Sylvain Meignier committed
209
        return out_diar
Sylvain Meignier's avatar
Origin  
Sylvain Meignier committed
210

Sylvain Meignier's avatar
Sylvain Meignier committed
211

Sylvain Meignier's avatar
merge    
Sylvain Meignier committed
212
def hac_bic(feature_server, diar, threshold, square_root_bic = False):
Anthony Larcher's avatar
Anthony Larcher committed
213
214
215
216
217
218
219
220
    """

    :param feature_server:
    :param diar:
    :param threshold:
    :param square_root_bic:
    :return:
    """
Sylvain Meignier's avatar
Sylvain Meignier committed
221
222
223
224
    shows = diar.make_index(['show'])
    diar_out = Diar()
    for show in shows:
        cep, _ = feature_server.load(show)
Sylvain Meignier's avatar
stable    
Sylvain Meignier committed
225
        bic = HAC_BIC(cep, shows[show], alpha=threshold, sr=square_root_bic)
Sylvain Meignier's avatar
Sylvain Meignier committed
226
227
        diar_out += bic.perform(to_the_end=True)
    return diar_out