We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
DBSCAN changes instance ids
The output of DBSCAN looses traceability of data instances. The following workflow should explain the problem:

![image](https://user-images.githubusercontent.com/726604/117261710-c1626580-ae50-11eb-89b7-ff92dd6576a2.png)

t-SNE should mark all data instances, as the data subset is the same as the data, but instead reports that "No subset data instances appear in input data". 

![image](https://user-images.githubusercontent.com/726604/117261871-eeaf1380-ae50-11eb-8cba-267dfede1551.png)

Similar is of course true with any selection of the data that comes from DBSCAN. My original intention was to send the DBSCAN data to the boxplot and then show the selection from the box plot, sat, the clusters with interesting class-distribution, as a data subset to the t-SNE. But then I get, of course, the same warning in t-SNE, reporting the mismatch of the data subset and data provided to this widget.

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `Orange/widgets/unsupervised/owdbscan.py`
Content:
```
1 import sys
2 from itertools import chain
3 
4 import numpy as np
5 from AnyQt.QtWidgets import QApplication
6 from AnyQt.QtGui import QColor
7 from sklearn.metrics import pairwise_distances
8 
9 from Orange.preprocess import Normalize, Continuize, SklImpute
10 from Orange.widgets import widget, gui
11 from Orange.widgets.utils.slidergraph import SliderGraph
12 from Orange.widgets.settings import Setting
13 from Orange.data import Table, Domain, DiscreteVariable
14 from Orange.data.util import get_unique_names
15 from Orange.clustering import DBSCAN
16 from Orange.widgets.utils.annotated_data import ANNOTATED_DATA_SIGNAL_NAME
17 from Orange.widgets.utils.signals import Input, Output
18 from Orange.widgets.utils.state_summary import format_summary_details
19 from Orange.widgets.widget import Msg
20 
21 
22 DEFAULT_CUT_POINT = 0.1
23 PREPROCESSORS = [Continuize(), Normalize(), SklImpute()]
24 EPS_BOTTOM_LIMIT = 0.01
25 
26 
27 def get_kth_distances(data, metric, k=5):
28     """
29     The function computes the epsilon parameter for DBSCAN through method
30     proposed in the paper.
31     Parameters
32     ----------
33     data : Orange.data.Table
34         Visualisation coordinates - embeddings
35     metric : callable or str
36         The metric to compute the distance.
37     k : int
38         Number kth observed neighbour
39 
40     Returns
41     -------
42     np.ndarray
43         Epsilon parameter for DBSCAN
44     """
45     x = data.X
46     if x.shape[0] > 1000:  # subsample
47         x = x[np.random.randint(x.shape[0], size=1000), :]
48 
49     dist = pairwise_distances(x, metric=metric)
50     k = min(k+1, len(data) - 1)  # k+1 since first one is item itself
51     kth_point = np.argpartition(dist, k, axis=1)[:, k]
52     kth_dist = np.sort(dist[np.arange(0, len(kth_point)), kth_point])[::-1]
53 
54     return kth_dist
55 
56 
57 class OWDBSCAN(widget.OWWidget):
58     name = "DBSCAN"
59     description = "Density-based spatial clustering."
60     icon = "icons/DBSCAN.svg"
61     priority = 2150
62 
63     class Inputs:
64         data = Input("Data", Table)
65 
66     class Outputs:
67         annotated_data = Output(ANNOTATED_DATA_SIGNAL_NAME, Table)
68 
69     class Error(widget.OWWidget.Error):
70         not_enough_instances = Msg("Not enough unique data instances. "
71                                    "At least two are required.")
72 
73     METRICS = [
74         ("Euclidean", "euclidean"),
75         ("Manhattan", "cityblock"),
76         ("Cosine", "cosine")
77     ]
78 
79     min_samples = Setting(4)
80     eps = Setting(0.5)
81     metric_idx = Setting(0)
82     auto_commit = Setting(True)
83     k_distances = None
84     cut_point = None
85 
86     def __init__(self):
87         super().__init__()
88 
89         self.data = None
90         self.data_normalized = None
91         self.db = None
92         self.model = None
93         self._set_input_summary(None)
94         self._set_output_summary(None)
95 
96         box = gui.widgetBox(self.controlArea, "Parameters")
97         gui.spin(box, self, "min_samples", 1, 100, 1,
98                  callback=self._min_samples_changed,
99                  label="Core point neighbors")
100         gui.doubleSpin(box, self, "eps", EPS_BOTTOM_LIMIT, 1000, 0.01,
101                        callback=self._eps_changed,
102                        label="Neighborhood distance")
103 
104         box = gui.widgetBox(self.controlArea, self.tr("Distance Metric"))
105         gui.comboBox(box, self, "metric_idx",
106                      items=list(zip(*self.METRICS))[0],
107                      callback=self._metirc_changed)
108 
109         gui.auto_apply(self.buttonsArea, self, "auto_commit")
110         gui.rubber(self.controlArea)
111 
112         self.controlArea.layout().addStretch()
113 
114         self.plot = SliderGraph(
115             x_axis_label="Data items sorted by score",
116             y_axis_label="Distance to the k-th nearest neighbour",
117             callback=self._on_cut_changed
118         )
119 
120         self.mainArea.layout().addWidget(self.plot)
121 
122     def check_data_size(self, data):
123         if data is None:
124             return False
125         if len(data) < 2:
126             self.Error.not_enough_instances()
127             return False
128         return True
129 
130     def commit(self):
131         self.cluster()
132 
133     def cluster(self):
134         if not self.check_data_size(self.data):
135             return
136         self.model = DBSCAN(
137             eps=self.eps,
138             min_samples=self.min_samples,
139             metric=self.METRICS[self.metric_idx][1]
140         ).get_model(self.data_normalized)
141         self.send_data()
142 
143     def _compute_and_plot(self, cut_point=None):
144         self._compute_kdistances()
145         if cut_point is None:
146             self._compute_cut_point()
147         self._plot_graph()
148 
149     def _plot_graph(self):
150         nonzero = np.sum(self.k_distances > EPS_BOTTOM_LIMIT)
151         self.plot.update(np.arange(len(self.k_distances)),
152                          [self.k_distances],
153                          colors=[QColor('red')],
154                          cutpoint_x=self.cut_point,
155                          selection_limit=(0, nonzero - 1))
156 
157     def _compute_kdistances(self):
158         self.k_distances = get_kth_distances(
159             self.data_normalized, metric=self.METRICS[self.metric_idx][1],
160             k=self.min_samples
161         )
162 
163     def _compute_cut_point(self):
164         self.cut_point = int(DEFAULT_CUT_POINT * len(self.k_distances))
165         self.eps = self.k_distances[self.cut_point]
166 
167         if self.eps < EPS_BOTTOM_LIMIT:
168             self.eps = np.min(
169                 self.k_distances[self.k_distances >= EPS_BOTTOM_LIMIT])
170             self.cut_point = self._find_nearest_dist(self.eps)
171 
172     @Inputs.data
173     def set_data(self, data):
174         self.Error.clear()
175         self._set_input_summary(data)
176         if not self.check_data_size(data):
177             data = None
178         self.data = self.data_normalized = data
179         if self.data is None:
180             self._set_output_summary(None)
181             self.Outputs.annotated_data.send(None)
182             self.plot.clear_plot()
183             return
184 
185         if self.data is None:
186             return
187 
188         # preprocess data
189         for pp in PREPROCESSORS:
190             self.data_normalized = pp(self.data_normalized)
191 
192         self._compute_and_plot()
193         self.unconditional_commit()
194 
195     def send_data(self):
196         model = self.model
197 
198         clusters = [c if c >= 0 else np.nan for c in model.labels]
199         k = len(set(clusters) - {np.nan})
200         clusters = np.array(clusters).reshape(len(self.data), 1)
201         core_samples = set(model.projector.core_sample_indices_)
202         in_core = np.array([1 if (i in core_samples) else 0
203                             for i in range(len(self.data))])
204         in_core = in_core.reshape(len(self.data), 1)
205 
206         domain = self.data.domain
207         attributes, classes = domain.attributes, domain.class_vars
208         meta_attrs = domain.metas
209         names = [var.name for var in chain(attributes, classes, meta_attrs) if var]
210 
211         u_clust_var = get_unique_names(names, "Cluster")
212         clust_var = DiscreteVariable(
213             u_clust_var, values=["C%d" % (x + 1) for x in range(k)])
214 
215         u_in_core = get_unique_names(names + [u_clust_var], "DBSCAN Core")
216         in_core_var = DiscreteVariable(u_in_core, values=("0", "1"))
217 
218         x, y, metas = self.data.X, self.data.Y, self.data.metas
219 
220         meta_attrs += (clust_var, )
221         metas = np.hstack((metas, clusters))
222         meta_attrs += (in_core_var, )
223         metas = np.hstack((metas, in_core))
224 
225         domain = Domain(attributes, classes, meta_attrs)
226         new_table = Table(domain, x, y, metas, self.data.W)
227 
228         self._set_output_summary(new_table)
229         self.Outputs.annotated_data.send(new_table)
230 
231     def _set_input_summary(self, data):
232         summary = len(data) if data else self.info.NoInput
233         details = format_summary_details(data) if data else ""
234         self.info.set_input_summary(summary, details)
235 
236     def _set_output_summary(self, output):
237         summary = len(output) if output else self.info.NoOutput
238         details = format_summary_details(output) if output else ""
239         self.info.set_output_summary(summary, details)
240 
241     def _invalidate(self):
242         self.commit()
243 
244     def _find_nearest_dist(self, value):
245         array = np.asarray(self.k_distances)
246         idx = (np.abs(array - value)).argmin()
247         return idx
248 
249     def _eps_changed(self):
250         # find the closest value to eps
251         if self.data is None:
252             return
253         self.cut_point = self._find_nearest_dist(self.eps)
254         self.plot.set_cut_point(self.cut_point)
255         self._invalidate()
256 
257     def _metirc_changed(self):
258         if self.data is not None:
259             self._compute_and_plot()
260             self._invalidate()
261 
262     def _on_cut_changed(self, value):
263         # cut changed by means of a cut line over the scree plot.
264         self.cut_point = value
265         self.eps = self.k_distances[value]
266 
267         self.commit()
268 
269     def _min_samples_changed(self):
270         if self.data is None:
271             return
272         self._compute_and_plot(cut_point=self.cut_point)
273         self._invalidate()
274 
275 
276 if __name__ == "__main__":
277     a = QApplication(sys.argv)
278     ow = OWDBSCAN()
279     d = Table("iris.tab")
280     ow.set_data(d)
281     ow.show()
282     a.exec()
283     ow.saveSettings()
284
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/Orange/widgets/unsupervised/owdbscan.py b/Orange/widgets/unsupervised/owdbscan.py
--- a/Orange/widgets/unsupervised/owdbscan.py
+++ b/Orange/widgets/unsupervised/owdbscan.py
@@ -10,7 +10,7 @@
 from Orange.widgets import widget, gui
 from Orange.widgets.utils.slidergraph import SliderGraph
 from Orange.widgets.settings import Setting
-from Orange.data import Table, Domain, DiscreteVariable
+from Orange.data import Table, DiscreteVariable
 from Orange.data.util import get_unique_names
 from Orange.clustering import DBSCAN
 from Orange.widgets.utils.annotated_data import ANNOTATED_DATA_SIGNAL_NAME
@@ -197,11 +197,10 @@
 
         clusters = [c if c >= 0 else np.nan for c in model.labels]
         k = len(set(clusters) - {np.nan})
-        clusters = np.array(clusters).reshape(len(self.data), 1)
+        clusters = np.array(clusters)
         core_samples = set(model.projector.core_sample_indices_)
         in_core = np.array([1 if (i in core_samples) else 0
                             for i in range(len(self.data))])
-        in_core = in_core.reshape(len(self.data), 1)
 
         domain = self.data.domain
         attributes, classes = domain.attributes, domain.class_vars
@@ -215,15 +214,8 @@
         u_in_core = get_unique_names(names + [u_clust_var], "DBSCAN Core")
         in_core_var = DiscreteVariable(u_in_core, values=("0", "1"))
 
-        x, y, metas = self.data.X, self.data.Y, self.data.metas
-
-        meta_attrs += (clust_var, )
-        metas = np.hstack((metas, clusters))
-        meta_attrs += (in_core_var, )
-        metas = np.hstack((metas, in_core))
-
-        domain = Domain(attributes, classes, meta_attrs)
-        new_table = Table(domain, x, y, metas, self.data.W)
+        new_table = self.data.add_column(clust_var, clusters, to_metas=True)
+        new_table = new_table.add_column(in_core_var, in_core, to_metas=True)
 
         self._set_output_summary(new_table)
         self.Outputs.annotated_data.send(new_table)

{"golden_diff": "diff --git a/Orange/widgets/unsupervised/owdbscan.py b/Orange/widgets/unsupervised/owdbscan.py\n--- a/Orange/widgets/unsupervised/owdbscan.py\n+++ b/Orange/widgets/unsupervised/owdbscan.py\n@@ -10,7 +10,7 @@\n from Orange.widgets import widget, gui\n from Orange.widgets.utils.slidergraph import SliderGraph\n from Orange.widgets.settings import Setting\n-from Orange.data import Table, Domain, DiscreteVariable\n+from Orange.data import Table, DiscreteVariable\n from Orange.data.util import get_unique_names\n from Orange.clustering import DBSCAN\n from Orange.widgets.utils.annotated_data import ANNOTATED_DATA_SIGNAL_NAME\n@@ -197,11 +197,10 @@\n \n         clusters = [c if c >= 0 else np.nan for c in model.labels]\n         k = len(set(clusters) - {np.nan})\n-        clusters = np.array(clusters).reshape(len(self.data), 1)\n+        clusters = np.array(clusters)\n         core_samples = set(model.projector.core_sample_indices_)\n         in_core = np.array([1 if (i in core_samples) else 0\n                             for i in range(len(self.data))])\n-        in_core = in_core.reshape(len(self.data), 1)\n \n         domain = self.data.domain\n         attributes, classes = domain.attributes, domain.class_vars\n@@ -215,15 +214,8 @@\n         u_in_core = get_unique_names(names + [u_clust_var], \"DBSCAN Core\")\n         in_core_var = DiscreteVariable(u_in_core, values=(\"0\", \"1\"))\n \n-        x, y, metas = self.data.X, self.data.Y, self.data.metas\n-\n-        meta_attrs += (clust_var, )\n-        metas = np.hstack((metas, clusters))\n-        meta_attrs += (in_core_var, )\n-        metas = np.hstack((metas, in_core))\n-\n-        domain = Domain(attributes, classes, meta_attrs)\n-        new_table = Table(domain, x, y, metas, self.data.W)\n+        new_table = self.data.add_column(clust_var, clusters, to_metas=True)\n+        new_table = new_table.add_column(in_core_var, in_core, to_metas=True)\n \n         self._set_output_summary(new_table)\n         self.Outputs.annotated_data.send(new_table)\n", "issue": "DBSCAN changes instance ids\nThe output of DBSCAN looses traceability of data instances. The following workflow should explain the problem:\r\n\r\n![image](https://user-images.githubusercontent.com/726604/117261710-c1626580-ae50-11eb-89b7-ff92dd6576a2.png)\r\n\r\nt-SNE should mark all data instances, as the data subset is the same as the data, but instead reports that \"No subset data instances appear in input data\". \r\n\r\n![image](https://user-images.githubusercontent.com/726604/117261871-eeaf1380-ae50-11eb-8cba-267dfede1551.png)\r\n\r\nSimilar is of course true with any selection of the data that comes from DBSCAN. My original intention was to send the DBSCAN data to the boxplot and then show the selection from the box plot, sat, the clusters with interesting class-distribution, as a data subset to the t-SNE. But then I get, of course, the same warning in t-SNE, reporting the mismatch of the data subset and data provided to this widget.\n", "before_files": [{"content": "import sys\nfrom itertools import chain\n\nimport numpy as np\nfrom AnyQt.QtWidgets import QApplication\nfrom AnyQt.QtGui import QColor\nfrom sklearn.metrics import pairwise_distances\n\nfrom Orange.preprocess import Normalize, Continuize, SklImpute\nfrom Orange.widgets import widget, gui\nfrom Orange.widgets.utils.slidergraph import SliderGraph\nfrom Orange.widgets.settings import Setting\nfrom Orange.data import Table, Domain, DiscreteVariable\nfrom Orange.data.util import get_unique_names\nfrom Orange.clustering import DBSCAN\nfrom Orange.widgets.utils.annotated_data import ANNOTATED_DATA_SIGNAL_NAME\nfrom Orange.widgets.utils.signals import Input, Output\nfrom Orange.widgets.utils.state_summary import format_summary_details\nfrom Orange.widgets.widget import Msg\n\n\nDEFAULT_CUT_POINT = 0.1\nPREPROCESSORS = [Continuize(), Normalize(), SklImpute()]\nEPS_BOTTOM_LIMIT = 0.01\n\n\ndef get_kth_distances(data, metric, k=5):\n    \"\"\"\n    The function computes the epsilon parameter for DBSCAN through method\n    proposed in the paper.\n    Parameters\n    ----------\n    data : Orange.data.Table\n        Visualisation coordinates - embeddings\n    metric : callable or str\n        The metric to compute the distance.\n    k : int\n        Number kth observed neighbour\n\n    Returns\n    -------\n    np.ndarray\n        Epsilon parameter for DBSCAN\n    \"\"\"\n    x = data.X\n    if x.shape[0] > 1000:  # subsample\n        x = x[np.random.randint(x.shape[0], size=1000), :]\n\n    dist = pairwise_distances(x, metric=metric)\n    k = min(k+1, len(data) - 1)  # k+1 since first one is item itself\n    kth_point = np.argpartition(dist, k, axis=1)[:, k]\n    kth_dist = np.sort(dist[np.arange(0, len(kth_point)), kth_point])[::-1]\n\n    return kth_dist\n\n\nclass OWDBSCAN(widget.OWWidget):\n    name = \"DBSCAN\"\n    description = \"Density-based spatial clustering.\"\n    icon = \"icons/DBSCAN.svg\"\n    priority = 2150\n\n    class Inputs:\n        data = Input(\"Data\", Table)\n\n    class Outputs:\n        annotated_data = Output(ANNOTATED_DATA_SIGNAL_NAME, Table)\n\n    class Error(widget.OWWidget.Error):\n        not_enough_instances = Msg(\"Not enough unique data instances. \"\n                                   \"At least two are required.\")\n\n    METRICS = [\n        (\"Euclidean\", \"euclidean\"),\n        (\"Manhattan\", \"cityblock\"),\n        (\"Cosine\", \"cosine\")\n    ]\n\n    min_samples = Setting(4)\n    eps = Setting(0.5)\n    metric_idx = Setting(0)\n    auto_commit = Setting(True)\n    k_distances = None\n    cut_point = None\n\n    def __init__(self):\n        super().__init__()\n\n        self.data = None\n        self.data_normalized = None\n        self.db = None\n        self.model = None\n        self._set_input_summary(None)\n        self._set_output_summary(None)\n\n        box = gui.widgetBox(self.controlArea, \"Parameters\")\n        gui.spin(box, self, \"min_samples\", 1, 100, 1,\n                 callback=self._min_samples_changed,\n                 label=\"Core point neighbors\")\n        gui.doubleSpin(box, self, \"eps\", EPS_BOTTOM_LIMIT, 1000, 0.01,\n                       callback=self._eps_changed,\n                       label=\"Neighborhood distance\")\n\n        box = gui.widgetBox(self.controlArea, self.tr(\"Distance Metric\"))\n        gui.comboBox(box, self, \"metric_idx\",\n                     items=list(zip(*self.METRICS))[0],\n                     callback=self._metirc_changed)\n\n        gui.auto_apply(self.buttonsArea, self, \"auto_commit\")\n        gui.rubber(self.controlArea)\n\n        self.controlArea.layout().addStretch()\n\n        self.plot = SliderGraph(\n            x_axis_label=\"Data items sorted by score\",\n            y_axis_label=\"Distance to the k-th nearest neighbour\",\n            callback=self._on_cut_changed\n        )\n\n        self.mainArea.layout().addWidget(self.plot)\n\n    def check_data_size(self, data):\n        if data is None:\n            return False\n        if len(data) < 2:\n            self.Error.not_enough_instances()\n            return False\n        return True\n\n    def commit(self):\n        self.cluster()\n\n    def cluster(self):\n        if not self.check_data_size(self.data):\n            return\n        self.model = DBSCAN(\n            eps=self.eps,\n            min_samples=self.min_samples,\n            metric=self.METRICS[self.metric_idx][1]\n        ).get_model(self.data_normalized)\n        self.send_data()\n\n    def _compute_and_plot(self, cut_point=None):\n        self._compute_kdistances()\n        if cut_point is None:\n            self._compute_cut_point()\n        self._plot_graph()\n\n    def _plot_graph(self):\n        nonzero = np.sum(self.k_distances > EPS_BOTTOM_LIMIT)\n        self.plot.update(np.arange(len(self.k_distances)),\n                         [self.k_distances],\n                         colors=[QColor('red')],\n                         cutpoint_x=self.cut_point,\n                         selection_limit=(0, nonzero - 1))\n\n    def _compute_kdistances(self):\n        self.k_distances = get_kth_distances(\n            self.data_normalized, metric=self.METRICS[self.metric_idx][1],\n            k=self.min_samples\n        )\n\n    def _compute_cut_point(self):\n        self.cut_point = int(DEFAULT_CUT_POINT * len(self.k_distances))\n        self.eps = self.k_distances[self.cut_point]\n\n        if self.eps < EPS_BOTTOM_LIMIT:\n            self.eps = np.min(\n                self.k_distances[self.k_distances >= EPS_BOTTOM_LIMIT])\n            self.cut_point = self._find_nearest_dist(self.eps)\n\n    @Inputs.data\n    def set_data(self, data):\n        self.Error.clear()\n        self._set_input_summary(data)\n        if not self.check_data_size(data):\n            data = None\n        self.data = self.data_normalized = data\n        if self.data is None:\n            self._set_output_summary(None)\n            self.Outputs.annotated_data.send(None)\n            self.plot.clear_plot()\n            return\n\n        if self.data is None:\n            return\n\n        # preprocess data\n        for pp in PREPROCESSORS:\n            self.data_normalized = pp(self.data_normalized)\n\n        self._compute_and_plot()\n        self.unconditional_commit()\n\n    def send_data(self):\n        model = self.model\n\n        clusters = [c if c >= 0 else np.nan for c in model.labels]\n        k = len(set(clusters) - {np.nan})\n        clusters = np.array(clusters).reshape(len(self.data), 1)\n        core_samples = set(model.projector.core_sample_indices_)\n        in_core = np.array([1 if (i in core_samples) else 0\n                            for i in range(len(self.data))])\n        in_core = in_core.reshape(len(self.data), 1)\n\n        domain = self.data.domain\n        attributes, classes = domain.attributes, domain.class_vars\n        meta_attrs = domain.metas\n        names = [var.name for var in chain(attributes, classes, meta_attrs) if var]\n\n        u_clust_var = get_unique_names(names, \"Cluster\")\n        clust_var = DiscreteVariable(\n            u_clust_var, values=[\"C%d\" % (x + 1) for x in range(k)])\n\n        u_in_core = get_unique_names(names + [u_clust_var], \"DBSCAN Core\")\n        in_core_var = DiscreteVariable(u_in_core, values=(\"0\", \"1\"))\n\n        x, y, metas = self.data.X, self.data.Y, self.data.metas\n\n        meta_attrs += (clust_var, )\n        metas = np.hstack((metas, clusters))\n        meta_attrs += (in_core_var, )\n        metas = np.hstack((metas, in_core))\n\n        domain = Domain(attributes, classes, meta_attrs)\n        new_table = Table(domain, x, y, metas, self.data.W)\n\n        self._set_output_summary(new_table)\n        self.Outputs.annotated_data.send(new_table)\n\n    def _set_input_summary(self, data):\n        summary = len(data) if data else self.info.NoInput\n        details = format_summary_details(data) if data else \"\"\n        self.info.set_input_summary(summary, details)\n\n    def _set_output_summary(self, output):\n        summary = len(output) if output else self.info.NoOutput\n        details = format_summary_details(output) if output else \"\"\n        self.info.set_output_summary(summary, details)\n\n    def _invalidate(self):\n        self.commit()\n\n    def _find_nearest_dist(self, value):\n        array = np.asarray(self.k_distances)\n        idx = (np.abs(array - value)).argmin()\n        return idx\n\n    def _eps_changed(self):\n        # find the closest value to eps\n        if self.data is None:\n            return\n        self.cut_point = self._find_nearest_dist(self.eps)\n        self.plot.set_cut_point(self.cut_point)\n        self._invalidate()\n\n    def _metirc_changed(self):\n        if self.data is not None:\n            self._compute_and_plot()\n            self._invalidate()\n\n    def _on_cut_changed(self, value):\n        # cut changed by means of a cut line over the scree plot.\n        self.cut_point = value\n        self.eps = self.k_distances[value]\n\n        self.commit()\n\n    def _min_samples_changed(self):\n        if self.data is None:\n            return\n        self._compute_and_plot(cut_point=self.cut_point)\n        self._invalidate()\n\n\nif __name__ == \"__main__\":\n    a = QApplication(sys.argv)\n    ow = OWDBSCAN()\n    d = Table(\"iris.tab\")\n    ow.set_data(d)\n    ow.show()\n    a.exec()\n    ow.saveSettings()\n", "path": "Orange/widgets/unsupervised/owdbscan.py"}], "after_files": [{"content": "import sys\nfrom itertools import chain\n\nimport numpy as np\nfrom AnyQt.QtWidgets import QApplication\nfrom AnyQt.QtGui import QColor\nfrom sklearn.metrics import pairwise_distances\n\nfrom Orange.preprocess import Normalize, Continuize, SklImpute\nfrom Orange.widgets import widget, gui\nfrom Orange.widgets.utils.slidergraph import SliderGraph\nfrom Orange.widgets.settings import Setting\nfrom Orange.data import Table, DiscreteVariable\nfrom Orange.data.util import get_unique_names\nfrom Orange.clustering import DBSCAN\nfrom Orange.widgets.utils.annotated_data import ANNOTATED_DATA_SIGNAL_NAME\nfrom Orange.widgets.utils.signals import Input, Output\nfrom Orange.widgets.utils.state_summary import format_summary_details\nfrom Orange.widgets.widget import Msg\n\n\nDEFAULT_CUT_POINT = 0.1\nPREPROCESSORS = [Continuize(), Normalize(), SklImpute()]\nEPS_BOTTOM_LIMIT = 0.01\n\n\ndef get_kth_distances(data, metric, k=5):\n    \"\"\"\n    The function computes the epsilon parameter for DBSCAN through method\n    proposed in the paper.\n    Parameters\n    ----------\n    data : Orange.data.Table\n        Visualisation coordinates - embeddings\n    metric : callable or str\n        The metric to compute the distance.\n    k : int\n        Number kth observed neighbour\n\n    Returns\n    -------\n    np.ndarray\n        Epsilon parameter for DBSCAN\n    \"\"\"\n    x = data.X\n    if x.shape[0] > 1000:  # subsample\n        x = x[np.random.randint(x.shape[0], size=1000), :]\n\n    dist = pairwise_distances(x, metric=metric)\n    k = min(k+1, len(data) - 1)  # k+1 since first one is item itself\n    kth_point = np.argpartition(dist, k, axis=1)[:, k]\n    kth_dist = np.sort(dist[np.arange(0, len(kth_point)), kth_point])[::-1]\n\n    return kth_dist\n\n\nclass OWDBSCAN(widget.OWWidget):\n    name = \"DBSCAN\"\n    description = \"Density-based spatial clustering.\"\n    icon = \"icons/DBSCAN.svg\"\n    priority = 2150\n\n    class Inputs:\n        data = Input(\"Data\", Table)\n\n    class Outputs:\n        annotated_data = Output(ANNOTATED_DATA_SIGNAL_NAME, Table)\n\n    class Error(widget.OWWidget.Error):\n        not_enough_instances = Msg(\"Not enough unique data instances. \"\n                                   \"At least two are required.\")\n\n    METRICS = [\n        (\"Euclidean\", \"euclidean\"),\n        (\"Manhattan\", \"cityblock\"),\n        (\"Cosine\", \"cosine\")\n    ]\n\n    min_samples = Setting(4)\n    eps = Setting(0.5)\n    metric_idx = Setting(0)\n    auto_commit = Setting(True)\n    k_distances = None\n    cut_point = None\n\n    def __init__(self):\n        super().__init__()\n\n        self.data = None\n        self.data_normalized = None\n        self.db = None\n        self.model = None\n        self._set_input_summary(None)\n        self._set_output_summary(None)\n\n        box = gui.widgetBox(self.controlArea, \"Parameters\")\n        gui.spin(box, self, \"min_samples\", 1, 100, 1,\n                 callback=self._min_samples_changed,\n                 label=\"Core point neighbors\")\n        gui.doubleSpin(box, self, \"eps\", EPS_BOTTOM_LIMIT, 1000, 0.01,\n                       callback=self._eps_changed,\n                       label=\"Neighborhood distance\")\n\n        box = gui.widgetBox(self.controlArea, self.tr(\"Distance Metric\"))\n        gui.comboBox(box, self, \"metric_idx\",\n                     items=list(zip(*self.METRICS))[0],\n                     callback=self._metirc_changed)\n\n        gui.auto_apply(self.buttonsArea, self, \"auto_commit\")\n        gui.rubber(self.controlArea)\n\n        self.controlArea.layout().addStretch()\n\n        self.plot = SliderGraph(\n            x_axis_label=\"Data items sorted by score\",\n            y_axis_label=\"Distance to the k-th nearest neighbour\",\n            callback=self._on_cut_changed\n        )\n\n        self.mainArea.layout().addWidget(self.plot)\n\n    def check_data_size(self, data):\n        if data is None:\n            return False\n        if len(data) < 2:\n            self.Error.not_enough_instances()\n            return False\n        return True\n\n    def commit(self):\n        self.cluster()\n\n    def cluster(self):\n        if not self.check_data_size(self.data):\n            return\n        self.model = DBSCAN(\n            eps=self.eps,\n            min_samples=self.min_samples,\n            metric=self.METRICS[self.metric_idx][1]\n        ).get_model(self.data_normalized)\n        self.send_data()\n\n    def _compute_and_plot(self, cut_point=None):\n        self._compute_kdistances()\n        if cut_point is None:\n            self._compute_cut_point()\n        self._plot_graph()\n\n    def _plot_graph(self):\n        nonzero = np.sum(self.k_distances > EPS_BOTTOM_LIMIT)\n        self.plot.update(np.arange(len(self.k_distances)),\n                         [self.k_distances],\n                         colors=[QColor('red')],\n                         cutpoint_x=self.cut_point,\n                         selection_limit=(0, nonzero - 1))\n\n    def _compute_kdistances(self):\n        self.k_distances = get_kth_distances(\n            self.data_normalized, metric=self.METRICS[self.metric_idx][1],\n            k=self.min_samples\n        )\n\n    def _compute_cut_point(self):\n        self.cut_point = int(DEFAULT_CUT_POINT * len(self.k_distances))\n        self.eps = self.k_distances[self.cut_point]\n\n        if self.eps < EPS_BOTTOM_LIMIT:\n            self.eps = np.min(\n                self.k_distances[self.k_distances >= EPS_BOTTOM_LIMIT])\n            self.cut_point = self._find_nearest_dist(self.eps)\n\n    @Inputs.data\n    def set_data(self, data):\n        self.Error.clear()\n        self._set_input_summary(data)\n        if not self.check_data_size(data):\n            data = None\n        self.data = self.data_normalized = data\n        if self.data is None:\n            self._set_output_summary(None)\n            self.Outputs.annotated_data.send(None)\n            self.plot.clear_plot()\n            return\n\n        if self.data is None:\n            return\n\n        # preprocess data\n        for pp in PREPROCESSORS:\n            self.data_normalized = pp(self.data_normalized)\n\n        self._compute_and_plot()\n        self.unconditional_commit()\n\n    def send_data(self):\n        model = self.model\n\n        clusters = [c if c >= 0 else np.nan for c in model.labels]\n        k = len(set(clusters) - {np.nan})\n        clusters = np.array(clusters)\n        core_samples = set(model.projector.core_sample_indices_)\n        in_core = np.array([1 if (i in core_samples) else 0\n                            for i in range(len(self.data))])\n\n        domain = self.data.domain\n        attributes, classes = domain.attributes, domain.class_vars\n        meta_attrs = domain.metas\n        names = [var.name for var in chain(attributes, classes, meta_attrs) if var]\n\n        u_clust_var = get_unique_names(names, \"Cluster\")\n        clust_var = DiscreteVariable(\n            u_clust_var, values=[\"C%d\" % (x + 1) for x in range(k)])\n\n        u_in_core = get_unique_names(names + [u_clust_var], \"DBSCAN Core\")\n        in_core_var = DiscreteVariable(u_in_core, values=(\"0\", \"1\"))\n\n        new_table = self.data.add_column(clust_var, clusters, to_metas=True)\n        new_table = new_table.add_column(in_core_var, in_core, to_metas=True)\n\n        self._set_output_summary(new_table)\n        self.Outputs.annotated_data.send(new_table)\n\n    def _set_input_summary(self, data):\n        summary = len(data) if data else self.info.NoInput\n        details = format_summary_details(data) if data else \"\"\n        self.info.set_input_summary(summary, details)\n\n    def _set_output_summary(self, output):\n        summary = len(output) if output else self.info.NoOutput\n        details = format_summary_details(output) if output else \"\"\n        self.info.set_output_summary(summary, details)\n\n    def _invalidate(self):\n        self.commit()\n\n    def _find_nearest_dist(self, value):\n        array = np.asarray(self.k_distances)\n        idx = (np.abs(array - value)).argmin()\n        return idx\n\n    def _eps_changed(self):\n        # find the closest value to eps\n        if self.data is None:\n            return\n        self.cut_point = self._find_nearest_dist(self.eps)\n        self.plot.set_cut_point(self.cut_point)\n        self._invalidate()\n\n    def _metirc_changed(self):\n        if self.data is not None:\n            self._compute_and_plot()\n            self._invalidate()\n\n    def _on_cut_changed(self, value):\n        # cut changed by means of a cut line over the scree plot.\n        self.cut_point = value\n        self.eps = self.k_distances[value]\n\n        self.commit()\n\n    def _min_samples_changed(self):\n        if self.data is None:\n            return\n        self._compute_and_plot(cut_point=self.cut_point)\n        self._invalidate()\n\n\nif __name__ == \"__main__\":\n    a = QApplication(sys.argv)\n    ow = OWDBSCAN()\n    d = Table(\"iris.tab\")\n    ow.set_data(d)\n    ow.show()\n    a.exec()\n    ow.saveSettings()\n", "path": "Orange/widgets/unsupervised/owdbscan.py"}]}