Projet de classification de conformations de protéines par k-medoids

doc_kmedoids.py 12KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328
  1. """!
  2. @brief Cluster analysis algorithm: K-Medoids.
  3. @details Implementation based on papers @cite book::algorithms_for_clustering_data, @cite book::finding_groups_in_data.
  4. @authors Andrei Novikov (pyclustering@yandex.ru)
  5. @date 2014-2019
  6. @copyright GNU Public License
  7. @cond GNU_PUBLIC_LICENSE
  8. PyClustering is free software: you can redistribute it and/or modify
  9. it under the terms of the GNU General Public License as published by
  10. the Free Software Foundation, either version 3 of the License, or
  11. (at your option) any later version.
  12. PyClustering is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15. GNU General Public License for more details.
  16. You should have received a copy of the GNU General Public License
  17. along with this program. If not, see <http://www.gnu.org/licenses/>.
  18. @endcond
  19. """
  20. import numpy
  21. from pyclustering.cluster.encoder import type_encoding
  22. from pyclustering.utils import medoid
  23. from pyclustering.utils.metric import distance_metric, type_metric
  24. import pyclustering.core.kmedoids_wrapper as wrapper
  25. from pyclustering.core.wrapper import ccore_library
  26. from pyclustering.core.metric_wrapper import metric_wrapper
  27. class kmedoids:
  28. """!
  29. @brief Class represents clustering algorithm K-Medoids.
  30. @details The algorithm is less sensitive to outliers tham K-Means. The principle difference between K-Medoids and K-Medians is that
  31. K-Medoids uses existed points from input data space as medoids, but median in K-Medians can be unreal object (not from
  32. input data space).
  33. Clustering example:
  34. @code
  35. from pyclustering.cluster.kmedoids import kmedoids
  36. from pyclustering.cluster import cluster_visualizer
  37. from pyclustering.utils import read_sample
  38. from pyclustering.samples.definitions import FCPS_SAMPLES
  39. # Load list of points for cluster analysis.
  40. sample = read_sample(FCPS_SAMPLES.SAMPLE_TWO_DIAMONDS)
  41. # Set random initial medoids.
  42. initial_medoids = [1, 500]
  43. # Create instance of K-Medoids algorithm.
  44. kmedoids_instance = kmedoids(sample, initial_medoids)
  45. # Run cluster analysis and obtain results.
  46. kmedoids_instance.process()
  47. clusters = kmedoids_instance.get_clusters()
  48. # Show allocated clusters.
  49. print(clusters)
  50. # Display clusters.
  51. visualizer = cluster_visualizer()
  52. visualizer.append_clusters(clusters, sample)
  53. visualizer.show()
  54. @endcode
  55. Metric for calculation distance between points can be specified by parameter additional 'metric':
  56. @code
  57. # create Minkowski distance metric with degree equals to '2'
  58. metric = distance_metric(type_metric.MINKOWSKI, degree=2)
  59. # create K-Medoids algorithm with specific distance metric
  60. kmedoids_instance = kmedoids(sample, initial_medoids, metric=metric)
  61. # run cluster analysis and obtain results
  62. kmedoids_instance.process()
  63. clusters = kmedoids_instance.get_clusters()
  64. @endcode
  65. Distance matrix can be used instead of sequence of points to increase performance and for that purpose parameter 'data_type' should be used:
  66. @code
  67. # calculate distance matrix for sample
  68. sample = read_sample(path_to_sample)
  69. matrix = calculate_distance_matrix(sample)
  70. # create K-Medoids algorithm for processing distance matrix instead of points
  71. kmedoids_instance = kmedoids(matrix, initial_medoids, data_type='distance_matrix')
  72. # run cluster analysis and obtain results
  73. kmedoids_instance.process()
  74. clusters = kmedoids_instance.get_clusters()
  75. medoids = kmedoids_instance.get_medoids()
  76. @endcode
  77. """
  78. def __init__(self, data, initial_index_medoids, tolerance=0.001, ccore=True, **kwargs):
  79. """!
  80. @brief Constructor of clustering algorithm K-Medoids.
  81. @param[in] data (list): Input data that is presented as list of points (objects), each point should be represented by list or tuple.
  82. @param[in] initial_index_medoids (list): Indexes of intial medoids (indexes of points in input data).
  83. @param[in] tolerance (double): Stop condition: if maximum value of distance change of medoids of clusters is less than tolerance than algorithm will stop processing.
  84. @param[in] ccore (bool): If specified than CCORE library (C++ pyclustering library) is used for clustering instead of Python code.
  85. @param[in] **kwargs: Arbitrary keyword arguments (available arguments: 'metric', 'data_type', 'itermax').
  86. <b>Keyword Args:</b><br>
  87. - metric (distance_metric): Metric that is used for distance calculation between two points.
  88. - data_type (string): Data type of input sample 'data' that is processed by the algorithm ('points', 'distance_matrix').
  89. - itermax (uint): Maximum number of iteration for cluster analysis.
  90. """
  91. self.__pointer_data = data
  92. self.__clusters = []
  93. self.__medoid_indexes = initial_index_medoids
  94. self.__tolerance = tolerance
  95. self.__metric = kwargs.get('metric', distance_metric(type_metric.EUCLIDEAN_SQUARE))
  96. self.__data_type = kwargs.get('data_type', 'points')
  97. self.__itermax = kwargs.get('itermax', 200)
  98. self.__distance_calculator = self.__create_distance_calculator()
  99. self.__ccore = ccore and self.__metric.get_type() != type_metric.USER_DEFINED
  100. if self.__ccore:
  101. self.__ccore = ccore_library.workable()
  102. #self.__verify_instance()
  103. def process(self):
  104. """!
  105. @brief Performs cluster analysis in line with rules of K-Medoids algorithm.
  106. @return (kmedoids) Returns itself (K-Medoids instance).
  107. @remark Results of clustering can be obtained using corresponding get methods.
  108. @see get_clusters()
  109. @see get_medoids()
  110. """
  111. if self.__ccore is True:
  112. ccore_metric = metric_wrapper.create_instance(self.__metric)
  113. self.__clusters, self.__medoid_indexes = wrapper.kmedoids(self.__pointer_data, self.__medoid_indexes, self.__tolerance, self.__itermax, ccore_metric.get_pointer(), self.__data_type)
  114. else:
  115. changes = float('inf')
  116. iterations = 0
  117. while changes > self.__tolerance and iterations < self.__itermax:
  118. self.__clusters = self.__update_clusters()
  119. update_medoid_indexes = self.__update_medoids()
  120. changes = max([self.__distance_calculator(self.__medoid_indexes[index], update_medoid_indexes[index]) for index in range(len(update_medoid_indexes))])
  121. self.__medoid_indexes = update_medoid_indexes
  122. iterations += 1
  123. return self
  124. def predict(self, points):
  125. """!
  126. @brief Calculates the closest cluster to each point.
  127. @param[in] points (array_like): Points for which closest clusters are calculated.
  128. @return (list) List of closest clusters for each point. Each cluster is denoted by index. Return empty
  129. collection if 'process()' method was not called.
  130. An example how to calculate (or predict) the closest cluster to specified points.
  131. @code
  132. from pyclustering.cluster.kmedoids import kmedoids
  133. from pyclustering.samples.definitions import SIMPLE_SAMPLES
  134. from pyclustering.utils import read_sample
  135. # Load list of points for cluster analysis.
  136. sample = read_sample(SIMPLE_SAMPLES.SAMPLE_SIMPLE3)
  137. # Initial medoids for sample 'Simple3'.
  138. initial_medoids = [4, 12, 25, 37]
  139. # Create instance of K-Medoids algorithm with prepared centers.
  140. kmedoids_instance = kmedoids(sample, initial_medoids)
  141. # Run cluster analysis.
  142. kmedoids_instance.process()
  143. # Calculate the closest cluster to following two points.
  144. points = [[0.35, 0.5], [2.5, 2.0]]
  145. closest_clusters = kmedoids_instance.predict(points)
  146. print(closest_clusters)
  147. @endcode
  148. """
  149. if len(self.__clusters) == 0:
  150. return []
  151. medoids = [ self.__pointer_data[index] for index in self.__medoid_indexes ]
  152. differences = numpy.zeros((len(points), len(medoids)))
  153. for index_point in range(len(points)):
  154. differences[index_point] = [ self.__metric(points[index_point], center) for center in medoids ]
  155. return numpy.argmin(differences, axis=1)
  156. def get_clusters(self):
  157. """!
  158. @brief Returns list of allocated clusters, each cluster contains indexes of objects in list of data.
  159. @see process()
  160. @see get_medoids()
  161. """
  162. return self.__clusters
  163. def get_medoids(self):
  164. """!
  165. @brief Returns list of medoids of allocated clusters represented by indexes from the input data.
  166. @see process()
  167. @see get_clusters()
  168. """
  169. return self.__medoid_indexes
  170. def get_cluster_encoding(self):
  171. """!
  172. @brief Returns clustering result representation type that indicate how clusters are encoded.
  173. @return (type_encoding) Clustering result representation.
  174. @see get_clusters()
  175. """
  176. return type_encoding.CLUSTER_INDEX_LIST_SEPARATION
  177. def __verify_instance(self):
  178. pass
  179. def __create_distance_calculator(self):
  180. """!
  181. @brief Creates distance calculator in line with algorithms parameters.
  182. @return (callable) Distance calculator.
  183. """
  184. if self.__data_type == 'points':
  185. return lambda index1, index2: self.__metric(self.__pointer_data[index1], self.__pointer_data[index2])
  186. elif self.__data_type == 'distance_matrix':
  187. if isinstance(self.__pointer_data, numpy.matrix):
  188. return lambda index1, index2: self.__pointer_data.item((index1, index2))
  189. return lambda index1, index2: self.__pointer_data[index1][index2]
  190. else:
  191. raise TypeError("Unknown type of data is specified '%s'" % self.__data_type)
  192. def __update_clusters(self):
  193. """!
  194. @brief Calculate distance to each point from the each cluster.
  195. @details Nearest points are captured by according clusters and as a result clusters are updated.
  196. @return (list) updated clusters as list of clusters where each cluster contains indexes of objects from data.
  197. """
  198. clusters = [[self.__medoid_indexes[i]] for i in range(len(self.__medoid_indexes))]
  199. for index_point in range(len(self.__pointer_data)):
  200. if index_point in self.__medoid_indexes:
  201. continue
  202. index_optim = -1
  203. dist_optim = float('Inf')
  204. for index in range(len(self.__medoid_indexes)):
  205. dist = self.__distance_calculator(index_point, self.__medoid_indexes[index])
  206. if dist < dist_optim:
  207. index_optim = index
  208. dist_optim = dist
  209. clusters[index_optim].append(index_point)
  210. return clusters
  211. def __update_medoids(self):
  212. """!
  213. @brief Find medoids of clusters in line with contained objects.
  214. @return (list) list of medoids for current number of clusters.
  215. """
  216. medoid_indexes = [-1] * len(self.__clusters)
  217. for index in range(len(self.__clusters)):
  218. medoid_index = medoid(self.__pointer_data, self.__clusters[index], metric=self.__metric, data_type=self.__data_type)
  219. medoid_indexes[index] = medoid_index
  220. return medoid_indexes