The Affinity Matrix Is NON-BINARY with`affinity="precomputed_nearest_neighbors"`

### Describe the issue linked to the documentation

## Issue Source:

https://github.com/scikit-learn/scikit-learn/blob/59dd128d4d26fff2ff197b8c1e801647a22e0158/sklearn/cluster/_spectral.py#L452-L454

## Issue Description

The Affinity Matrix Is _non-binary_ with`affinity`=`"precomputed_nearest_neighbors"`. I.e., when a precomputed distance matrix is given as `x`, the affinity matrix from SpectralClustering.fit().affinity_matrix_ is NOT binary (as described in the document). It has 3 values: 0.0, 1.0, and 0.5.

## Reproducible Code Snippet
Generate a random distance ,a
```python
from sklearn.cluster import SpectralClustering
import numpy as np

## generate a random distance matrix --> symmetric
np.random.seed(0)
distmat=np.random.rand(200,200)
distmat=(np.triu(distmat,1)+np.triu(distmat,1).T)/2
print(f"Check asymmetric locations (if any):\t{np.where(distmat!=distmat.T)}")

## affinity matrix 
aff_mat=SpectralClustering(n_clusters=30,affinity='precomputed_nearest_neighbors',assign_labels='discretize', n_neighbors=50 ,n_jobs=-1).fit(distmat).affinity_matrix_.toarray()
print(f"Unique values (ought to be 'binary'):\t{np.unique(aff_mat)}")
```

## Machine & Version Info

```python
System:
    python: 3.8.3 (default, Jul  2 2020, 16:21:59)  [GCC 7.3.0]
executable: /opt/share/linux-rocky8-x86_64/gcc-12.2.0/anaconda3-2020.07-yv6vdwqiouaru27jxhpezh6t6mdpqf3e/bin/python
   machine: Linux-4.18.0-425.3.1.el8.x86_64-x86_64-with-glibc2.10

Python dependencies:
          pip: 20.1.1
   setuptools: 65.6.3
      sklearn: 0.23.1
        numpy: 1.22.3
        scipy: 1.5.0
       Cython: 0.29.21
       pandas: 1.4.2

Built with OpenMP: True
```

### Suggest a potential alternative/fix

Since the affinity matrix is calculated as  `(connectivity+connectivity.T)*0.5` [source_code](https://github.com/scikit-learn/scikit-learn/blob/59dd128d4d26fff2ff197b8c1e801647a22e0158/sklearn/cluster/_spectral.py#L715C8-L720C74), and that the `connectivity` is calculated by `kneighbors_graph` [source_code](https://github.com/scikit-learn/scikit-learn/blob/59dd128d4d26fff2ff197b8c1e801647a22e0158/sklearn/neighbors/_base.py#L998C5-L1002C1), it is intrinsically not symmetric -- i might be j's K nearest neighbor, while j could not be i's when `n_quirey `== `n_samples`.

COMMENT:
The spectral clustering algorithm as outlined in von Luxburg, 2007, p.3, notes that when using the k-nearest neighbour graph for the construction of a similarity graph, we must adjust for the fact that this is initially not symmetric. The author suggests two approaches to this:

> k-nearest neighbor graphs: Here the goal is to connect vertex vi with vertex vj if vj is among the k-nearest neighbors of vi. However, this definition leads to a directed graph, as the neighborhood relationship is not symmetric. There are two ways of making this graph undirected. The first way is to simply ignore the directions of the edges, that is we connect vi and vj with an undirected edge if vi is among the k-nearest neighbors of vj or if vj is among the k-nearest neighbors of vi. The resulting graph is what is usually called the k-nearest neighbor graph. The second choice is to connect vertices vi and vj if both vi is among the k-nearest neighbors of vj and vj is among the k-nearest neighbors of vi. The resulting graph is called the mutual k-nearest neighbor graph. In both cases, after connecting the appropriate vertices we weight the edges by the similarity of their endpoints.

As far as I can tell no provision has been made for this in the source code yet.

https://github.com/scikit-learn/scikit-learn/blob/59dd128d4d26fff2ff197b8c1e801647a22e0158/sklearn/cluster/_spectral.py#L716-L720

I am happy to work on this and put in a pull request. It would be great to get some guidance on this @glemaitre . Optimally, I would imagine we should provide the user with the option to pass a parameter to choose their preferred method. I am not sure if the impact of this choice is large and what the default choice ought to be.

Labels: Documentation, Needs Investigation