def k_modes(X, n_clusters, init, n_init, max_iter, verbose):
    """k-modes algorithm"""

    if sparse.issparse(X):
        raise TypeError("k-modes does not support sparse data.")

    X = check_array(X, dtype=None)

    # Convert the categorical values in X to integers for speed.
    # Based on the unique values in X, we can make a mapping to achieve this.
    X, enc_map = encode_features(X)

    npoints, nattrs = X.shape
    assert n_clusters < npoints, "More clusters than data points?"

    all_centroids = []
    all_labels = []
    all_costs = []
    all_n_iters = []
    for init_no in range(n_init):

        # _____ INIT _____
        if verbose:
            print("Init: initializing centroids")
        if isinstance(init, str) and init == 'Huang':
            centroids = init_huang(X, n_clusters)
        elif isinstance(init, str) and init == 'Cao':
            centroids = init_cao(X, n_clusters)
        elif isinstance(init, str) and init == 'random':
            seeds = np.random.choice(range(npoints), n_clusters)
            centroids = X[seeds]
        elif hasattr(init, '__array__'):
            assert init.shape[0] == n_clusters, "Too many initial centroids in init."
            assert init.shape[1] == nattrs, "Too many attributes in init for X."
            centroids = np.asarray(init, dtype=np.uint8)
        else:
            raise NotImplementedError

        if verbose:
            print("Init: initializing clusters")
        membship = np.zeros((n_clusters, npoints), dtype=np.uint8)
        # cl_attr_freq is a list of lists with dictionaries that contain the
        # frequencies of values per cluster and attribute.
        cl_attr_freq = [[defaultdict(int) for _ in range(nattrs)]
                        for _ in range(n_clusters)]
        for ipoint, curpoint in enumerate(X):
            # Initial assignment to clusters
            clust = np.argmin(matching_dissim(centroids, curpoint))
            membship[clust, ipoint] = 1
            # Count attribute values per cluster.
            for iattr, curattr in enumerate(curpoint):
                cl_attr_freq[clust][iattr][curattr] += 1
        # Perform an initial centroid update.
        for ik in range(n_clusters):
            for iattr in range(nattrs):
                if sum(membship[ik]) == 0:
                    # Empty centroid, choose randomly
                    centroids[ik, iattr] = np.random.choice(X[:, iattr])
                else:
                    centroids[ik, iattr] = get_max_value_key(cl_attr_freq[ik][iattr])

        # _____ ITERATION _____
        if verbose:
            print("Starting iterations...")
        itr = 0
        converged = False
        cost = np.Inf
        while itr <= max_iter and not converged:
            itr += 1
            centroids, moves = _k_modes_iter(X, centroids, cl_attr_freq, membship)
            # All points seen in this iteration
            labels, ncost = _labels_cost(X, centroids)
            converged = (moves == 0) or (ncost >= cost)
            cost = ncost
            if verbose:
                print("Run {}, iteration: {}/{}, moves: {}, cost: {}"
                      .format(init_no + 1, itr, max_iter, moves, cost))

        # Store result of current run.
        all_centroids.append(centroids)
        all_labels.append(labels)
        all_costs.append(cost)
        all_n_iters.append(itr)

    best = np.argmin(all_costs)
    if n_init > 1 and verbose:
        print("Best run was number {}".format(best + 1))

    return all_centroids[best], all_labels[best], all_costs[best], \
        all_n_iters[best], enc_map
dataset/ETHPy150Open nicodv/kmodes/kmodes/kmodes.py/k_modes/original