PMLBook.github.io/Ch_discovery.html at main · PMLBook/PMLBook.github.io

History

1324 lines (1150 loc) · 172 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

<!DOCTYPE html>

<head>

<title>5. Structure discovery — Principles of Machine Learning: A Deployment-First Perspective</title>

document.documentElement.dataset.mode = localStorage.getItem("mode") || "";

document.documentElement.dataset.theme = localStorage.getItem("theme") || "";

</script>

window.dataLayer = window.dataLayer || [];

function gtag(){ dataLayer.push(arguments); }

gtag('js', new Date());

gtag('config', 'G-0HQMPESCSN');

</script>

window.dataLayer = window.dataLayer || [];

function gtag(){ dataLayer.push(arguments); }

gtag('js', new Date());

gtag('config', 'G-0HQMPESCSN');

</script>

</head>

<div id="pst-skip-link" class="skip-link d-print-none"><a href="#main-content">Skip to main content</a></div>

Back to top</button>

<input type="checkbox"

class="sidebar-toggle"

id="pst-primary-sidebar-checkbox"/>

<input type="checkbox"

class="sidebar-toggle"

id="pst-secondary-sidebar-checkbox"/>

<form class="bd-search d-flex align-items-center"

action="search.html"

method="get">

<input type="search"

class="form-control"

name="q"

id="search-input"

placeholder="Search this book..."

aria-label="Search this book..."

autocomplete="off"

autocorrect="off"

autocapitalize="off"

spellcheck="false"/>

</form></div>

</div>

</div>

</header>

</div>

</a></div>

document.write(`

Search

</button>

`);

</script></div>

Welcome to our Principles of Machine Learning

</a>

</li>

</ul>

<li class="toctree-l1"><a class="reference internal" href="Ch_introduction.html">1. Introduction</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_regression.html">2. Regression</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_methodology1.html">3. Methodology I: Three basic tasks</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_classification1.html">4. Classification I: The geometric view</a></li>

<li class="toctree-l1 current active"><a class="current reference internal" href="#">5. Structure discovery</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_density.html">6. Density estimation</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_classification2.html">7. Classification II: The probabilistic view</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_methodology2.html">8. Methodology II: Pipelines</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_feature.html">9. Feature Engineering</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_ensemble.html">10. Ensemble methods</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_neuralnets.html">11. Neural networks</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_optimisation.html">12. Optimisation methods</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_methodology3.html">13. Methodology III: Workflows</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_ethics.html">14. The machine learning professional</a></li>

<li class="toctree-l1"><a class="reference internal" href="Ch_appendix.html">15. Appendix</a></li>

</ul>

</div>

</nav></div>

</div>

</div>

</div>

</button></div>

</div>

</button>

<li><a href="https://github.com/PMLBook/PMLBook.github.io" target="_blank"

class="btn btn-sm btn-source-repository-button dropdown-item"

title="Source repository"

data-bs-placement="left" data-bs-toggle="tooltip"

Repository

</a>

</li>

<li><a href="https://github.com/PMLBook/PMLBook.github.io/issues/new?title=Issue%20on%20page%20%2FCh_discovery.html&body=Your%20issue%20content%20here." target="_blank"

class="btn btn-sm btn-source-issues-button dropdown-item"

title="Open an issue"

data-bs-placement="left" data-bs-toggle="tooltip"

Open issue

</a>

</li>

</ul>

</div>

</button>

<li><a href="_sources/Ch_discovery.md" target="_blank"

class="btn btn-sm btn-download-source-button dropdown-item"

title="Download source file"

data-bs-placement="left" data-bs-toggle="tooltip"

.md

</a>

</li>

<li>

<button onclick="window.print()"

class="btn btn-sm btn-download-pdf-button dropdown-item"

title="Print to PDF"

data-bs-placement="left" data-bs-toggle="tooltip"

.pdf

</button>

</li>

</ul>

</div>

<button onclick="toggleFullScreen()"

class="btn btn-sm btn-fullscreen-button"

title="Fullscreen mode"

data-bs-placement="bottom" data-bs-toggle="tooltip"

</button>

document.write(`

</button>

`);

</script>

document.write(`

</button>

`);

</script>

</button>

</div></div>

</div>

<h1>Structure discovery</h1>

<div>

<h2> Contents </h2>

</div>

<li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#is-english-we-speaking">5.1. Is English we speaking?</a></li>

<li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#embedded-deployment">5.2. Embedded deployment</a></li>

<li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#formulating-structure-discovery-problems">5.3. Formulating structure discovery problems</a><ul class="nav section-nav flex-column">

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#mathematical-notation">5.3.1. Mathematical notation</a></li>

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#cost-and-quality">5.3.2. Cost and quality</a></li>

</ul>

</li>

<li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#clustering">5.4. Clustering</a><ul class="nav section-nav flex-column">

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#k-means">5.4.1. K-means</a><ul class="nav section-nav flex-column">

<li class="toc-h4 nav-item toc-entry"><a class="reference internal nav-link" href="#similarity-as-proximity">5.4.1.1. Similarity as proximity</a></li>

<li class="toc-h4 nav-item toc-entry"><a class="reference internal nav-link" href="#k-means-as-an-optimisation-method">5.4.1.2. K-means as an optimisation method</a></li>

<li class="toc-h4 nav-item toc-entry"><a class="reference internal nav-link" href="#local-minima-in-k-means">5.4.1.3. Local minima in K-means</a></li>

<li class="toc-h4 nav-item toc-entry"><a class="reference internal nav-link" href="#selecting-k">5.4.1.4. Selecting \(K\)</a></li>

</ul>

</li>

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#connectivity-based-methods">5.4.2. Connectivity-based methods</a><ul class="nav section-nav flex-column">

<li class="toc-h4 nav-item toc-entry"><a class="reference internal nav-link" href="#similarity-as-connectivity-dbscan">5.4.2.1. Similarity as connectivity: DBSCAN</a></li>

<li class="toc-h4 nav-item toc-entry"><a class="reference internal nav-link" href="#dbscan-hyperparameters">5.4.2.2. DBSCAN hyperparameters</a></li>

</ul>

</li>

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#hierarchical-clustering">5.4.3. Hierarchical clustering</a></li>

</ul>

</li>

<li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#basis-discovery">5.5. Basis discovery</a><ul class="nav section-nav flex-column">

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#measuring-sample-spread">5.5.1. Measuring sample spread</a></li>

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#the-directional-sample-variance">5.5.2. The directional sample variance</a></li>

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#spread-along-perpendicular-directions">5.5.3. Spread along perpendicular directions</a></li>

<li class="toc-h3 nav-item toc-entry"><a class="reference internal nav-link" href="#principal-component-analysis">5.5.4. Principal Component Analysis</a></li>

</ul>

</li>

<li class="toc-h2 nav-item toc-entry"><a class="reference internal nav-link" href="#summary-and-discussion">5.6. Summary and discussion</a></li>

</ul>

</nav>

</div>

<h1>5. Structure discovery<a class="headerlink" href="#structure-discovery" title="Link to this heading">#</a></h1>

The concept of attribute space is key in machine learning.

We have learned that the attribute space allows us to visualise datasets. Although visualising datasets is indeed very important, there is much more to the attribute space than just plotting samples. The attribute space provides us with a framework to think about populations and how machine learning works. Using the notion of attribute space we can make the obvious but crucial observation that machine learning works because the attribute space is mostly empty. What we mean by this is that samples from a population do not just lie anywhere in the attribute space. The way that samples from a population are spread across the attribute space is what we call the structure of the population. Whether implicitely or explicitely, machine learning methods operate on the basis that there exists an underlying structure whose understanding we can benefit from.

The goal of unsupervised learning is to provide answers to the important question, what is the structure of my population? Or in simpler words, where in the attribute space will I find samples from my population? As you would expect, unsupervised learning methods use datasets to build models that describe how samples from a population are spread across the attribute space.

This chapter will focus on our first family of unsupervised learning problems: structure discovery. We will start by taking a linguistic detour which will invite us to ask ourselves, is English we speaking? This linguistic journey will culminate in our fifth top tip. Then we will introduce the notion of embedded deployment, which is the most common deployment modality in unsupervised learning. Afterwards, we will formulate structure discovery problems and then will introduce two subfamilies of approaches, namely clustering and basis discovery. The final two sections will cover each subfamily in more detail.

<h2>5.1. Is English we speaking?<a class="headerlink" href="#is-english-we-speaking" title="Link to this heading">#</a></h2>

If you are a Muggle like us, reading the words wingardium leviosa will leave you indifferent. It might have an esoteric feel to it but still, it will sound like a meaningless utterance. However if you happen to study at Hogwarts School of Witchcraft and Wizardry, you will most certainly know that there are wingardium leviosas and wingardium leviosaaas, and your ability to distinguish them will make all the difference between being able to levitate an object and failing to do so. Harry Potter’s best friend and Hogwarts School’s low-ability student Ron Weasley knows this well: language precision can make or break a charm.

Fantasy fiction, like the Harry Potter series, draws heavily from belief systems in which rituals involving precise vocalisations allow the initiated to connect with the supernatural world. Language precision being essential in many such rituals, it is not surprising to learn that one of the most important contributions to linguistics ever, known as the Astadhyayi, was born out of the need to transmit faithfully a corpus of sacred texts. These texts are known as the Vedas and were composed in the Sanskrit language around 1500 BCE, northwest of the Indian subcontinent. The Astadhyayi is a sophisticated description of the Sanskrit language and was written with a clear goal in mind: to freeze Sanskrit so that future generations would be able to recite the Vedas exactly as they were originally composed. Thanks to the Astadhyayi, Sanskrit remains the best understood ancient language.

The desire to freeze the Sanskrit language can only make sense if we acknowledge that natural languages change over time. We have all witnessed language changes in our own lifetimes and whether we welcome these changes or deeply mistrust them, they are the reason behind the existing diversity of languages. Early Western scholars found the origins of the world languages in a divine punishment - Babel’s confusio linguarium. Nowadays we ascribe the diversity of languages to a historical process where communities that once lived together broke up and diverged, following different geographical and linguistic paths. This historical process is frequently illustrated as a tree whose branches represent the different linguistic paths traversed by multiple generations of peoples and culminated in today’s living languages, symbolised by the tree’s leaves (see <a class="reference internal" href="#language-tree">Fig. 5.1</a>). Language trees also serve as taxonomy systems, allowing us to represent the relationship between languages in pretty much the same way as we use life trees to represent the evolution of living organisms and their relationships. Sanskrit, for instance, belongs to the Indo-European language branch, together with other ancient languages such as Latin, and many living ones, including Punjabi, Persian, Kurdish, Albanian, Latvian, German and Portuguese. So here is a simple question for you: how many leaves do you think the full language tree has? Tens, hundreds, thousands?

Fig. 5.1 Branches of a horse chestnut tree in Clissold Park, London. The origins of and relationship between human languages are frequently represented as tree branches. Branching can be interpreted as the historical process by which a single language splits into separate languages. Therefore, a branch can also be used to represent a family of related languages. For instance, the Indo-European language branch has several sub-branches, including the Indo-Iranian, Anatolian, Armenian, Hellenic, Balto-Slavic, Italic and Germanic. These sub-branches, in turn, keep branching further.<a class="headerlink" href="#language-tree" title="Link to this image">#</a>

</figcaption>

</figure>

Linguists have asked themselves this same question many times before, and answers range from several thousand languages to a few dozen. Given the lack of consensus the obvious follow-up question is, what is so difficult about counting languages? Do linguists suspect that there might be languages spoken by peoples they have not met yet? Are there previously recorded languages that might have now ceased to exist? As it turns out, the reason is much deeper than this: we simply find it difficult to agree on what a language is. Gone are the days when true languages were superior forms of human communication, equipped with a formalised grammar, a rich literary tradition and a powerful army. Back in those days we would have said that two people understand each other, provided they speak the same prescribed language - or something close to it. Today we say instead that two people speak the same language, if they understand each other. Where we used to see immutable languages surrounded by corrupted versions, such as provincial dialects or creoles, we now see a linguistic continuum where every point can be at the same time a language, a dialect and a creole. Languages are no longer seen as pure and isolated entities, but as ever changing pluralities influencing one another. Rather than as a branching tree, a more accurate illustration of the evolution of natural languages would be that of a leaf whose veins diverge and reconnect, evolve independently over time and then mix back again, each vein in the leaf as valuable as any other (see <a class="reference internal" href="#language-leaf">Fig. 5.2</a>).

Fig. 5.2 Detailed view of a horse chestnut leaf. Its veins do not grow and diverge independently from one another, but remain connected. Analogously, languages do not develop independently from one another. There is no such thing as a pure language.<a class="headerlink" href="#language-leaf" title="Link to this image">#</a>

</figcaption>

</figure>

Let us move to the safe realm of machine learning and consider the problem of transcribing English speech to text. To build a machine learning solution for this problem, we would need to build a dataset consisting of multiple English speech recordings together with their transcriptions. This might seem uncontroversial at first, however upon reflection we will ask ourselves, what do we mean by English? One of the so-called standard Englishes, for instance standard British, American or Australian? Or a group of related English variants? Whether we think English should be spoken in a certain, correct way is completely irrelevant to solve our problem. The relevant consideration is how the speakers in our target population actually speak. We know by now that our datasets have to be representative of our target population. Therefore, if we want to create the right dataset to build an English speech-to-text transcription model, we need to know in advance which population we will use this model against so that we can collect the right speech recordings. Collecting speech recordings that reflect how we feel our population should speak will not work, as we will risk rendering our datasets non-representative and hence unsuitable to build our solution.

Our fifth top tip is:

<h3 style="text-align: center;">Know your populations!</h3>

</div>

When we describe our populations we sometimes use concepts that behind an appearance of familiarity, are only vaguely understood. In some cases those concepts can even be nonsensical. Language is one of those deceivingly simple concepts but there are many others, for instance emotion, intelligence, opinion, taste or ethnicity. Taking the concepts that define our populations for granted will at best lead to meaningless problems, at worst to harmful solutions. In every case, dissapointment will follow as we will have spent efforts building solutions that when deployed do not work as intended. Taking the time to understand our populations and the concepts that define them is crucial to formulate problems that make sense and to create the right datasets to solve them.

A note of warning: The Cruciatus Curse always hits sloppy machine learning practitioners who do not take the time to understand their populations.

Question for you

Is English we speaking?

Submit your response here: <a href="https://forms.office.com/e/HQS8D8Lgbx" target = "_blank">Your Response</a>

</div>

</section>

<h2>5.2. Embedded deployment<a class="headerlink" href="#embedded-deployment" title="Link to this heading">#</a></h2>

Machine learning is concerned with problems involving populations. In some cases these problems can be fully formulated in terms of the attributes that describe the target population. For instance, in a prediction problem our goal is to estimate the value of the label of a future sample. The label is, of course, one of the attributes of our samples. Using supervised learning, we can build a model that predicts the value of a label. This model is the solution to the prediction problem and can therefore be directly deployed. Direct deployment is the deployment modality where the model that we have built is the solution to the problem at hand.

There are other problems that are not fully formulated in terms of the attributes of the target population, yet we can benefit from learning something about the population. In such cases it is useful to distinguish between the main problem that we want to solve, and the nested problem of gaining knowledge about the population. Unsupervised learning can be used to build models that constitute solutions to a nested problem. Once built, unsupervised learning models can be embedded within the solution to the main problem and be deployed as one of its components. We call this second deployment modality embedded deployment.

Let us discuss one example that illustrates the notion of embedded deployment. Consider a recommendation system for a movie streaming plaform, whose purpose is to offer a personalised catalog of movies to the platform’s customers. Building a recommendation system is our main problem, where the platform’s customers form our target population. To build this recommendation system it is important to understand our population. One option to describe our population is to define different categories of customers. This task is known as customer segmentation. Customer categories can be hand-crafted based on previous knowledge about the customers or be discovered using datasets that record details about the customers. Customer segmentation constitutes the nested problem that we need to solve prior to solving the main problem of building a recommendation system. Once we have defined a set of customer categories, the recommendation system can create a catalog for each category of customers. At the end of this process we will deploy a recommendation system and embedded within it, a customer segmentation solution.

Unsupervised learning offers a variety of approaches to create customer categories using datasets. Even though we have not covered any unsupervised learning approach yet, we would agree that different unsupervised learning approaches might lead to different categories of customers. So the question is, how can we identify the most suitable segmentation of customers? To answer this question, we need to note that we are not asking how well a customer segmentation model describes our population of customers, but rather how useful it is in the context of the recommendation system that we want to build. In other words, to assess the quality of the solution to the nested problem, we need to assess the deployment quality of the solution to the main problem. Understanding this point is key to developing test strategies in unsupervised learning. We will come back to this point when we discuss the notions of <a class="reference internal" href="#costanddepl">Cost and quality</a> in structure discovery.

</section>

<h2>5.3. Formulating structure discovery problems<a class="headerlink" href="#formulating-structure-discovery-problems" title="Link to this heading">#</a></h2>

Unsupervised learning builds models that describe how samples from a population are distributed across the attribute space. Depending on the type of description that they provide, unsupervised learning methods can be categorised into two subfamilies. These two subfamilies were introduced in <a class="reference internal" href="Ch_introduction.html#intro3">The machine learning taxonomy</a> and are density estimation, which will be covered in a <a class="reference internal" href="Ch_density.html#density">later chapter</a>, and structure discovery, which is the focus of this chapter.

A structure discovery model describes its target population as a discrete set of constituents. There are different approaches in structure discovery, and we will group them into two categories: clustering and basis discovery. Clustering approaches create constituents that are defined as collections of similar samples. Constituents in basis discovery are directions of interest in the attribute space. Let us develop the mathematical notation needed to formulate structure discotery problems.

<h3>5.3.1. Mathematical notation<a class="headerlink" href="#mathematical-notation" title="Link to this heading">#</a></h3>

In contrast with supervised learning, in unsupervised learning the notions of label and predictor do not exist. Thus, the mathematical notation that we will present in structure discovery will not include either of them.

The basic mathematical notation that we need to discuss structure discovery problems and methods consists of the following concepts:

<li>Population sample: \(\boldsymbol{x}\).</li>

<li>Number of attributes: \(D\). This is also the number of dimensions of the attribute space.</li>

<li>Dataset: \(\{\boldsymbol{x}_i: 1\leq i \leq N \}\), where \(N\) is the number of samples and \(i\) is the sample identifier. The attributes of a dataset sample \(\boldsymbol{x}_i\) will be denoted by \(x_{i,1}, ..., x_{i,D}\). When all the attributes are numerical, we will define sample \(\boldsymbol{x}_i\) as the vector \(\boldsymbol{x}_i=\left[x_{i,1}, ..., x_{i,D} \right]^T\). Note that we have not appended the value 1 to this vector, as we did in supervised learning.</li>

<li>Model: discrete set of \(K\) constituents \(\{C_k: 1\leq k \leq K\}\), where \(k\) is the constituent identifier.</li>

</ul>

<a class="reference internal" href="#agevsdevicevsos">Table 5.1</a> shows a toy dataset consisting of samples described by three attributes, namely Age, Device type and OS version. For instance, the third sample in this dataset has the attributes \(x_{3,1} = 66\), \(x_{3,2} =\text{ 'Smart TV'}\) and \(x_{3,3} = \text{ 'Tizen 6.5'}\), where we have used \(Age\) as the first attribute, \(Device \ type\) as the second and \(OS \ version\) as the third. This toy dataset could be used to build a solution for a customer segmentation problem like the one suggested in the section on <a class="reference internal" href="#embedded">Embedded deployment</a>. Note that there is nothing about <a class="reference internal" href="#agevsdevicevsos">Table 5.1</a> that makes this dataset an unsupervised learning dataset. It is simply a dataset. Some authors make a distinction between labelled datasets and unlabelled datasets to emphasise that they are used to solve, respectively, a supervised or an unsupervised learning problem. Any dataset can however be used in both supervised and unsupervised learning problems and therefore we will not make such distinction. From a deployment-first perspective it makes sense to distinguish between supervised and unsupervised learning problems and models, not datasets.

<caption>Table 5.1 A toy dataset registering three attributes (customer age, device type and OS version) describing a group of customers of a video streaming platform.<a class="headerlink" href="#agevsdevicevsos" title="Link to this table">#</a></caption>

<thead>

<th class="head">Device type</th>

<th class="head">OS version</th>

</tr>

</thead>

<tbody>

<td>Mobile</td>

<td>Android 11</td>

</tr>

<td>Tablet</td>

</tr>

<td>Smart TV</td>

<td>Tizen 6.5</td>

</tr>

<td>Laptop</td>

<td>Windows 10</td>

</tr>

<td>Mobile</td>

</tr>

</tbody>

</table>

</div>

Models in structure discovery describe a population as a collection of \(K\) constituents \(C_k\). Take as an example a customer segmentation scenario where we define four categories of customers, for instance the categories:

<li>\(C_1: \{\text{Customers where } Age \leq 20\}\)</li>

<li>\(C_2: \{\text{Customers where } 20 < Age \leq 45\}\)</li>

<li>\(C_3: \{\text{Customers where } 45 < Age \leq 60\}\)</li>

<li>\(C_4: \{\text{Customers where } 60 \leq Age\}\)</li>

</ul>

These four categories constitute a summarised description of our customer base and they allow us to think about our population as if it consisted of four customers. Using our mathematical notation, we would say that this model consists of \(K = 4\) constituents. The first constituent \(C_1\) corresponds to the category of all the customers in our population who are 20 years old or younger. The remaining constituents, \(C_2\), \(C_3\) and \(C_4\), can be interpreted in a similar way. In this example we have used the customers’ age to define each category, but we could have used the other attributes too. For instance, we could have defined one constituent as the group of customers who are 45 years old or younger, and use a mobile device. The question is, how can we come up with such constituents?

In structure discovery we use datasets of samples from our target population to define a set of constituents. In some cases these constituents can have a straightforward interpretation like \(C_1\) corresponds to all the customers who are 20 years old or younger, but in general such simple interpretation might not be available. As we shall see, each structure discovery approach will implement a different strategy and in general, different approaches will produce a different set of constituents. To make sense of each strategy, we need to discuss first the notion of cost in unsupervised learning.

</section>

<h3>5.3.2. Cost and quality<a class="headerlink" href="#cost-and-quality" title="Link to this heading">#</a></h3>

In chapter <a class="reference internal" href="Ch_methodology1.html#meth1">Methodology I: Three basic tasks</a> we learned that during training, machine learning models are built using a dataset together with a notion of cost. We also learned that the final quality of a model has to be assessed in deployment conditions, either live, once the model has been deployed, or during an offline test task using a separate dataset.

Before discussing how the notions of cost and quality are applied in structure discovery -and unsupervised learning in general- let us pause for a moment and reflect on how we approach quality assessment in supervised learning. As mentioned in the <a class="reference internal" href="#embedded">Embedded deployment</a> section, supervised learning models can be directly deployed against the target population. Furthremore, in direct deployment the quality of a solution is defined in terms of the attributes of the population. Specifically, the quality of a supervised learning model is defined as its ability to predict one of the attributes of the population, namely the label. Since quality assessement in supervised learning requires comparing a model’s predicted labels to the true labels, designing a test tasks is simple. We just need to create a dataset of samples whose labels we know -a test dataset- and ask the model to predict the values of the labels. The predictions on the test dataset can then be used to estimate the deployment quality of the model.

Structure discovery and in general unsupervised learning models are also trained using a dataset and a notion of cost. The cost in unsupervised learning is however very different from the cost in supervised learning. Specifically, the unsupervised learning cost cannot generally be linked to the notion of deployment quality. Having learned that training costs in supervised learning capture a model’s ability to predict the value of a label, you might find this statement confusing. As we shall see, in structure discovery the cost encapsulates prior assumptions about the nature of the constituents that we seek to define. This means that when we choose a structure discovery approach together with a cost we are imposing how the final constituents will look. A similar observation will be made about the role of the cost in <a class="reference internal" href="Ch_density.html#density">density estimation</a>. A natural follow-up question is, how do we know if we are choosing the right structure discovery approach? Are we obtaining the true constituents of our population? For instance, in the customer segmentation problem we will ask ourselves, how do we know that we have created the right categories of customers, if their nature depends on a cost that we have chosen?

As was the case in supervised learning, we can only assess the quality of an unsupervised learning model in deployment conditions. Deployment is however very different in supervised and unsupervised learning. Since unsupervised learning models are usually deployed as a component of the solution of a main problem, the notion of deployment quality will in general not be defined in terms of the attributes of the population. Therefore, we might not be able to use a dataset of samples from our population to assess the quality of our solution. Quality assessment in unsupervised learning depends heavily on the nature of the main problem. To illustrate this point, let us get back to our customer segmentation problem. To assess the quality of a customer segmentation solution we need to assess the quality of the whole recommendation system it is a part of, for instance by counting how many movies from the catalog our customers have watched. Note that in this example, the quantity number of watched movies is not provided by any of the attributes of our population (e.g. age, device type, OS version). Furthermore, the same customer segmentation solution could be appropriate for the recommendation system of a video streaming platform, but not for the recommendation system of an e-commerce website. Therefore, rather than asking ourselves whether we have identified the true constituents of our population, we need to ask ourselves whether the constituents that we have defined are the right ones for the main problem being considered.

Since cost and deployment quality in unsupervised learning are assessed differently, designing validation and test tasks is not always straightforward. In some cases, model validation and test tasks cannot rely on previously collected datasets and can only be implemented live during deployment. For instance, to compare the quality of several customer segmentation solutions for our video recommendation system, we might need to deploy each customer segmentation solution against different groups of customers formed randomly. Note that in this example of live validation, there is no need to previously create a validation dataset. Once again, im machine learning we should always first identify the tasks that we want to carry out, then decide whether and how to use data.

</section>

<h2>5.4. Clustering<a class="headerlink" href="#clustering" title="Link to this heading">#</a></h2>

In this section we introduce clustering, our first family of structure discovery methods. Clustering methods split a collection of samples into groups, or clusters, of similar samples. Given a dataset consisting of samples extracted from a population, the set of clusters created by clustering can be interpreted as the population’s constituents.

Customer segmentation is an example of a problem where we can apply clustering methods. In this case, a cluster \(C_k\) can be defined as a collection of similar customers, i.e. customers with similar personal characteristics, preferences, behaviour or background. Each cluster of customers can then be interpreted as a customer category or a customer prototype. Another example of a problem involving human populations where clustering would be useful is the following. Imagine we are interested in manufacturing T-shirts of \(K\) different sizes. We would like the chosen sizes to be suitable for as many individuals as possible. To determine the right sizes we could create a dataset of samples consisting of the chest width and chest length of a collection of individuals. Clustering would allow us to create \(K\) groups of individuals of similar chest width and length. For each cluster of individuals, a T-shirt could be manufactured whose size is the average size of the individuals within the corresponding cluster.

Since a cluster is defined as a group of similar samples, clustering tecniques require a notion of similarity between samples, so that we can determine which samples belong together. A notion of similarity implicitly encapsulates a notion cost and as we shall see, different clustering approaches differ in the notion of cost that they implement.

<h3>5.4.1. K-means<a class="headerlink" href="#k-means" title="Link to this heading">#</a></h3>

<a class="reference internal" href="#clusters1a">Fig. 5.3</a> represents in the attribute space a dataset consisting of 50 samples described by two attributes \(x_1\) and \(x_2\). How would you describe this dataset?

Fig. 5.3 Toy dataset consisting of 50 samples described by two attributes \(x_1\) and \(x_2\). Visually, samples are clumped around the points of coordinates \((0,5)\) and \((10,0)\).<a class="headerlink" href="#clusters1a" title="Link to this image">#</a>

</figcaption>

</figure>

A simple way to describe the dataset in <a class="reference internal" href="#clusters1a">Fig. 5.3</a> would be as two distinct clumps of samples roughly spread around the points \((0,5)\) and \((10,0)\), respectively. Note that this is a summarised description of our dataset. Instead of reading the \(x_1\) and \(x_2\) coordinates of each of the 50 samples in the dataset, we have read the coordinates of just two points in the attribute space, namely the centres \((0,5)\) and \((10,0)\). We can distinguish both clumps visually by assigning one colour to samples in one clump, and another colour to samples in the other clump, as in <a class="reference internal" href="#clusters1b">Fig. 5.4</a>.

Fig. 5.4 Samples in <a class="reference internal" href="#clusters1a">Fig. 5.3</a> that belong to the same clump are shown in the same colour.<a class="headerlink" href="#clusters1b" title="Link to this image">#</a>

</figcaption>

</figure>

Incidentally, this summarised description is a clustering arrangement consisting of \(K=2\) constituents, \(C_1\) and \(C_2\), where \(C_1\) is the set of all the samples around \((0,5)\) and \(C_2\) is the set of all the samples around \((10, 0)\). In other words, we have inadvertently run a clustering method on the dataset shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>. What we want to ask ourselves is, what process have we followed to identify both clusters? Specifically, which notion of similarity have we used to group them together? As it turns out, we have mentally run, unknowingly, K-means clustering. K-means is a clustering algorithm that creates clusters as groups of samples that are close to one another in the attribute space. In K-means, proximity encodes the notion of similarity between samples.

In the name K-means, \(K\) refers to the number of clusters that will be created and is a quantity that needs to be set beforehand. \(K\) is in fact a hyperparameter and different values of \(K\) will lead to solutions of different complexity. To see why just ask yourself, is it easier to describe a dataset as a collection of \(K=2\) clusters or as \(K=20\) clusters? The latter would indeed be more complex than the former.

<h4>5.4.1.1. Similarity as proximity<a class="headerlink" href="#similarity-as-proximity" title="Link to this heading">#</a></h4>

There exist many options to define mathematically the notion of proximity. One of them is based on the so-called squared distance. Given two samples \(\boldsymbol{x}_i\) and \(\boldsymbol{x}_j\) consisting of \(D\) attributes \(x_{i,1}, ..., x_{i,D}\) and \(x_{j,1}, ..., x_{j,D}\) respectively, the squared distance \(d^2_{i,j}\) between sample \(\boldsymbol{x}_i\) and sample \(\boldsymbol{x}_j\) is defined as the sum of the squared difference between each pair of corresponding attributes:

(5.1)<a class="headerlink" href="#equation-kmeanssqdist" title="Link to this equation">#</a>\[

d^2_{i,j} = (x_{i,1}-x_{j,1})^2 + ... + (x_{i,D}-x_{j,D})^2

\]</div>

Two samples will then be close if their square distance is small, far if it is large. Using proximity as our notion of similarity, in a K-means clustering solution samples within the same cluster should be close to one another and samples from different clustres should be far apart. In other words, similar (close) samples should belong to the same cluster and dissimilar (distant) ones to different clusters. Before discussing how K-means uses the squared distance to create clusters, have a look at the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>. Plot the samples of the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a> and have a go at the ensuing question.

<caption>Table 5.2 A simple dataset consisting of \(N=8\) samples described by two attributes \(x_1\) and \(x_2\).<a class="headerlink" href="#simpleclustering" title="Link to this table">#</a></caption>

<thead>

</tr>

</thead>

<tbody>

</tr>

</tr>

</tr>

</tr>

</tr>

</tr>

</tr>

</tr>

</tbody>

</table>

</div>

Question for you

<a class="reference internal" href="#clustersa">Fig. 5.5</a>, <a class="reference internal" href="#clustersb">Fig. 5.6</a> and <a class="reference internal" href="#clustersc">Fig. 5.7</a> show three clustering arrangements \(\mathcal{A}_1\), \(\mathcal{A}_2\) and \(\mathcal{A}_3\) for the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>. Each clustering arrangement consists of \(K=2\) clusters and samples belonging to the same clusters are displayed using the same colour.

Which clustering arrangement matches the statement samples within the same cluster are close, samples from different clusters are far apart?

Submit your response here: <a href="" target = "_blank">Your Response</a>

</div>

Fig. 5.5 Clustering arrangement \(\mathcal{A}_1\) for the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>.<a class="headerlink" href="#clustersa" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.6 Clustering arrangement \(\mathcal{A}_2\) for the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>.<a class="headerlink" href="#clustersb" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.7 Clustering arrangement \(\mathcal{A}_3\) for the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>.<a class="headerlink" href="#clustersc" title="Link to this image">#</a>

</figcaption>

</figure>

Visually, the clustering arrangement shown in <a class="reference internal" href="#clustersa">Fig. 5.5</a> is the one that represents best the idea that samples within the same cluster are close, samples from different clusters are far apart. Unfortunately, we will not always be able to visualise our datasets and even if we could, we would rarely face trivial scenarios like the one shown in <a class="reference internal" href="#clustersa">Fig. 5.5</a>. We therefore need an approach that will allow us to compare quantitatively, not visually, different clustering arrangements so that we can identify the best one. Specifically, we need a cost function.

K-means uses a cost function that is based on the notions of intra-cluster sample scatter \(I(C_k)\) and inter-cluster sample scatter \(O(C_k, C_l)\). Given a cluster \(C_k\), the intra-cluster scatter \(I(C_k)\) quantifies how far, on average, two samples in \(C_k\) are from one another. The intra-cluster scatter can be quantified as the sum of the squared distances between every pair of samples within the cluster, divided by the number of samples in the cluster, \(N_k\):

(5.2)<a class="headerlink" href="#equation-eqicss" title="Link to this equation">#</a>\[

I(C_k) = \frac{1}{2}\times \frac{1}{N_k} \sum_{\boldsymbol{x}_i, \boldsymbol{x}_j \in C_k} d^2_{i,j}

\]</div>

Note that the square distance between every pair of samples \(i\) and \(j\) appears twice in the summation expresion. The reason is that the terms \(d^2_{i,j}\) and \(d^2_{j,i}\), which correspond to the same squared distance between samples \(i\) and \(j\), are both included in the summation. The factor \(\frac{1}{2}\) compensates for this double counting.

Let us now describe the inter-cluster scatter \(O(C_k, C_l)\). Given two clusters \(C_k\) and \(C_l\), the inter-cluster scatter \(O(C_k, C_l)\) quantifies the average distance between two samples belonging to \(C_k\) and \(C_l\) respectively and can be mathematically expressed as

(5.3)<a class="headerlink" href="#equation-eqocss" title="Link to this equation">#</a>\[

O(C_k, C_l) = \frac{1}{N_{k,l}}\sum_{\boldsymbol{x}_i \in C_k, \boldsymbol{x}_i \in C_l} d^2_{i,j}

\]</div>

where \(N_{k,l}\) is the number of pairs of samples, such that the first sample belongs to cluster \(C_k\) and the second to cluster \(C_l\).

Using the idea that samples within the same cluster are close, whereas samples from different clusters are far apart, the best clustering arrangement \(\mathcal{A}_{opt}\) can be identified as the one with the lowest intra-cluster scatter or the one with the highest inter-cluster scatter. It can be shown that minimising the intra-cluster scatter also maximises the inter-cluster scatter and therefore, we can choose one quantity or another to define a cost function for K-means. Given a clustering arrangement \(\mathcal{A}=\{C_1,..., C_K\}\), we will define K-means cost function \(E\{\mathcal{A}\}\) as the sum of the intra-cluster scatter values of each cluster \(C_k\) in \(\mathcal{A}\):

(5.4)<a class="headerlink" href="#equation-eqkmeanscost" title="Link to this equation">#</a>\[

E\{\mathcal{A}\} = \sum_{C_k \in \mathcal{A}} I(C_k)

\]</div>

The interpretation of the K-means cost \(E\{\mathcal{A}\}\) is strightforward: the closer the samples within each cluster in the arrangement, the better. Now that we have defined a cost function for K-means, if we are given several candidate clustering arrangements, to select the best one we will first calculate the cost of each candidate and then we will select the one with the lowest cost. Let us illustrate this approach using our previous example, where we considered three clustering arrangement \(\mathcal{A}_1\) (<a class="reference internal" href="#clustersa">Fig. 5.5</a>), \(\mathcal{A}_2\) (<a class="reference internal" href="#clustersb">Fig. 5.6</a>) and \(\mathcal{A}_3\) (<a class="reference internal" href="#clustersc">Fig. 5.7</a>). As a first step, go ahead and calculate \(E\{\mathcal{A}_1\}\), the K-means cost of the clustering arrangement \(\mathcal{A}_1\).

Question for you

The clustering arrangement \(\mathcal{A}_1\) (<a class="reference internal" href="#clustersa">Fig. 5.5</a>) consists of two clusters \(C_1\) and \(C_2\) defined as the following collections of samples:

</ul>

Calculate \(E\{\mathcal{A}_1\}\), the K-means cost of clustering arrangement \(\mathcal{A}_1\).

Submit your response here: <a href="" target = "_blank">Your Response</a>

</div>

To calculate the K-means cost \(E\{\mathcal{A}_1\}\), we need to add the intra-cluster scatter values of clusters \(C_1\) and \(C_2\). In this particular example, the intra-cluster scatter value is the same for clusters \(C_1\) and \(C_2\), \(I(C_1)=I(C_2)\), and therefore we only need to calculate one of them, for instance \(I(C_1)\). Let us calculate \(I(C_1)\) by first obtaining the sum of all the squared distances to each sample in \(C_1\), and the adding all such sums. Starting from \((0, 3)\) and moving clock-wise we have:

<li>Sum of squared distances to \((0,3)\): \((1^2+1^2)+(2^2+0)+(1^2+(-1)^2) = 8\).</li>

<li>Sum of squared distances to \((1,4)\): \((1^2+(-1)^2)+(0+(-2)^2)+ ((-1)^2+(-1)^2) = 8\).</li>

<li>Sum of squared distances to \((2,3)\): \(((-1)^2+(-1)^2)+((-2)^2+0)+((-1)^2+1^2) = 8\).</li>

<li>Sum of squared distances to \((1,2)\): \(((-1)^2+1^2)+(0+2^2)+(1^2+1^2) = 8\).</li>

</ul>

Using the sums of squared distances to each sample in \(C_1\), the intra-cluster scatter value \(I(C_1)\) can be obtained as

I(C_1)=\frac{1}{2 \times 4} (8+8+8+8)=4

\]</div>

Since \(I(C_1)=I(C_2)\), the resulting K-means cost of \(\mathcal{A}_1\) is

E\{\mathcal{A}_1\} = I(C_1) + I(C_2) = 4 + 4 = 8

\]</div>

Following the same procedure for clustering arrangements \(\mathcal{A}_2\) and \(\mathcal{A}_3\), their K-means costs are:

E\{\mathcal{A}_2\} = 27 + 15 = 42

\]</div>

E\{\mathcal{A}_3\} = 21 + 21 = 42

\]</div>

The best clustering arrangement is therefore \(\mathcal{A}_1\), which agrees with our previous visual selection.

In this example, we have compared the K-means cost of three candidate clustering arrangments and have selected the one with the lowest cost. In general, we will be given a dataset and will be asked to find the best clustering arrangement amongst all the possible clustering arrangements. In other words, we will need to solve an optimisation problem. As we shall see in the next section, K-means is in fact an optimisation method to find the clustering arrangement that achieves the lowest sum of intra-cluster scatters.

</section>

<h4>5.4.1.2. K-means as an optimisation method<a class="headerlink" href="#k-means-as-an-optimisation-method" title="Link to this heading">#</a></h4>

Using the notion of intra-cluster scatter we have defined the K-means cost <a class="reference internal" href="#equation-eqkmeanscost">(5.4)</a>. Coming up with a notion of cost is only half of the job, as we still need to find the clustering arrangement that minimises it. In other words, we need to find the optimal clustering arrangement. Mathematically, we express this task as the optimisation problem

(5.5)<a class="headerlink" href="#equation-eqminimea" title="Link to this equation">#</a>\[

\mathcal{A}_{opt} = \underset{\mathcal{A} \in \boldsymbol{\mathcal{A}}}{\operatorname{argmin}} E\{\mathcal{A}\}

\]</div>

where \(\mathcal{A}_{opt}\) is the optimal clustering arrangement, \(E\{\mathcal{A}\}\) is the K-means cost function defined in <a class="reference internal" href="#equation-eqkmeanscost">(5.4)</a> and \(\boldsymbol{\mathcal{A}}\) is the set of all the possible clustering arrangements.

So how do we find the optimal clustering arrangement \(\mathcal{A}_{opt}\) among all the candidates in \(\boldsymbol{\mathcal{A}}\)? A simple option would be to calculate the cost of every clustering arrangement in \(\boldsymbol{\mathcal{A}}\) and select the one with the lowest cost. This option is unfortunately impractical, as in general we should expect a large number of candidate clustering arrangements. For instance, for the small 8-sample dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a> there are 128 different 2-cluster arrangements. For a still modest dataset like the 50-samples one shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>, the number of potential 2-cluster arrangements grows to more than 560 trillion. Computing the K-means cost of every candidate solution is clearly not a sensible avenue to solve <a class="reference internal" href="#equation-eqminimea">(5.5)</a>.

K-means is an iterative algorithm to solve <a class="reference internal" href="#equation-eqminimea">(5.5)</a> that shares many similarities with gradient descent. In K-means, each cluster \(C_k\) is represented by a cluster prototype \(\boldsymbol{c}_k\) defined as the average of all the samples within the cluster:

(5.6)<a class="headerlink" href="#equation-eqkmeansproto" title="Link to this equation">#</a>\[

\boldsymbol{c}_k = \frac{1}{N_k} \sum_{\boldsymbol{x}_i \in C_k} \boldsymbol{x}_i,

\]</div>

which explains the name K-means. Each cluster prototype can therefore be interpreted as a summary which indicates where a cluster of samples is centred in the attribute space, as illustrated in <a class="reference internal" href="#clusterscenters">Fig. 5.8</a>.

Fig. 5.8 Cluster prototypes (represented by the symbol \(+\)) for the clustering arrangement \(\mathcal{A}_1\) shown in <a class="reference internal" href="#clustersa">Fig. 5.5</a>.<a class="headerlink" href="#clusterscenters" title="Link to this image">#</a>

</figcaption>

</figure>

Interestingly, the intra-cluster scatter \(I(C_k)\), which was defined in <a class="reference internal" href="#equation-eqicss">(5.2)</a>, can be calculated using the squared distance \(d^2_i\) between each sample \(\boldsymbol{x}_i\) in a cluster \(C_k\) and the cluster prototype \(\boldsymbol{c}_k\) as

(5.7)<a class="headerlink" href="#equation-eqicss2" title="Link to this equation">#</a>\[

I(C_k) = \sum_{\boldsymbol{x}_i \in C_k} d^2_{i}

\]</div>

For instance, in <a class="reference internal" href="#clusterscenters">Fig. 5.8</a>, the intra-cluster scatter \(I(C_1)\) can be calculated as the sum of all the squared distances from each sample in \(C_1\) to the prototype \(\boldsymbol{c}_1\) as \(I(C_1) = 1^2+1^2+1^2+1^2=4\). Note that computing \(I(C_k)\) in terms of the distances to the prototypes involves fewer operations than doing it in terms of the distances between every pair samples in the cluster. For instance, if we calculate the intra-cluster scatter of a cluster consisting of 10 samples, <a class="reference internal" href="#equation-eqicss">(5.2)</a> requires calculating and adding 100 squared distances, whereas <a class="reference internal" href="#equation-eqicss2">(5.7)</a> requires 10 squared distances only.

Computing the intra-cluster scatter as the sum of the squared distances to the cluster prototype offers the following alternative interpretation of our notion of cost: in a good clustering arrangement, samples are close to their cluster prototypes. As a consequence of this, K-means favours spherical clusters consisting of samples surrounding their protoypes. To be more precise, K-means favours convex clusters, where every pair of samples in the same cluster can be connected by a segment that does not cross a different cluster.

To find the best clustering arrangment, K-means proceeds iteratively. K-means starts by placing each of the \(K\) prototypes randomly in the attribute space. From this starting point, K-means iterates on the following two steps:

<li>Each sample is associated to the closest prototype, resulting in a new set of clusters.</li>

<li>New prototypes are calculated as the centers of the newly formed clusters.</li>

</ul>

As K-means proceeds, we will see samples being reassigned to different clusters until we reach a stable clustering arrangement where no sample is reassigned. This is our final clustering arrangement. <a class="reference internal" href="#kmeans1">Fig. 5.9</a>, <a class="reference internal" href="#kmeans2">Fig. 5.10</a>, <a class="reference internal" href="#kmeans3">Fig. 5.11</a> and <a class="reference internal" href="#kmeans4">Fig. 5.12</a> illustrate how K-means operates using the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a> as an example. As you can see, K-means refines iteratively an initial arrangement until it finds the clustering arrangement \(\mathcal{A}_1\).

Fig. 5.9 K-means initial arrangement for the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>, where \(K=2\). Prototypes are placed randomly in the attribute space.<a class="headerlink" href="#kmeans1" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.10 K-means clustering of the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>: First iteration.<a class="headerlink" href="#kmeans2" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.11 K-means clustering of the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>: Second iteration.<a class="headerlink" href="#kmeans3" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.12 K-means clustering of the dataset shown in <a class="reference internal" href="#simpleclustering">Table 5.2</a>: Third iteration and final solution.<a class="headerlink" href="#kmeans4" title="Link to this image">#</a>

</figcaption>

</figure>

<a class="reference internal" href="#kmeans-randomset-1">Fig. 5.13</a>, <a class="reference internal" href="#kmeans-randomset-2">Fig. 5.14</a> and <a class="reference internal" href="#kmeans-randomset-3">Fig. 5.15</a> illustrate how K-means operates on the dataset shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>. From an initial clustering arrangement created by placing \(K=2\) protoypes randomly in the attribute space, K-means progressively improves the arrangement until it finds the solution that best embodies the statements samples are close to their protoypes or samples within the same cluster are close, samples from different clusters are far apart. This solution is precisely the one that we found visually in <a class="reference internal" href="#clusters1b">Fig. 5.4</a>.

Fig. 5.13 K-means initial arrangement for the dataset shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>, where \(K=2\). Prototypes are placed randomly in the attribute space.<a class="headerlink" href="#kmeans-randomset-1" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.14 K-means clustering of the dataset shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>: First iteration.<a class="headerlink" href="#kmeans-randomset-2" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.15 K-means clustering of the dataset shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>: Second iteration and final solution.<a class="headerlink" href="#kmeans-randomset-3" title="Link to this image">#</a>

</figcaption>

</figure>

So far we have explored two examples where K-means returns the exact clustering arrangements that we would identify visually. We have used two simple examples precisely because we can visually find a solution to the clustering probem. In general, the dimensionality of our datasets will prevent us from using visual means. These are precisely the scenarios where K-means and other clustering algorithms demonstrate their power. Since we have no visual means to check whether the solution provided by K-means is indeed the one that minimises the K-means cost, it is important that we ask ourselves if, as an optimisation algorithm, K-means will always return the optimal arrangement. Moreover, in the examples that we have presented we have chosen the value \(K=2\) beforehand. This choice was based on our visual observation but in general this avenue will not be available. So how can we choose the value of \(K\)? In the following two sections, we will turn our attention to both questions.

</section>

<h4>5.4.1.3. Local minima in K-means<a class="headerlink" href="#local-minima-in-k-means" title="Link to this heading">#</a></h4>

We have presented K-means as an optimisation algorithm that shares many similarities with gradient descent. Specifically, K-means starts with a random initial solution that is improved iteratively until a final, stable solution is reached. As it turns out, K-means shares another similarity with gradient descent: there is always a risk that K-means might reach a final solution that is not globally optimal, but locally. To understand how this could happen, have a look at the prototype initialisation in <a class="reference internal" href="#kmeans-local1">Fig. 5.16</a>. In this initialisation, one of the prototypes is positioned closer to every single sample in the dataset than the other prototype. Because of this, all the samples are assigned to the first prototype, resulting in a final clustering arrangement where one cluster includes all the samples in the dataset and the other one is empty. This final clustering arrangement is shown in <a class="reference internal" href="#kmeans-local2">Fig. 5.17</a> and constitutes a local optimum of the cost function \(E\{A\}\). The global optimum was presented in <a class="reference internal" href="#kmeans-randomset-3">Fig. 5.15</a>.

Fig. 5.16 K-means initial arrangement for the dataset shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>, where \(K=2\). Prototypes are placed randomly in the attribute space.<a class="headerlink" href="#kmeans-local1" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.17 K-means clustering of the dataset shown in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>: First iteration and final solution. The initial location of the cluster prototypes has resulted in K-means getting stuck in a local minimum: the first cluster has all the samples in the dataset, whereas the second is empty.<a class="headerlink" href="#kmeans-local2" title="Link to this image">#</a>

</figcaption>

</figure>

In order to reduce the risk of producing as a final solution a poor local optimum of the K-means cost \(E\{A\}\), we can run K-means several times, using each time different, random initial prototypes. The final solution will be the one with the lowest K-means cost amongst all the solutions produced by each run of K-means. This is the same strategy that we suggested when we were discussing local optima in the context of gradient descent.

</section>

<h4>5.4.1.4. Selecting \(K\)<a class="headerlink" href="#selecting-k" title="Link to this heading">#</a></h4>

Before running K-means on a dataset, we need to set the number of clusters \(K\). Which value should we then choose for \(K\)? As previously mentioned, the number of clusters \(K\) is a hyperparameter in K-means and its value leads to models of different degrees of complexity. Specifically, low values of \(K\) lead to simple models (consisting of a few clusters), whereas high values of \(K\) result in complex models (consisting of many clusters).

To set the value of \(K\) we need to frame our clustering problem within its deployment context. In some cases this value will be directly given by the problem that we want to solve. For instance, imagine that we need to identify 3 average chest sizes to manufacture T-shirts of 3 different sizes. To do so, we can apply K-means to a dataset that records the chest size of a group of individuals using \(K=3\) and use the final prototypes as the desired average chest sizes. Therefore, in this example the value of \(K\) is given. In other cases, our clustering problem will be embedded within a main problem that defines a notion of deployment quality, and the suitability of a particular value of \(K\) will be linked to the quality of the main solution. Finding a suitable customer segmentation solution for a recommendation system is an example of this scenario. If we use K-means for customer segmentation, different values of \(K\) will lead to different customer segmentation solutions. In this problem, the right value of \(K\) will be the one that results in the most effective recomendation system. Therefore, the quality of the main solution dictates what the right value of \(K\) should be.

It is worth exploring and reflecting on the behaviour of the intra-cluster scatter as we change the value of \(K\). One basic observation, illustrated in <a class="reference internal" href="#clusteringelbow">Fig. 5.18</a>, the K-means cost \(E\{A\}\) always decreases as \(K\) increases. This behaviour might mislead us into thinking that increasing the number of clusters produces better clustering solutions, as they exhibit a lower cost. Why is this conclusion wrong? First, the described behaviour should not be surprising. Increasing \(K\) results in more, smaller clusters and therefore lower average distance between samples within the same cluster. When we use as many prototypes as samples, each sample will constitute its own cluster and therefore the intra-cluster scatter will be identically zero. Second and more importantly, we need to remember that the K-means cost is not a deployment quality metric. Given a value of \(K\), the K-means cost is used to find the optimal clustering arrangement. Once we have found the optimal clustering arrangement for each value of \(K\), we need to quantify its quality in deployment conditions using a quality metric.

Fig. 5.18 As we increase the value of the hyperparameter \(K\) in K-means, the intra-cluster sample scatter decreases first sharply, then slowly. The curve representing the dependence of the intra-cluster sample scatter on \(K\) resembles a flexed arm.<a class="headerlink" href="#clusteringelbow" title="Link to this image">#</a>

</figcaption>

</figure>

There is another interesting behaviour that we can observe in <a class="reference internal" href="#clusteringelbow">Fig. 5.18</a>: the rate of decrease of the intra-cluster scatter cost changes as we increase the value of \(K\). Specifically, for \(K < 4\), the intra-cluster scatter cost drops quickly, then for \(K > 4\) it drops slowly. This suggests that something might be going on around \(K=4\). One usual interpretation of this observation is that beyond \(K=4\), K-means starts splitting true clusters. Let us illustrate this phenomenon using a simple visual example. <a class="reference internal" href="#clusteringelbowk1">Fig. 5.19</a> shows a dataset which visually consists of four distinct clumps of samples. The solutions provided by K-means for \(K=2\) and \(K=4\) are shown in <a class="reference internal" href="#clusteringelbowk2">Fig. 5.20</a> and <a class="reference internal" href="#clusteringelbowk4">Fig. 5.21</a>. For \(K=4\), K-means creates the same clusters that we identified visually. <a class="reference internal" href="#clusteringelbowk5">Fig. 5.22</a> shows that when we increase the value of the hyperparameter \(K\) to \(K=5\), K-means splits the clump located around \((10,5)\) into two separate clusters. As we continue to increase \(K\), we would expect other clumps to be split further.

Fig. 5.19 Simple dataset which visually can be described as four clumps of samples centred at \((0,0)\), \((0,5)\), \((10,0)\) and \((10,5)\).<a class="headerlink" href="#clusteringelbowk1" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.20 K-means clustering of the dataset shown in <a class="reference internal" href="#clusteringelbowk1">Fig. 5.19</a> using \(K=2\).<a class="headerlink" href="#clusteringelbowk2" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.21 K-means clustering of the dataset shown in <a class="reference internal" href="#clusteringelbowk1">Fig. 5.19</a> using \(K=4\).<a class="headerlink" href="#clusteringelbowk4" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.22 K-means clustering of the dataset shown in <a class="reference internal" href="#clusteringelbowk1">Fig. 5.19</a> using \(K=5\).<a class="headerlink" href="#clusteringelbowk5" title="Link to this image">#</a>

</figcaption>

</figure>

In general we won’t be able to visualise our datasets and identify clumps of samples as we did for the dataset shown in <a class="reference internal" href="#clusteringelbowk1">Fig. 5.19</a>. Luckily, we will always be able to plot the dependence of the intra-sample scatter on \(K\). The corresponding graph looks like a flexed arm where the elbow indicates the value of \(K\) where the drop of the intra-cluster scatter changes from fast to slow, as in <a class="reference internal" href="#clusteringelbow">Fig. 5.18</a>. The elbow can then be used to identify the number of true clusters. This strategy known to select \(K\) is known as the elbow method. The elbow method and other similar analyses can reveal useful insights into the structure of the population. However, we need to remember that we should always select the value of \(K\) based on our notion of deployment quality.

</section>

<h3>5.4.2. Connectivity-based methods<a class="headerlink" href="#connectivity-based-methods" title="Link to this heading">#</a></h3>

The dataset represented in <a class="reference internal" href="#dbscan2">Fig. 5.23</a> consists of 100 samples described by two attributes \(x_A\) and \(x_B\). Visually, the distribution of samples in the attributes space is different from that of the dataset represented in <a class="reference internal" href="#clusters1a">Fig. 5.3</a>, where samples appeared to be clustered around two centres in the attribute space. How would you group visually the samples shown in <a class="reference internal" href="#dbscan2">Fig. 5.23</a>?

Fig. 5.23 Distribution of samples suggesting non-convex clusters.<a class="headerlink" href="#dbscan2" title="Link to this image">#</a>

</figcaption>

</figure>

If we were to apply K-means with \(K=2\) to the dataset represented in <a class="reference internal" href="#dbscan2">Fig. 5.23</a>, we would obtain two clusters like the ones shown in <a class="reference internal" href="#k-means-non-convex">Fig. 5.24</a>. The resulting clusters are convex which, as you will remember, means that between any two samples of the same cluster, we will never find a sample from another cluster. Do you think this is a good clustering arrangement?

Question for you

Is <a class="reference internal" href="#k-means-non-convex">Fig. 5.24</a> a good clustering arrangement?

Submit your response here: <a href="" target = "_blank">Your Response</a>

</div>

Fig. 5.24 Cluster centers.<a class="headerlink" href="#k-means-non-convex" title="Link to this image">#</a>

</figcaption>

</figure>

As discussed in sections <a class="reference internal" href="#costanddepl">Cost and quality</a> and <a class="reference internal" href="#selectk">Selecting K</a>, the answer to this question depends on the main problem that we want to solve. If we want to manufacture T-shirt of two different sizes and \(x_A\) and \(x_B\) represent the chest width and length of samples from our target population, the prototypes provided by K-means clustering would ensure that on average, our T-shirts are suitable for as many people as possible and hence <a class="reference internal" href="#k-means-non-convex">Fig. 5.24</a> would be the right solution. However not every problem requires convex clusters and there will be cases where the solution provided by K-means migth not be the right one for the main problem at hand.

Regardless of the main problem, you might feel that the convex solution provided by K-means does not capture the underlying structure of the population. After looking at <a class="reference internal" href="#dbscan2">Fig. 5.23</a>, you might have visually identified non-convex clusters where samples are not distributed around a cluster center. If your proposed clusters are non-convex then, unlike K-means, you will have used a notion of similarity that is not based on proximity. What could this notion of similarity be?

<h4>5.4.2.1. Similarity as connectivity: DBSCAN<a class="headerlink" href="#similarity-as-connectivity-dbscan" title="Link to this heading">#</a></h4>

Imagine that you could jump from one sample to another sample, provided that both samples are close enough. Using this idea, we can define the new notion of connectivity. We will say that two samples are connected if you can reach one from the other either jumping directly or using other samples as stepping stones. We can use this notion of connectivity to define clusters as groups of samples that are connected.

When developing a connectivity-based clustering method, it is important to note that:

<li>We need to specify the maximum distance that will connect directly two samples. Using a short maximum distance disconnects samples and result in many small clusters, whereas a long maximum distance connects more samples and result in few, large clusters.</li>

<li>A small deviation in the location of one single sample could disconnect or connect two or more sets of samples. Therefore, small random deviations in our dataset can result in very different clustering arrangements. To design robust clustering methods, we need to implement strategies that minimise the impact of randomness on the final clustering solution.</li>

</ul>

Density-based methods are connectivity-based methods that rather than simply connecting individual samples, connect regions in the attribute space that are locally dense, in other words, that contain a large number of samples. One of the most popular density-based methods is DBSCAN, which stands for density-based spatial clustering of applications with noise. DBSCAN includes two quantities, namely a radius \(r\) and a threshold \(t\), which are used to define dense regions in the attribute space. Using \(r\) and \(t\), we will say that a sample is in a locally dense region of the attribute space, if within a radius \(r\) we observe more than \(t\) samples.

DBSCAN distinguishes between three types of samples:

<li>Samples surrounded by more than \(t\) samples within a radius \(r\) are known as core samples. Thus, core samples are in a dense region of the attribute space.</li>

<li>Samples surrounded by fewer than \(t\) samples within a radius \(r\) are by definition not in a dense region of the attribute space. If they include at least one core sample within a radius \(r\) they are border samples.</li>

<li>Samples that do not meet any of the previous conditions are known as outlier samples. Note that the term outlier is a name given to these samples by the authors of DBSCAN and should not be confused with the usual meaning of the term outlier.</li>

</ul>

<a class="reference internal" href="#dbscan-illustration">Fig. 5.25</a> shows a simple dataset consisting of samples described by two attributes \(x_1\) and \(x_2\). As you can see, some regions in the attribute space are more dense than others. For instance, the rectangular region \(-4<x_1<-2\) and \(-1<x_2<0\) contains no samples, the region \(0<x_1<2\) and \(-2<x_2<-1\) contains one sample and \(-2<x_1<0\) and \(0<x_2<1\) contains three samples.

Fig. 5.25 Simple dataset consisting of samples described by two attributes \(x_1\) and \(x_2\).<a class="headerlink" href="#dbscan-illustration" title="Link to this image">#</a>

</figcaption>

</figure>

<a class="reference internal" href="#dbscan-illustration-2">Fig. 5.26</a> identifies the core, border and outlier samples resulting from applying DBSCAN to the dataset shown in <a class="reference internal" href="#dbscan-illustration">Fig. 5.25</a>. In this example, we have used the radius and threshold values \(r=1\) and \(t=3\). As you can see, DBSCAN separate samples that lie within high-density regions of the attribute space, from samples that lie within low-density regions of the attribute space.

Fig. 5.26 Core (\(\circ\)), border (\(\oplus\)) and outlier (\(\times\)) samples returned by DBSCAN when applied to the dataset shown in <a class="reference internal" href="#dbscan-illustration">Fig. 5.25</a> using \(r=1\) and \(t=3\).<a class="headerlink" href="#dbscan-illustration-2" title="Link to this image">#</a>

</figcaption>

</figure>

Once core, border and outlier samples have been identified, DBSCAN proceeds by first excluding outlier samples. Then cluster backbones are created by grouping core samples that lie within each other’s neighbourhoods. Each backbone thus produced defines one DBSCAN cluster. Finally, border samples are assigned to the backbone that they are connected to. Note that by connecting core samples within reach from one another, rather than connecting any two samples within reach from one another, we are implicitly connecting dense regions. This makes DBSCAN more robust against small, random deviations in the location of our samples.

</section>

<h4>5.4.2.2. DBSCAN hyperparameters<a class="headerlink" href="#dbscan-hyperparameters" title="Link to this heading">#</a></h4>

In contrast with K-means, DBSCAN does not require that we impose beforehand the number of clusters that we would like to discover. This should not be interpreted as DBSCAN being superior over K-means, in that it finds the appropriate number of clusters on its own. DBSCAN defines two hyperparameters, namely the radius \(r\) and the threshold \(t\), whose values lead to clustering arrangements of different complexity. For some values of \(r\) and \(t\) DBSCAN will produce many, small clusters, whereas for other values it will produce few, large clusters. Hence, the role of \(r\) ant \(t\) in DBSCAN is analogous to the role of \(K\) in K-means: they control the degree of complexity of the final solution.

To understand how \(r\) and \(t\) control the degree of complexity of the final solution, we need to revisit the basic principles of DBSCAN. In a nutshell, DBSCAN connects samples that are close and in high-density regions. Two samples are close if their distance is lower than \(r\), and they are in a high-density region, in other words, they are core, if they have more than \(t\) neughbouring samples within a radius \(r\). Reducing the value of \(r\) produces two effects. First, it disconnects core samples which were previously close and now are further than the new, smaller value of \(r\). And second, it reduces the number of core samples, as within a small radius we will find fewer neighbouring samples than within a large radius. Hence, small values of \(r\) results in solutions consisting of many, small clusters. Increasing \(t\) also results in many, more clusters, as for a sample to be considered core, within the same radius \(r\) more neighbouring samples will be required. Finally, since reducing \(r\) and increasing \(t\) reduces the number of core samples, a greater number of outliers will be produced.

<a class="reference internal" href="#dbscan-r5">Fig. 5.27</a>, <a class="reference internal" href="#dbscan-r4">Fig. 5.28</a> and <a class="reference internal" href="#dbscan-r35">Fig. 5.29</a> show the clusters discovered by DBSCAN when applied to the dataset shown in <a class="reference internal" href="#dbscan2">Fig. 5.23</a>, for a threshold \(t=3\) and radius values \(r=0.7\), \(r=0.5\) and \(r=0.4\), respectively. The clustering arrangements produced by DBSCAN clearly identify and group close samples with high-density regions. As we can see, as the value of the radius \(r\) decreases the number of clusters increase. The number of outliers also increase, as expected.

Fig. 5.27 DBSCAN clustering solution for the dataset shown in <a class="reference internal" href="#dbscan2">Fig. 5.23</a> using \(t=3\) and \(r=0.7\).<a class="headerlink" href="#dbscan-r5" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.28 DBSCAN clustering solution for the dataset shown in <a class="reference internal" href="#dbscan2">Fig. 5.23</a> using \(t=3\) and \(r=0.5\).<a class="headerlink" href="#dbscan-r4" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.29 DBSCAN clustering solution for the dataset shown in <a class="reference internal" href="#dbscan2">Fig. 5.23</a> using \(t=3\) and \(r=0.4\).<a class="headerlink" href="#dbscan-r35" title="Link to this image">#</a>

</figcaption>

</figure>

As with any other machine learning model, to set the values of the hyperparameters \(r\) and \(t\) we need to implement a validation task. This validation task should allow us to compare in deployment conditions the quality of the DBSCAN solutions built using different values of \(r\) and \(t\). This validation task depends on the main problem that we want to solve, which defines the deployment conditions and the notion of deployment quality.

</section>

<h3>5.4.3. Hierarchical clustering<a class="headerlink" href="#hierarchical-clustering" title="Link to this heading">#</a></h3>

The hyperparameter \(K\) in K-means and the hyperparameters \(r\) and \(t\) in DBSCAN control the complexity of the final clustering solution. Depending on the value of their hyperparameters, K-means and DBSCAN can provide solutions that range from arrangements consisting of many, small clusters to arrangements that have few, large clusters. Thus, hyperparameters in clustering play a similar role to hyperparameters in supervised learning.

So far, our discussion around hyperparameters has focused on finding the right values, understood as the ones that result in the highest deployment quality. However, there is nothing intrinsically wrong about the clustering arrangement found for other choices of hyperparameter values. Given any choice of hyperparamenter values, the corresponding clustering solution is valid on its own, although in the context of a specific main problem, one clustering arrangement might be better suited than others. In fact, we can see each clustering arragnement produced by different choices of hyperparameters as a unique description of the underlying population.

By changing the values of the hyperparameters of a clustering method, we can build a multi-level description of a population, from low-complexity descriptions to high-complexity ones. Given a dataset, there exist two trivial clustering solutions at both ends of this multi-level clustering description. At the top, we have a description consisting of one single cluster that encompasses all the samples in the dataset. At the bottom, we have a description where each sample is its own clusters and there are as many clusters as samples. Changing the hyperparameter values of the clustering method we can build intermediate descriptions between the two extremes.

The previous interpretation is at the core of the strategy implemented by hierarchical clustering methods. Hierarchical clustering methods build clustering arrangements at multiple levels. The resulting collection of clustering arrangements is hierarchical in the sense that any cluster in one level contains all the samples from one or more clusters in the level below. <a class="reference internal" href="#hier-vis">Fig. 5.31</a> shows the top four levels of a hierarchical clustering solution for the simple dataset shown in <a class="reference internal" href="#hier-dataset">Fig. 5.30</a>. As you can see, at the top of the hierarchy we find a clustering arrangement consisting of just one cluster. As we go down, clusters are split into smaller clusters.

Fig. 5.30 Simple dataset consisting of 10 samples.<a class="headerlink" href="#hier-dataset" title="Link to this image">#</a>

</figcaption>

</figure>

Fig. 5.31 Top four levels of a hyerarchical clustering solution for the dataset shown in <a class="reference internal" href="#hier-dataset">Fig. 5.30</a>.<a class="headerlink" href="#hier-vis" title="Link to this image">#</a>

</figcaption>

</figure>

The relationship between clusters at different levels of a hierarchical solution can be represented as a dendrogram. At the bottom of the dendrogram, we find the arrangement where each sample is one cluster and at the top, the whole dataset. A dendrogram for a hierarchical clustering solution for the dataset shown in <a class="reference internal" href="#hier-dataset">Fig. 5.30</a> is shown in <a class="reference internal" href="#hier-dendrogram">Fig. 5.32</a>.

Fig. 5.32 Dendrogram representation of a hyerarchical clustering solution for the dataset shown in <a class="reference internal" href="#hier-dataset">Fig. 5.30</a>. Numbers correspond to the sample identifiers included in <a class="reference internal" href="#hier-dataset">Fig. 5.30</a>.<a class="headerlink" href="#hier-dendrogram" title="Link to this image">#</a>

</figcaption>

</figure>

There are two basic strategies in hierarchical clustering:

<li>The divisive or top-down approach splits clusters starting from the top of the dendrogram and stops at the bottom level.</li>

<li>The agglomerative or bottom-up merges clusters, starting from the bottom until we reach the top level.</li>

</ul>

The main difference between hierarchical approaches is the rule that determines which clusters to split in divisive approaches, and which clusters to merge in agglomerative approaches. Three examples of merging strategies in agglomerative hierarchical clustering include:

<li>Single linkage: uses the distance between the two closest samples from every pair of clusters. This option results in clusters of arbitrary shapes.</li>

<li>Complete linkage: uses the distance between the two further samples from every pair of clusters. This choice produces clusters that tend to have a spherical shape.</li>

<li>Group average: uses the average distance between samples in two cluster. It also produces spherical shapes.</li>

</ul>

<a class="reference internal" href="#dbscan-hier-dbscan">Fig. 5.33</a> shows the top 4 levels of a divise hierarchical clustering solution for the dataset shown in <a class="reference internal" href="#dbscan2">Fig. 5.23</a>. As you can see, the top level consists of one single cluster formed by every sample in the dataset and every time we move down the hierarchy of solutions, one of the clusters is split into two new clusters.

Fig. 5.33 Top 4 levels of a divise hierarchical clustering solution for the dataset shown in <a class="reference internal" href="#dbscan2">Fig. 5.23</a>.<a class="headerlink" href="#dbscan-hier-dbscan" title="Link to this image">#</a>

</figcaption>

</figure>

By design, hierarchical clustering methods produce multiple clustering arrangements organised hierarchically. At the top of the hierarchy we find the clustering arrangement with the lowest complexity and at the bottom, the one with the highest complexity. Given a nested problem, each clustering arrangement in the hierarchy constitutes a candidate solution that can be assessed indirectly using the notion of deployment quality that defines the main problem. Moreover, hierarchical clustering solutions are interesting in their own right, and not only as candidate solutions for a nested problem, as they can shed light on the nature of the underlying population. Hierarchical clustering methods are found in many pure scientific endeavours. Language trees and life trees are examples of scientific models that can be built using hierarchical approaches. The structure of language and life trees can provide insight into historical processes for which we otherwise lack evidence, such as immemorial human migrations and the evolution of living organisms. By providing descriptions of the structure of the underlying population, clustering methods and in general unsupervised learning methods, are amongst the most productive tools for scientists in every field of study, from the humanities to the physical sciences.

</section>

<h2>5.5. Basis discovery<a class="headerlink" href="#basis-discovery" title="Link to this heading">#</a></h2>

<a class="reference internal" href="#pca-example1">Fig. 5.34</a> shows a simple dataset consisting of 50 samples described by two attributes, \(x_1\) and \(x_2\). How would you describe this dataset?

Fig. 5.34 Simple dataset of 50 samples arrenged roughly in a straight line.<a class="headerlink" href="#pca-example1" title="Link to this image">#</a>

</figcaption>

</figure>

One prominent feature of the dataset shown in <a class="reference internal" href="#pca-example1">Fig. 5.34</a> is that its samples are roughly arranged in a straight line. Looking for directions along which samples in a dataset are spread out can reveal interesting properties of the underlying population. Specifically, such directions can suggest previously unknown relationships between the attributes of our population. For instance, the linear arrangement observed in <a class="reference internal" href="#pca-example1">Fig. 5.34</a> suggests that population samples whith large \(x_1\) values will also exhibit large \(x_2\) values. Directions of interest can be visually identified in simple datasets, like the one shown in <a class="reference internal" href="#pca-example1">Fig. 5.34</a>. The question arises, how can we identify directions non-visually, in scenarios where the attribute space has many dimensions?

Basis discovery is a family of unsupervised learning approaches that use datasets to discover directions of interest in the attribute space. A basis in maths is a term that refers to a set of directions that we can combine to reach every location in a space. In machine learning, given a population defined by a set of attributes, by default we use as our basis the axes defined by each attribute, for instance \(x_1\) and \(x_2\) in <a class="reference internal" href="#pca-example1">Fig. 5.34</a>. This might sound like a platitude, however it is important to recognise that the axes defined by the attributes of the population are not the only choice that exists and other sets of axes can also be used. Basis discovery methods use datasets to come up with new sets of axes for our populations. Each new axis constitutes a new direction of interest and can suggest relationships between the attributes of our population.

In this section we introduce principal components analysis (PCA), one of the most popular basis discovery methods. PCA identifies a set of perpendicular directions in the attribute space along which samples from a dataset spread out. In addition to identifying these directions, PCA quantifies the amount of spread along each direction. To understand PCA, we need to discuss first what we mean by sample spread along a direction and how to quantify it.

<h3>5.5.1. Measuring sample spread<a class="headerlink" href="#measuring-sample-spread" title="Link to this heading">#</a></h3>

View remainder of file in raw view

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

Ch_discovery.html

Latest commit

History

Ch_discovery.html

File metadata and controls